Welchen Zweck hat Graufarbe bei der DFS- und BFS-Implementierung in CLRS?

Question

In der Implementierung von DFS und BFS, CLRS Autoren unterscheiden 3 Farben für jeden Eckpunkt - grau, schwarz und weiß. Ich verstehe, dass schwarz und weiß bedeutet, ob Knoten besucht wurde oder nicht. Warum brauchen wir graue Farbe?

Meine Vermutung ist Zyklen zu erkennen, aber können wir auch Zyklen mit nur schwarz & weiß (d. H. Ohne das Grau) erkennen?

Answer 1

Der Hauptgrund ist, dem Leser zu helfen, das Konzept besser zu verstehen. Aber es gibt einige Algorithmen, die tatsächlich graue Knoten verwenden. Zum Beispiel zum Finden von Zyklen in einem gerichteten Diagramm benötigen Sie graue Knoten, da ein schwarz Nachbar keinen Zyklus angibt und nur grau Nachbarn erstellen Zyklen.

A->B, B->C, A->C 

A->C keinen Zyklus trotz C ist schwarz erstellen.