Dans de nombreuses implémentations de recherche en profondeur d'abord que j'ai vues (par exemple: ici ), le code fait la distinction entre un sommet gris (découvert, mais pas tous ses voisins ont été visités) et un sommet noir (découvert et tous ses voisins ont été visités) . Quel est le but de cette distinction? Il semble que l'algorithme DFS ne visitera jamais un sommet visité, qu'il soit gris ou noir.
Lorsque vous effectuez un DFS, n'importe quel nœud se trouve dans l'un des trois états - avant d'être visité, lors de la visite récursive de ses descendants et après que tous ses descendants ont été visités (retour à son parent, c'est-à-dire phase de récapitulation). Les trois couleurs correspondent à chacun des trois états. L'une des raisons de mentionner les couleurs et l'heure de la visite et du retour est de faire explicitement ces distinctions pour une meilleure compréhension.
Bien sûr, il existe des utilisations réelles de ces couleurs. Considérons un graphe orienté . Supposons que vous vouliez vérifier G pour l'existence de cycles. Dans un graphique non orienté, si le nœud considéré a un voisin noir ou gris, il indique un cycle (et le DFS ne le visite pas comme vous le mentionnez). Toutefois, en cas d'un dirigé graphique, un voisin noir ne signifie pas un cycle. Par exemple, considérons un graphe avec 3 sommets - A , B , et C , avec des bords dirigés comme A → B , B → C , A → C . Supposons que le DFS commence à A, Puis visites , puis C . Lorsqu'il est revenu à A , il vérifie alors que C a déjà été visité et qu'il est noir. Mais il n'y a pas de cycle dans le graphique.
Dans un graphe orienté, un cycle est présent si et seulement si un nœud est revu avant que tous ses descendants aient été visités. En d'autres termes, si un nœud a un voisin qui est gris, alors il y a un cycle (et pas quand le voisin est noir). Un nœud gris signifie que nous explorons actuellement ses descendants - et si l'un de ces descendants a un bord avec ce nœud gris, alors il y a un cycle. Ainsi, pour la détection de cycle dans les graphiques dirigés, vous devez avoir 3 couleurs. Il pourrait aussi y avoir d'autres exemples, mais vous devriez avoir l'idée.
C'est un exercice dans CLRS que vous pouvez supprimer la couleur grise ou noire et l'algorithme fonctionne bien avec seulement deux couleurs, en d'autres termes, il n'est pas vraiment nécessaire. Le but principal du marquage des sommets est de s'assurer que nous ne tombons pas dans une boucle infinie en visitant à plusieurs reprises les sommets déjà visités.
La raison d'utiliser 3 couleurs dans l'algorithme DFS est principalement pédagogique: elle est conceptuellement plus claire, elle aide les étudiants à voir ce qui se passe pendant l'exécution pour chaque nœud.
la source
Le sommet gris indique que vous avez visité ce nœud et que vous êtes passé à l'un de ses voisins dans un certain ordre, mais il pourrait y avoir plus de sommets voisins sur ce nœud. Il peut être utile lors du retour en arrière pour explorer des sommets non visités.
Disons que Vertex A a deux voisins B et C et B a un voisin D .
commencez au sommet A qui est de couleur blanche et rendez-le gris et passez à son voisin.
Disons qu'en choisissant l'ordre alphabétique, il visite le sommet B qui est de couleur blanche et marque en gris.
Puis visite D de blanc -> gris D -> plus de voisins. marque donc D-> noir .
Maintenant, revenons à B en gris et plus de ports. D'où les marques B-> noires .
AGain revient en arrière A en gris et visite la marque c à c-> Gris plus aucun voisin marque C comme noir
enfin, revenons à A et marque le sommet A comme noir car il n'y a plus de sommets blancs et tout comme noir.
la source
Dans DFS, nous classons les bords en tant que bord avant, bord arrière, bord transversal et bord d'arbre.
Nous utilisons 3 couleurs pour classer les bords. et ces couleurs représentent l'état du sommet c'est-à-dire v. blanc: le sommet v n'est pas encore découvert.
gris: v a déjà été découvert, mais tous les sommets accessibles depuis v ne sont pas encore découverts. donc le sommet v est toujours dans la pile.
noir: v est déjà sorti de la pile. Découvert et terminé.
En faisant le DFS si vous rencontrez un sommet gris à travers le bord e, alors c'est un bord arrière. Si vous rencontrez un sommet noir à travers le bord e, alors c'est un bord transversal / bord avant. si vous rencontrez un sommet blanc, vous appellerez récursivement DFS.
la source