W wielu implementacjach pierwszego wyszukiwania głębokości, które widziałem (na przykład: tutaj ), kod rozróżnia szary wierzchołek (wykryty, ale nie odwiedzono wszystkich jego sąsiadów) i czarny wierzchołek (odkryty i odwiedzono wszystkich jego sąsiadów) . Jaki jest cel tego rozróżnienia? Wygląda na to, że algorytm DFS nigdy nie odwiedzi odwiedzonego wierzchołka, niezależnie od tego, czy jest szary czy czarny.
Odpowiedzi:
Podczas wykonywania DFS, dowolny węzeł znajduje się w jednym z trzech stanów - przed odwiedzeniem, podczas rekurencyjnego odwiedzania swoich potomków i po odwiedzeniu wszystkich potomków (powrót do jego rodzica, tj. Faza podsumowania). Trzy kolory odpowiadają każdemu z trzech stanów. Jednym z powodów wymienienia kolorów oraz czasu wizyty i powrotu jest wyraźne dokonanie tych rozróżnień dla lepszego zrozumienia.
Oczywiście istnieją rzeczywiste zastosowania tych kolorów. Rozważmy skierowaną wykres . Załóżmy, że chcesz sprawdzić G pod kątem istnienia cykli. Na niekierowanym wykresie, jeśli rozważany węzeł ma czarnego lub szarego sąsiada, oznacza to cykl (i DFS nie odwiedza go, jak wspomniałeś). Jednak w przypadku wykresu skierowanego czarny sąsiad nie oznacza cyklu. Na przykład, należy rozważyć wykres z 3 - wierzchołki A , B , i C , z skierowanych krawędziach jak A → B , B → C , A → C . Załóżmy, że DFS zaczyna się od A, Następnie wizyty , następnie C . Po powrocie do A sprawdza, czy C był już odwiedzany i czy jest czarny. Ale na wykresie nie ma cyklu.
Na wykresie ukierunkowanym cykl występuje tylko wtedy, gdy węzeł jest ponownie widziany przed odwiedzeniem wszystkich jego potomków. Innymi słowy, jeśli węzeł ma sąsiada, który jest szary, wówczas występuje cykl (a nie gdy sąsiad jest czarny). Szary węzeł oznacza, że obecnie badamy jego potomków - a jeśli jeden z takich potomków ma przewagę do tego szarego węzła, wtedy jest cykl. Tak więc, aby wykryć cykl na ukierunkowanych wykresach, musisz mieć 3 kolory. Mogą być też inne przykłady, ale powinieneś o tym pomyśleć.
Jest to ćwiczenie w CLRS, w którym można usunąć szary lub czarny kolor, a algorytm działa dobrze tylko z dwoma kolorami, innymi słowy nie jest tak naprawdę potrzebny. Głównym celem oznaczania wierzchołków jest upewnienie się, że nie wpadniemy w nieskończoną pętlę poprzez wielokrotne odwiedzanie już odwiedzonych wierzchołków.
Powód zastosowania 3 kolorów w algorytmie DFS ma głównie charakter pedagogiczny: jest koncepcyjnie jaśniejszy, pomaga uczniom zobaczyć, co dzieje się podczas wykonywania dla każdego węzła.
Szary wierzchołek oznacza, że odwiedziłeś ten węzeł i przeniosłeś się do jednego z jego sąsiadów w określonej kolejności, ale może być więcej sąsiadujących wierzchołków do tego węzła. Jest to przydatne podczas cofania w celu eksploracji nieodwiedzonych wierzchołków.
Powiedzmy Vertex A ma dwóch sąsiadów B i C oraz B ma jeden sąsiad D .
zacznij od wierzchołka A, który ma biały kolor, i uczyń go szarym i przejdź do sąsiada.
Powiedzmy, że wybierając kolejność alfabetyczną, odwiedza wierzchołek B, który ma biały kolor i oznacza szary.
Następnie odwiedza D białego -> szarego D -> nigdy więcej sąsiadów. stąd znaki D-> czarny .
Teraz cofnij się do B w Grayu i już nie będziesz nieghbors. Stąd znaki B-> czarne .
Znów cofnij A na szaro i odwiedzimy znak c do c-> Szary nie ma już sąsiadów zaznacza C jako czarny
wreszcie wróć do A i zaznacz wierzchołek A jako czarny, ponieważ nie ma już białych wierzchołków i wszystkie są czarne.
W DFS klasyfikujemy krawędzie jako przednie, tylne, poprzeczne i drzewiaste.
Używamy 3 kolorów do klasyfikacji krawędzi. a kolory te reprezentują stan wierzchołka, tj. v. biały: wierzchołek v nie został jeszcze odkryty.
szary: v zostało już odkryte, ale wszystkie wierzchołki dostępne z v nie zostały jeszcze odkryte. więc wierzchołek v nadal znajduje się na stosie.
czarny: v jest już wyskakujące ze stosu. odkryte i zakończone.
Wykonując DFS, jeśli napotkasz szary wierzchołek przechodzący przez krawędź e, wówczas jest to tylna krawędź. Jeśli napotkasz czarny wierzchołek przechodzący przez krawędź e, oznacza to krawędź poprzeczną / przednią. jeśli napotkasz biały wierzchołek, wywołasz rekursywnie DFS.