In vielen Implementierungen der Tiefensuche, die ich gesehen habe (zum Beispiel: hier ), wurde der Code zwischen einem grauen Scheitelpunkt (entdeckt, aber nicht alle seine Nachbarn wurden besucht) und einem schwarzen Scheitelpunkt (entdeckt und alle seine Nachbarn wurden besucht) unterschieden. . Was ist der Zweck dieser Unterscheidung? Es scheint, dass der DFS-Algorithmus niemals einen besuchten Scheitelpunkt besucht, unabhängig davon, ob er grau oder schwarz ist.
Bei der Ausführung einer DFS befindet sich ein Knoten in einem von drei Zuständen - vor dem Besuch, während des rekursiven Besuchs seiner Nachkommen und nachdem alle Nachkommen besucht wurden (Rückkehr zu seinem übergeordneten Knoten, dh Nachbearbeitungsphase). Die drei Farben entsprechen jedem der drei Zustände. Einer der Gründe für die Erwähnung von Farben und Zeitpunkt des Besuchs und der Rückkehr besteht darin, diese Unterscheidungen zum besseren Verständnis ausdrücklich vorzunehmen.
Natürlich gibt es tatsächliche Verwendungen dieser Farben. Betrachten wir einen gerichteten Graphen . Angenommen, Sie möchten G auf das Vorhandensein von Zyklen prüfen . Wenn der betreffende Knoten in einem ungerichteten Diagramm einen schwarzen oder grauen Nachbarn hat, zeigt er einen Zyklus an (und das DFS besucht ihn nicht, wie Sie bereits erwähnt haben). Bei einem gerichteten Graphen bedeutet ein schwarzer Nachbar jedoch keinen Zyklus. Betrachten wir zum Beispiel ein Diagramm mit 3 Vertices - A , B , und C , mit gerichteten Kanten als A → B , B → C , A → C . Angenommen, die DFS beginnt bei A, Dann Besuche , dann C . Wenn es zu A zurückgekehrt ist , prüft es, ob C bereits besucht wurde und schwarz ist. In der Grafik gibt es jedoch keinen Zyklus.
In einem gerichteten Graphen ist ein Zyklus nur dann vorhanden, wenn ein Knoten erneut gesehen wird, bevor alle seine Nachkommen besucht wurden. Mit anderen Worten, wenn ein Knoten einen Nachbarn hat, der grau ist, gibt es einen Zyklus (und nicht, wenn der Nachbar schwarz ist). Ein grauer Knoten bedeutet, dass wir derzeit seine Nachkommen untersuchen. Wenn ein solcher Nachkomme eine Kante zu diesem grauen Knoten hat, gibt es einen Zyklus. Für die Zykluserkennung in gerichteten Diagrammen sind 3 Farben erforderlich. Es könnte auch andere Beispiele geben, aber Sie sollten auf die Idee kommen.
Es ist eine Übung in CLRS, dass Sie die graue oder schwarze Farbe entfernen können, und der Algorithmus funktioniert gut mit nur zwei Farben, mit anderen Worten, es ist nicht wirklich erforderlich. Das Hauptziel beim Markieren von Scheitelpunkten besteht darin, sicherzustellen, dass wir nicht in eine Endlosschleife geraten, indem wir bereits besuchte Scheitelpunkte wiederholt besuchen.
Der Grund für die Verwendung von 3 Farben im DFS-Algorithmus ist hauptsächlich pädagogischer Natur: Er ist konzeptionell klarer und hilft den Schülern zu erkennen, was während der Ausführung für jeden Knoten vor sich geht.
quelle
Der graue Scheitelpunkt gibt an, dass Sie diesen Knoten besucht und in einer bestimmten Reihenfolge zu einem seiner Nachbarn übergegangen sind, dieser Knoten verfügt jedoch möglicherweise über mehrere benachbarte Scheitelpunkte. Dies ist hilfreich beim Zurückverfolgen, um nicht besuchte Scheitelpunkte zu erkunden.
Lassen Sie uns sagen Vertex A hat zwei Nachbarn B und C und B hat einen Nachbarn D .
Beginnen Sie bei Scheitelpunkt A, der weiß ist, und machen Sie ihn grau und bewegen Sie sich zu seinem Nachbarn.
Nehmen wir an, durch Auswahl der alphabetischen Reihenfolge wird der Scheitelpunkt B aufgerufen, der in weißer Farbe und als grau markiert ist.
Dann besucht D Weiß -> Grau D -> keine Nachbarn mehr. daher markiert D-> schwarz .
Nun zieht zurück nach B in Grau und nicht mehr nieghbors. Daher Markierungen B-> schwarz .
AGewinnen Sie die Rückspuren A in Grau und besuchen Sie die Markierung c, um c-> Grau markiert keine Nachbarn mehr C als schwarz
Schließlich kehren Sie zu A zurück und markieren den Scheitelpunkt A als schwarz, da es keine weißen Scheitelpunkte mehr gibt und alle als schwarz.
quelle
In der DFS klassifizieren wir Kanten als Vorderkante, Hinterkante, Kreuzkante und Baumkante.
Wir verwenden 3 Farben, um die Kanten zu klassifizieren. und diese Farben stellen den Zustand des Scheitelpunkts dar, dh v. weiß: Der Scheitelpunkt v ist noch nicht entdeckt.
grey: v wurde bereits erkannt, aber alle von v aus erreichbaren Scheitelpunkte wurden noch nicht erkannt. Der Scheitelpunkt v befindet sich also noch im Stapel.
black: v ist bereits nicht mehr im Stapel. Ermittelt und fertig.
Wenn Sie bei der DFS auf einen grauen Scheitelpunkt durch Kante e stoßen, handelt es sich um eine Hinterkante. Wenn Sie durch Kante e auf einen schwarzen Scheitelpunkt stoßen, handelt es sich um eine Querkante / Vorderkante. Wenn Sie auf einen weißen Eckpunkt stoßen, rufen Sie DFS rekursiv auf.
quelle