Dlaczego DFS, a nie BFS do znajdowania cyklu na wykresach

Przeważnie DFS służy do znajdowania cyklu na wykresach, a nie BFS. Jakieś powody? Oba mogą sprawdzić, czy węzeł został już odwiedzony podczas przeglądania drzewa / wykresu.

Przeszukiwanie wgłębne jest bardziej wydajne w pamięci niż przeszukiwanie wszerz, ponieważ możesz cofnąć się wcześniej. Jest również łatwiejsze do zaimplementowania, jeśli używasz stosu wywołań, ale zależy to od najdłuższej ścieżki, która nie przepełnia stosu.

Również jeśli twój wykres jest ukierunkowany , musisz nie tylko pamiętać, czy odwiedziłeś węzeł, czy nie, ale także, jak się tam dostałeś. W przeciwnym razie możesz pomyśleć, że znalazłeś cykl, ale w rzeczywistości masz tylko dwie oddzielne ścieżki A-> B, ale to nie znaczy, że istnieje ścieżka B-> A. Na przykład,

Jeśli zrobisz BFS zaczynając od 0, wykryje, że cykl jest obecny, ale w rzeczywistości nie ma cyklu.

Dzięki wyszukiwaniu wgłębnemu możesz oznaczyć węzły jako odwiedzone podczas schodzenia i odznaczyć je podczas cofania. Zobacz komentarze dotyczące poprawy wydajności tego algorytmu.

Aby uzyskać najlepszy algorytm wykrywania cykli na grafie skierowanym, możesz spojrzeć na algorytm Tarjana .

1. DFS jest łatwiejszy do wdrożenia
2. Gdy DFS znajdzie cykl, stos będzie zawierał węzły tworzące cykl. To samo nie dotyczy BFS, więc musisz wykonać dodatkową pracę, jeśli chcesz również wydrukować znaleziony cykl. To sprawia, że ​​DFS jest znacznie wygodniejszy.

BFS może być rozsądny, jeśli wykres nie jest ukierunkowany (bądź moim gościem w pokazaniu wydajnego algorytmu wykorzystującego BFS, który raportowałby cykle w ukierunkowanym wykresie!), Gdzie każda „krawędź poprzeczna” definiuje cykl. Jeśli krawędź poprzeczna jest {v1, v2}, a korzeń (w drzewie BFS), który zawiera te węzły r, to cykl jest r ~ v1 - v2 ~ r( ~jest to ścieżka, -pojedyncza krawędź), co można raportować prawie tak łatwo, jak w DFS.

Jedynym powodem korzystania z BFS byłoby to, gdybyś wiedział, że twój (niekierowany) wykres będzie miał długie ścieżki i małe pokrycie ścieżek (innymi słowy, głębokie i wąskie). W takim przypadku BFS wymagałby proporcjonalnie mniej pamięci dla swojej kolejki niż stos DFS (oba oczywiście nadal liniowe).

We wszystkich innych przypadkach wyraźnie wygrywa DFS. Działa zarówno na wykresach ukierunkowanych, jak i nieukierunkowanych, a raportowanie cykli jest trywialne - po prostu połącz dowolną tylną krawędź do ścieżki od przodka do potomka, a otrzymasz cykl. Podsumowując, znacznie lepsze i praktyczne niż BFS dla tego problemu.

BFS nie będzie działać dla ukierunkowanego wykresu w znajdowaniu cykli. Rozważmy A-> B i A-> C-> B jako ścieżki od A do B na wykresie. BFS powie, że po przejściu jednej ze ścieżek, którą odwiedza B. Kontynuując podróż następną ścieżką, powie, że zaznaczony węzeł B został ponownie znaleziony, a zatem istnieje cykl. Najwyraźniej nie ma tu cyklu.

Nie wiem, dlaczego w moim kanale pojawiło się takie stare pytanie, ale wszystkie poprzednie odpowiedzi są złe, więc ...

DFS służy do znajdowania cykli w ukierunkowanych wykresach, ponieważ działa .

W DFS każdy wierzchołek jest „odwiedzany”, gdzie odwiedzanie wierzchołka oznacza:

1. Wierzchołek zostaje uruchomiony

2. Odwiedzany jest podgraf dostępny z tego wierzchołka. Obejmuje to śledzenie wszystkich nieoznaczonych krawędzi, które są dostępne z tego wierzchołka, i odwiedzanie wszystkich osiągalnych nieodwiedzonych wierzchołków.

3. Wierzchołek jest gotowy.

Krytyczną cechą jest to, że wszystkie krawędzie osiągalne z wierzchołka są śledzone przed zakończeniem wierzchołka. Jest to funkcja DFS, ale nie BFS. W rzeczywistości jest to definicja DFS.

Dzięki tej funkcji wiemy, że po uruchomieniu pierwszego wierzchołka w cyklu:

1. Żadna z krawędzi cyklu nie została prześledzona. Wiemy o tym, ponieważ można się do nich dostać tylko z innego wierzchołka w cyklu, a mówimy o pierwszym wierzchołku, który ma zostać uruchomiony.
2. Wszystkie untraced krawędzie osiągalny z tego wierzchołka będą śledzone przed jego zakończeniem, i że obejmuje wszystkie krawędzie w cyklu, ponieważ żaden z nich nie został jeszcze prześledzić. Dlatego jeśli istnieje cykl, znajdziemy krawędź z powrotem do pierwszego wierzchołka po jego rozpoczęciu, ale przed zakończeniem; i
3. Ponieważ wszystkie nakreślone krawędzie są osiągalne z każdego rozpoczętego, ale nieukończonego wierzchołka, znalezienie krawędzi do takiego wierzchołka zawsze wskazuje na cykl.

Tak więc, jeśli istnieje cykl, to mamy gwarancję znalezienia krawędzi do rozpoczętego, ale niedokończonego wierzchołka (2), a jeśli znajdziemy taką krawędź, to mamy gwarancję, że istnieje cykl (3).

Dlatego DFS jest używany do znajdowania cykli w ukierunkowanych wykresach.

BFS nie daje takich gwarancji, więc po prostu nie działa. (niezależnie od doskonale dobrych algorytmów wyszukiwania cykli, które obejmują BFS lub podobne jako podprocedura)

Z drugiej strony wykres nieukierunkowany ma cykl, gdy istnieją dwie ścieżki między dowolną parą wierzchołków, tj. Gdy nie jest to drzewo. Jest to łatwe do wykrycia podczas BFS lub DFS - krawędzie śledzone do nowych wierzchołków tworzą drzewo, a każda inna krawędź wskazuje cykl.

Jeśli umieścisz cykl w losowym miejscu na drzewie, DFS będzie miał tendencję do trafiania w cykl, gdy pokryje około połowę drzewa, i połowę czasu, gdy już przeszedł tam, gdzie przebiega cykl, a połowę czasu nie ( i znajdzie go średnio w połowie reszty drzewa), więc oszacuje średnio około 0,5 * 0,5 + 0,5 * 0,75 = 0,625 drzewa.

Jeśli umieścisz cykl w losowym miejscu na drzewie, BFS będzie miał tendencję do uderzania w cykl tylko wtedy, gdy oceni warstwę drzewa na tej głębokości. W związku z tym zwykle trzeba ocenić liście drzewa binarnego równowagi, co generalnie skutkuje oceną większej części drzewa. W szczególności w 3/4 czasu co najmniej jedno z dwóch ogniw pojawia się w liściach drzewa i w tych przypadkach trzeba ocenić średnio 3/4 drzewa (jeśli jest jedno łącze) lub 7 / 8 drzewa (jeśli są dwa), więc możesz już oczekiwać wyszukiwania 1/2 * 3/4 ​​+ 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = 0.656 ... drzewa bez dodawania nawet kosztu przeszukiwania drzewa z dodanym cyklem z dala od węzłów liści.

Ponadto DFS jest łatwiejszy do wdrożenia niż BFS. Więc to jest ten, którego należy użyć, chyba że wiesz coś o swoich cyklach (np. Cykle prawdopodobnie znajdują się blisko korzenia, z którego szukasz, w którym momencie BFS daje ci przewagę).

Aby udowodnić, że wykres jest cykliczny, wystarczy udowodnić, że ma jeden cykl (krawędź skierowana do siebie bezpośrednio lub pośrednio).

W DFS bierzemy jeden wierzchołek na raz i sprawdzamy, czy ma cykl. Po znalezieniu cyklu możemy pominąć sprawdzanie innych wierzchołków.

W BFS musimy śledzić wiele krawędzi wierzchołków jednocześnie i najczęściej na końcu dowiadujesz się, czy ma cykl. Wraz ze wzrostem rozmiaru wykresu BFS wymaga więcej miejsca, obliczeń i czasu w porównaniu do DFS.

To w pewnym sensie zależy od tego, czy mówisz o implementacjach rekurencyjnych, czy iteracyjnych.

Recursive-DFS odwiedza każdy węzeł dwukrotnie. Iteracyjny-BFS odwiedza każdy węzeł raz.

Jeśli chcesz wykryć cykl, musisz zbadać węzły zarówno przed, jak i po dodaniu ich przylegania - zarówno po „uruchomieniu” w węźle, jak i po „zakończeniu” na węźle.

Wymaga to więcej pracy w Iterative-BFS, więc większość ludzi wybiera Recursive-DFS.

Zauważ, że prosta implementacja Iterative-DFS z, powiedzmy, std :: stack ma ten sam problem, co Iterative-BFS. W takim przypadku musisz umieścić fikcyjne elementy na stosie, aby śledzić „zakończenie” pracy nad węzłem.

Zobacz tę odpowiedź, aby uzyskać więcej informacji na temat tego, jak Iterative-DFS wymaga dodatkowej pracy, aby określić, kiedy „zakończysz” pracę z węzłem (odpowiedź w kontekście TopoSort):

Sortowanie topologiczne przy użyciu DFS bez rekursji

Mamy nadzieję, że to wyjaśnia, dlaczego ludzie preferują rekurencyjny system plików DFS w przypadku problemów, w których trzeba określić, kiedy „kończy się” przetwarzanie węzła.

Będziesz musiał użyć BFS gdy chcesz znaleźć najkrótszy cykl zawierający dany węzeł na skierowanym wykresie.

Na przykład:

Jeśli dany węzeł ma wartość 2, istnieją trzy cykle, w których jest częścią - [2,3,4], [2,3,4,5,6,7,8,9]&[2,5,6,7,8,9] . Najkrótsza jest[2,3,4]

Aby zrealizować to za pomocą BFS, musisz jawnie utrzymywać historię odwiedzanych węzłów przy użyciu odpowiednich struktur danych.

Ale dla wszystkich innych celów (np. Aby znaleźć jakąkolwiek ścieżkę cykliczną lub sprawdzić, czy cykl istnieje, czy nie), DFSjest to oczywisty wybór z powodów wymienionych przez innych.