Quel est le but d'avoir la couleur grise dans l'implémentation DFS et BFS dans CLRS?

Question

Dans la mise en œuvre de DFS et BFS, les auteurs CLRS distinguent 3 couleurs pour chaque sommet - gris, noir et blanc. Je comprends que le noir et blanc signifie que le nœud a été visité ou non. Pourquoi avons-nous besoin de couleur grise?

Je suppose qu'il s'agit de détecter des cycles, mais pouvons-nous également détecter des cycles avec seulement du blanc & blanc (c'est-à-dire sans le gris)?

Answer 1

La raison principale est d'aider le lecteur à mieux comprendre le concept. Mais il existe certains algorithmes qui utilisent effectivement les nœuds gris. Par exemple, pour trouver des cycles dans un graphe orienté, vous devez gris nœuds car un voisin noir n'indique pas de cycle et seuls les gris voisins créent des cycles.

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

A->C ne crée pas un cycle en dépit C être noir.