Was nutzt es, 3 Zustände für einen Vertex in DFS zu verwenden?

Dies ist eine Variation des DFS-Algorithmus, der in Einführung in Algorithmen von Coerman at al gezeigt wird.

Wenn Sie 3 statt nur 2 Farben verwenden, erhalten Sie mehr Informationen. Fist, es erlaubt Ihnen an jedem Punkt während des Algorithmus-Durchlaufs zu wissen, welche Scheitelpunkte gerade "offen" (grau) sind, welche "geschlossen" (schwarz) und welche noch unerforscht sind (weiß).

Wenn Sie außerdem "Timestamping" für die Farbgebung verwenden (eine Liste, die angibt, wann Sie jeden Scheitelpunkt in der Reihenfolge färben), in der DFS drei Farben verwendet, können Sie interessante Eigenschaften über den Graphen, z . Dies wird zum Beispiel verwendet, um zu bestimmen, ob ein Graph azyklisch ist oder nicht.

Beachten Sie, dass zum alleinigen Zweck der Entdeckung eines Graphen - die 3 Farben sind in der Tat nicht obligatorisch, und Übung 22-3.4 fordert Sie auf, das zu zeigen.

Sie haben Recht.

Anstatt ein Eckgrau einzufärben, können Sie es schwarz färben, und der Algorithmus funktioniert immer noch.

Es ist leicht zu sehen, dass nirgendwo im Code die Farben grau und schwarz geprüft werden. Die einzige Prüfung ist, ob ein Eckpunkt weiß ist oder nicht (die mit 2 markierte Linie). Das bedeutet, dass alle Farben, die nicht weiß sind, gleichwertig sind.

Ich vermute, der Punkt der Verwendung einer dritten Farbe ist hier für Ausführlichkeits- und / oder Visualisierungszwecke. Wenn Sie den Graphen anzeigen, während Sie ihn durchlaufen, macht es die dritte Farbe viel deutlicher, welcher Status der Traversierungsprozeß ist, d. H. Welche Knoten gerade "besucht" werden.