Cel szarego węzła w wyszukiwaniu na głębokości pierwszego wykresu

19

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.

użytkownik6805
źródło

Odpowiedzi:

26

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 AsolsolZA,b,doZAbbdoZAdoZA, 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.bdoZAdo

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ć.

Paresh
źródło
2
+1 dobre wyjaśnienie. Czy w przypadku prostego przejścia wszystkich węzłów na grafie bezkierunkowym (np. Połączonym w moim pytaniu), SZARY i CZARNY nie mają żadnej różnicy funkcjonalnej?
user6805,
1
@ user6805 W przypadku prostego przejścia - odwiedzając każdy węzeł - zarówno skierowanego, jak i niekierowanego wykresu, nie ma funkcjonalnej różnicy między szarym a czarnym. Możesz użyć tylko dwóch kolorów (lub odwiedził / nie odwiedził). Do bardziej złożonych algorytmów potrzebne są kolory.
Paresh
Zrozumiałem to! OK, rozważ następujący przypadek: twitter.com/MaksimADmitriev/status/796995958043279361 Przechodzimy przez wykresy za pomocą DFS. Wykres po lewej stronie jest taki sam jak wykres z tej odpowiedzi i nie ma cykli. Przejrzyjmy wykres po prawej, który ma cykl. Odwiedzamy A i zaznaczamy go na szaro. Odwiedzamy B i zaznaczamy go na szaro. Odwiedzamy C i zaznaczamy go na szaro. Teraz mamy zamiar odwiedzić A, który jest już szary. Tak więc „od czerni do czerni” nie oznacza, że ​​istnieje cykl, ale „od szarości do szarości” ma. Dlatego potrzebujemy szarości. Proszę mnie poprawić, jeśli się mylę
Maksim Dmitriev
Do jeszcze bardziej złożonych celów, takich jak znalezienie silnie połączonych komponentów, konieczne może być zarejestrowanie dwa razy dla każdego węzła: przed czasem, gdy węzeł zostanie znaleziony po raz pierwszy (tj. Czas, kiedy jest zabarwiony na szaro) i po czasie, gdy węzeł jest odwiedzany (tzn. czas, kiedy ma kolor czarny). Aby zaimplementować nagrania, utrzymywany jest licznik, który zwiększa się wraz z każdym zdarzeniem.
Jan
2

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.

Kaveh
źródło
0

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.

NRK
źródło
Nie wiem, czy różnica między szarością a czernią ma tu jakiś cel ..
user6805
to musisz zrozumieć. Jeśli wierzchołek jest oznaczony jako czarny, oznacza to, że nie będzie żadnych sąsiadujących wierzchołków do tego wierzchołka. Tutaj wierzchołek D zaznaczony na czarno, ponieważ nie ma sąsiadujących wierzchołków .. gdzie szary kolor sugeruje, że jest więcej sąsiadów do odwiedzenia, a zatem przechodzisz przez nie.
NRK,
Uważam, że dzięki temu nie musisz po prostu ponownie odwiedzać węzłów, o których wiesz, że na pewno nie mają tylnych krawędzi (tj. Optymalizacji)
Setheron
0

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.

Neeraj Singh
źródło
OK, ale o co chodzi? Powiedziałeś, że biały / szary / czarny jest związany z naprzód / wstecz / krzyż / drzewo, ale nie mówisz też, po co te rzeczy są. Więc teraz jest siedem rzeczy, których pytający nie rozumie, zamiast tylko trzech!
David Richerby
Te krawędzie mogą być używane w różnych zastosowaniach DFS, podobnie jak tylne krawędzie są używane do identyfikacji pętli na wykresie, Krawędzie do przodu i poprzeczne są używane do testowania, czy istnieje unikalna ścieżka między każdą parą wierzchołków.
Neeraj Singh,