Czym są algorytmy BFS i DFS oraz kiedy wybrać każdy z nich?

BFS i DFS to algorytmy przechodzenia grafu, które systematycznie znajdują wierzchołki osiągalne z wierzchołka startowego. BFS rozszerza przeszukiwanie poziom po poziomie od najbliższych wierzchołków, dlatego jest odpowiedni, gdy potrzebujesz ścieżki o minimalnej liczbie krawędzi w grafie nieważonym. DFS podąża jedną gałęzią tak daleko, jak to możliwe, zanim się wycofa, dlatego stanowi podstawę rozwiązywania problemów takich jak analiza struktury, wykrywanie cykli i sortowanie topologiczne. Żaden z nich nie jest zawsze lepszy; wybór zależy od kryterium ścieżki i celu analizy grafu. ocw.mit.edu↗algs4.cs.princeton.edu↗

Co znajdują BFS i DFS podczas przechodzenia grafu?

Graf to struktura relacyjna złożona z wierzchołków i krawędzi. Wierzchołki reprezentują encje, takie jak osoby, miasta, strony internetowe lub zadania, natomiast krawędzie reprezentują połączenia między nimi, takie jak znajomości, drogi, odsyłacze lub relacje między wymaganiami wstępnymi. Zbiór wierzchołków oznacza się przez $V$, a zbiór krawędzi przez $E$.

Jeśli krawędzie nie mają kierunku, graf jest nieskierowany. Na przykład wzajemną znajomość można zwykle traktować jako relację dwukierunkową. Z kolei relacje takie jak obserwowanie przez A użytkownika B albo konieczność ukończenia zadania A przed zadaniem B tworzą graf skierowany. W grafie skierowanym można poruszać się wyłącznie w kierunku strzałki; nie można automatycznie przejść w przeciwnym kierunku. ocw.mit.edu↗

Najbardziej podstawowe pytanie podczas przechodzenia grafu brzmi: „Które wierzchołki można osiągnąć z punktu startowego $s$?”. Odpowiadając na to pytanie, BFS i DFS mogą też zapisywać dodatkowe informacje, takie jak to, czy wierzchołek został odwiedzony, ścieżka, którą każdy wierzchołek osiągnięto po raz pierwszy, oraz kolejność przechodzenia. Jednak przejście rozpoczynające się w jednym wierzchołku przetwarza tylko część faktycznie osiągalną z tego wierzchołka. Niekoniecznie odwiedzi każdy wierzchołek grafu. ocw.mit.edu↗

Drzewo również jest rodzajem grafu. Dlatego BFS i DFS można stosować do problemów przypominających drzewa, takich jak hierarchie folderów lub schematy organizacyjne. Należy jednak pamiętać, że ogólny graf może zawierać cykle prowadzące z powrotem do wierzchołka i wiele ścieżek do tego samego wierzchołka. Bezpośrednie zastosowanie implementacji przeznaczonej tylko do przechodzenia drzew w ogólnym grafie może powodować wielokrotne odwiedzanie tych samych wierzchołków.

Jak BFS najpierw eksploruje pobliskie wierzchołki?

BFS to skrót od Breadth-First Search, czyli przeszukiwania wszerz. Najpierw znajduje wierzchołki osiągalne z punktu startowego przez jedną krawędź, następnie przez dwie, potem przez trzy, rozszerzając zakres wyszukiwania w tej kolejności. Odległość nie oznacza tu odległości fizycznej ani kosztu; jest to liczba krawędzi, które trzeba przejść od punktu startowego. algs4.cs.princeton.edu↗

W tym celu BFS zwykle używa kolejki. Kolejka to struktura danych FIFO (First In, First Out), co oznacza, że element dodany jako pierwszy jest usuwany jako pierwszy. Umieść wierzchołek startowy w kolejce i oznacz go jako odwiedzony, a następnie usuń jeden wierzchołek z początku kolejki. Oznacz wszystkich nieodkrytych sąsiadów tego wierzchołka jako odwiedzonych i dodaj ich na koniec kolejki. Powtarzaj te kroki, aż kolejka będzie pusta. Ponieważ wcześniej odkryte pobliskie wierzchołki są przetwarzane najpierw, zachowane zostaje rozszerzanie poziom po poziomie. gh.cp-algorithms.com↗algs4.cs.princeton.edu↗

Załóżmy na przykład, że zaczynając od A, odkrywasz sąsiadów A: B i C. Gdy BFS przetwarza B, odkrywa sąsiadów B; następnie przetwarza C i odkrywa sąsiadów C. Nawet jeśli wierzchołek odkryty z B znajduje się głębiej, C, które zostało już umieszczone w kolejce na tym samym poziomie, zostanie przetworzone wcześniej lub w bliskiej kolejności. Dokładna kolejność między B i C może się różnić zależnie od kolejności przechowywania sąsiednich wierzchołków.

Kluczowe w BFS jest oznaczenie wierzchołka jako odwiedzonego natychmiast po jego odkryciu. Jeśli odłożysz oznaczenie do chwili usunięcia go z kolejki, dwa wierzchołki mogą odkryć tego samego sąsiada i umieścić go w kolejce więcej niż raz. W typowym BFS oznaczenie nowego sąsiada jako odkrytego dokładnie w chwili dodania go do kolejki jest prostsze i bezpieczniejsze.

W jakich warunkach BFS zapewnia najkrótszą ścieżkę?

BFS jest często wybierany, ponieważ w grafie nieważonym znajduje ścieżkę o minimalnej liczbie krawędzi od wierzchołka startowego do każdego osiągalnego wierzchołka. Sprawdza wszystkie wierzchołki oddalone o jeden krok od początku, zanim sprawdzi wierzchołki oddalone o dwa kroki, więc ścieżka mająca mniej krawędzi niż ścieżka, która po raz pierwszy odkrywa dany wierzchołek, nie może pojawić się później. Jeśli podczas BFS zapisujesz poprzedzający wierzchołek jako rodzica przy pierwszym odkryciu każdego wierzchołka, te wskaźniki rodzica tworzą drzewo najkrótszych ścieżek. algs4.cs.princeton.edu↗

Aby odtworzyć ścieżkę, podążaj wskaźnikami rodzica wstecz od wierzchołka docelowego do wierzchołka startowego, a następnie odwróć kolejność. Przykładowo, jeśli parent[D] = B oraz parent[B] = A, odkryta ścieżka od A do D to A → B → D. Użyj osobnego znacznika, aby wskazać, że wierzchołek startowy nie ma rodzica.

Zbyt szerokie interpretowanie słowa „najkrótsza” prowadzi jednak do błędów. BFS gwarantuje minimalną liczbę krawędzi tylko wtedy, gdy wszystkie krawędzie można traktować jako mające taki sam koszt. Jeśli drogi mają różne czasy przejazdu lub loty różne ceny, ścieżka używająca dwóch krawędzi może być tańsza lub szybsza niż ścieżka z jedną krawędzią. W takim przypadku standardowy BFS nie jest algorytmem najkrótszej ścieżki według kosztu. W zależności od właściwości wag rozważ wyspecjalizowane metody ważone, takie jak algorytm Dijkstry lub algorytm Bellmana-Forda. algs4.cs.princeton.edu↗

Dlatego BFS dobrze sprawdza się w problemach takich jak „Ile stopni znajomości dzieli dwoje przyjaciół?” lub „Ile ruchów potrzeba, aby dotrzeć do punktu na siatce, jeśli przejście o jedną komórkę w górę, w dół, w lewo lub w prawo liczy się jako jeden ruch?”. Natomiast jeśli celem jest najkrótszy czas lub najniższy koszt, najpierw sprawdź, czy wagi krawędzi są rzeczywiście równe.

Dlaczego DFS zagłębia się przed wycofaniem?

DFS to skrót od Depth-First Search, czyli przeszukiwania w głąb. Z bieżącego wierzchołka wybiera jednego nieodwiedzonego sąsiada i kontynuuje przechodzenie, aż zbada gałąź tak głęboko, jak to możliwe. Gdy dociera do ślepego zaułka, wraca do poprzedniego wierzchołka i szuka innego sąsiada, który nie został jeszcze zbadany. Ten proces powrotu nazywa się również backtrackingiem. ocw.mit.edu↗

DFS łatwo zaimplementować za pomocą wywołań rekurencyjnych. Po wejściu do wierzchołka najpierw oznacz go jako odwiedzony, a następnie wywołaj tę samą funkcję przechodzenia dla każdego nieodwiedzonego sąsiada tego wierzchołka. Gdy wywołanie rekurencyjne się kończy, sterowanie naturalnie wraca do miejsca, które je wywołało, odzwierciedlając przebieg zagłębiania się, a następnie wycofywania.

Rekurencja nie jest jedyną opcją. DFS można także zaimplementować iteracyjnie za pomocą jawnego stosu. Stos to struktura danych LIFO (Last In, First Out), co oznacza, że element dodany jako ostatni jest usuwany jako pierwszy. Usuwając najpierw ostatnio odkryty wierzchołek, można uzyskać zachowanie charakterystyczne dla przeszukiwania w głąb. W implementacji rekurencyjnej rolę tę niejawnie pełni stos wywołań programu. ocw.mit.edu↗gh.cp-algorithms.com↗

Wskaźniki rodzica utworzone przez DFS również mogą pokazać jedną ścieżkę od wierzchołka startowego do danego wierzchołka. Nie ma jednak gwarancji, że taka ścieżka będzie miała minimalną liczbę krawędzi. Ponieważ DFS podąża wybraną pierwszą gałęzią tak głęboko, jak to możliwe, może odkryć krótszą ścieżkę w innej gałęzi dopiero później. ocw.mit.edu↗

Jakie rodzaje analizy strukturalnej wykorzystują DFS?

DFS ujawnia swoją wartość, gdy analizujesz strukturę grafu, a nie tylko sprawdzasz osiągalność. Znajdowanie spójnych składowych jest reprezentatywnym przykładem. W grafie nieskierowanym jednorazowe uruchomienie DFS z dowolnego nieodwiedzonego wierzchołka znajduje jako jedną grupę wszystkie wierzchołki z nim połączone. Ponowne uruchomienie DFS z pozostałego nieodwiedzonego wierzchołka znajduje kolejną grupę.

Wykrywanie cykli to kolejne częste zastosowanie DFS. Cykl to struktura, w której podążanie krawędziami może doprowadzić z powrotem do wierzchołka startowego albo do wierzchołka już znajdującego się na bieżącej ścieżce. W grafie skierowanym można wykryć cykl, rozróżniając sytuację, w której napotykasz wierzchołek już znajdujący się na bieżącej ścieżce rekurencyjnej. Dlatego należy odróżniać wierzchołek, który został tylko kiedyś odwiedzony, od wierzchołka, który aktualnie znajduje się na ścieżce przechodzenia.

Sortowanie topologiczne porządkuje zależności skierowane, takie jak relacje wymagań wstępnych między zadaniami, w kolejność. Jest możliwe tylko w skierowanym grafie acyklicznym, czyli DAG. DAG to graf skierowany bez cyklu, który przez podążanie zgodnie z kierunkami krawędzi wraca do punktu startowego. Jeśli istnieje cykl, pojawia się sprzeczność — na przykład B musi zostać ukończone przed A, a A przed B — więc żadna kolejność liniowa nie może spełnić wszystkich krawędzi. Metoda wykorzystująca kolejność kończenia DFS stanowi jedną z podstaw sortowania topologicznego. algs4.cs.princeton.edu↗

Znajdowanie silnie spójnych składowych jest również ważnym zagadnieniem opartym na DFS. Silnie spójna składowa to zbiór wierzchołków w grafie skierowanym, w którym dowolne dwa wierzchołki z tej samej grupy mogą się wzajemnie osiągnąć. Problem ten nie jest jednak rozwiązywany jednym prostym DFS; wymaga konstrukcji algorytmicznej wykorzystującej kolejność przechodzenia i kierunki krawędzi. algs4.cs.princeton.edu↗

Jakie problemy występują bez znaczników odwiedzenia?

W ogólnym grafie tablica lub zbiór odwiedzonych wierzchołków nie jest opcjonalny; jest niezbędny dla zakończenia działania i poprawności. Jeśli na przykład A i B są połączone, możesz przejść z A do B, a potem z B z powrotem do A. Bez sprawdzania stanu odwiedzenia DFS może rekurencyjnie przełączać się między A i B w nieskończoność, a BFS może wielokrotnie umieszczać ten sam wierzchołek w kolejce. ocw.mit.edu↗

Termin „odwiedzony” może być nieco inaczej podzielony zależnie od implementacji. W BFS wierzchołek jest zwykle oznaczany jako „odkryty” w chwili dodania go do kolejki. W DFS często oznacza się wierzchołek jako odwiedzony bezpośrednio po wejściu do jego funkcji. Bardziej zaawansowana analiza grafów skierowanych może rozróżniać stan nieodwiedzony, stan aktualnie eksplorowany oraz stan zakończony.

Zasada odwiedzania każdego wierzchołka tylko raz jest bezpośrednio związana z wydajnością przechodzenia. Jeśli nie rozwijasz wierzchołków, które zostały już przetworzone, to przy listach sąsiedztwa sprawdzasz każdy wierzchołek i każdą krawędź tylko ograniczoną liczbę razy. Ponadto, jeśli przypisujesz wskaźnik rodzica wyłącznie przy pierwszym odkryciu wierzchołka, jest jasne, która ścieżka odkryła ten wierzchołek jako pierwsza.

Aby przejść cały graf, potrzebujesz zewnętrznej pętli. Badaj kolejno każdy wierzchołek, a gdy znajdziesz taki, który nie został jeszcze odwiedzony, rozpocznij z niego nowy BFS lub DFS. W grafie nieskierowanym daje to przechodzenie według spójnych składowych. W grafie skierowanym kolejno przetwarza obszary osiągalne w wybranych kierunkach krawędzi. ocw.mit.edu↗

Dlaczego złożoność czasowa zależy od reprezentacji grafu?

Złożoność czasową BFS i DFS często podaje się jako $O(\lvert V \rvert + \lvert E \rvert)$. Jest to standardowa analiza przy użyciu list sąsiedztwa. Lista sąsiedztwa przechowuje dla każdego wierzchołka listę jego bezpośrednio połączonych sąsiadów. Ze znacznikami odwiedzenia każdy wierzchołek jest przetwarzany raz, a krawędzie są sprawdzane podczas skanowania list sąsiadów, więc całkowita praca jest proporcjonalna do liczby wierzchołków plus liczby krawędzi. ocw.mit.edu↗

Dodatkowa pamięć ma zwykle złożoność $O(\lvert V \rvert)$. Obejmuje ona tablicę odwiedzin, tablicę rodziców oraz kolejkę BFS albo stos DFS. W rekurencyjnym DFS dodatkowa pamięć obejmuje także stos wywołań wymagany przez głębokość rekurencji. Warto rozróżniać przestrzeń używaną do przechowywania samego grafu od dodatkowej przestrzeni używanej przez algorytm przechodzenia. ocw.mit.edu↗

Macierz sąsiedztwa przechowuje informację o istnieniu krawędzi dla każdej pary wierzchołków w tabeli. Aby znaleźć sąsiadów wierzchołka, może być konieczne sprawdzenie każdego możliwego wierzchołka. Dlatego BFS lub DFS używający macierzy sąsiedztwa może zwykle wymagać czasu $O(\lvert V \rvert^2)$. W przypadku grafów rzadkich, mających niewiele krawędzi, listy sąsiedztwa są szczególnie wydajne, ponieważ skanują tylko faktycznie połączonych sąsiadów. ocw.mit.edu↗

Notacja złożoności opisuje, jak zużycie zasobów ma tendencję do wzrostu wraz ze wzrostem rozmiaru danych wejściowych. Na rzeczywisty czas działania wpływają również identyfikatory wierzchołków, implementacja list sąsiedztwa, układ pamięci oraz rozmiar części osiągalnej z punktu startowego przechodzenia. Mimo to przy wyborze algorytmu rozsądnie jest najpierw sprawdzić, czy graf jest rzadki i jak jest reprezentowany.

Czy rzeczywista kolejność odwiedzania w BFS lub DFS jest ustalona?

Nie. BFS przestrzega zasady przetwarzania najpierw bliższych poziomów, a DFS zasady głębokiej eksploracji bieżącej gałęzi, ale to, który wierzchołek zostanie odwiedzony jako pierwszy na tym samym poziomie albo która gałąź zostanie zbadana najpierw spośród kilku sąsiadów, zależy od kolejności przechowywania sąsiednich wierzchołków. gh.cp-algorithms.com↗gh.cp-algorithms.com↗

Na przykład, jeśli lista sąsiadów A ma kolejność B, C, BFS zwykle najpierw odkryje B. Jeśli kolejność listy zostanie zmieniona na C, B, C może zostać odkryte jako pierwsze. Ta różnica może mieć większy wpływ w DFS. Jeśli zmieni się pierwszy wybrany sąsiad, zmieni się sama głęboko eksplorowana gałąź, a wraz z nią drzewo przechodzenia oraz ścieżki DFS utworzone za pomocą wskaźników rodzica.

Fakt ten ma znaczenie przy ocenie wyniku algorytmu. Jeśli problem wymaga „leksykograficznie pierwszej kolejności odwiedzania”, musisz posortować listy sąsiedztwa lub określić regułę priorytetu. Natomiast jeśli potrzebujesz tylko osiągalności, liczby spójnych składowych albo minimalnych odległości w liczbie krawędzi, szczegółowa kolejność na tym samym poziomie lub głębokości może nie być kluczowa dla wyniku.

W szczególności przy iteracyjnej implementacji DFS ze stosem kolejność dodawania sąsiadów na stos może być odwrotna do kolejności ich faktycznego zdejmowania. Jeśli chcesz uzyskać tę samą kolejność odwiedzania co w implementacji rekurencyjnej korzystającej z danej kolejności listy sąsiedztwa, musisz celowo dostosować kierunek dodawania sąsiadów na stos. Nie jest to inna definicja DFS; to różnica implementacyjna wynikająca z zachowania LIFO.

Jakie są częste nieporozumienia i błędy?

Pierwszym jest błędne przekonanie, że BFS rozwiązuje każdy rodzaj problemu najkrótszej ścieżki. Jak omówiono wcześniej, BFS gwarantuje minimalną liczbę krawędzi w grafie nieważonym. Jeśli wagi się różnią, jeden ruch nie musi mieć tej samej wartości co inny, więc zmienia się sam model problemu. algs4.cs.princeton.edu↗algs4.cs.princeton.edu↗

Drugim jest założenie, że DFS zawsze używa mniej pamięci niż BFS. Uwzględniając tablice odwiedzin i stan przechodzenia, oba algorytmy mogą ogólnie używać $O(\lvert V \rvert)$ dodatkowej pamięci. Maksymalny rozmiar kolejki lub stosu może być różny dla konkretnych kształtów grafów i implementacji, ale sama złożoność asymptotyczna nie ustanawia bezwarunkowej przewagi żadnego z nich. ocw.mit.edu↗

Trzecim jest przekonanie, że rekurencyjny DFS jest bezpieczny dla każdego wejścia. W grafie o bardzo dużej głębokości głębokość rekurencji także staje się duża. Należy uwzględnić limit stosu wywołań języka i środowiska wykonawczego; w takich przypadkach praktyczniejsza może być implementacja iteracyjna z jawnym stosem. Ważne jest również zrozumienie, że rekurencyjny stos wywołań jest częścią dodatkowej pamięci DFS. ocw.mit.edu↗

Czwartym jest traktowanie grafu skierowanego tak, jakby był nieskierowany. Istnienie krawędzi od A do B nie oznacza, że można przejść z B do A. Podczas przechowywania danych wejściowych na listach sąsiedztwa graf nieskierowany zwykle dodaje krawędź do list obu wierzchołków, podczas gdy graf skierowany dodaje ją tylko do listy wierzchołka źródłowego. Ta różnica zmienia znaczenie osiągalności, spójności i cykli. ocw.mit.edu↗

Piątym jest mylenie wyniku przechodzenia z jedyną poprawną ścieżką. Gdy kilka ścieżek ma tę samą minimalną liczbę krawędzi, BFS zapisuje jedną z nich za pomocą wskaźników rodzica. DFS również może tworzyć różne ścieżki zależnie od kolejności sąsiadów. Jeśli sama ścieżka wymaga priorytetu, w problemie trzeba określić reguły sortowania lub dodatkowe warunki.

Jakich kryteriów użyć przy wyborze algorytmu do problemu?

Najlepiej najpierw ująć cel w słowa. Jeśli pytanie brzmi jedynie: „Czy można to osiągnąć z punktu startowego?”, możliwe są zarówno BFS, jak i DFS, a wyboru możesz dokonać na podstawie środowiska implementacji i analizy potrzebnej później. Jeśli potrzebujesz minimalnej liczby krawędzi, na przykład „Ile identycznych ruchów potrzeba, aby dotrzeć na miejsce?”, BFS jest naturalnym wyborem. Jeśli musisz podążać ścieżką głęboko podczas analizy struktury albo istotny jest moment powrotu, prawdopodobnie odpowiedni będzie DFS.

Następnie sprawdź, co oznaczają krawędzie. Ustal, czy każdy ruch ma taki sam koszt, czy też występują wagi, takie jak czas, odległość lub koszt. Jeśli wagi istnieją, nie stosuj bezpośrednio własności BFS dotyczącej najkrótszej ścieżki. Sprawdź też z wyprzedzeniem, czy graf jest skierowany, czy mogą występować cykle oraz czy musisz zbadać cały graf. ocw.mit.edu↗algs4.cs.princeton.edu↗

Kryteria wyboru można podsumować następująco.

Na koniec weź pod uwagę rozmiar danych wejściowych i reprezentację. W przypadku grafu rzadkiego listy sąsiedztwa oraz standardowa analiza $O(\lvert V \rvert + \lvert E \rvert)$ dla BFS i DFS są dobrym wyborem. W środowiskach, w których głębokość rekurencji może stanowić problem, rozważ iteracyjny DFS. Jeśli kolejność odwiedzania wpływa na ocenę lub reguły biznesowe, kolejność na listach sąsiedztwa również jest częścią projektu.

Wniosek: cele i warunki przechodzenia są ważniejsze niż nazwy

BFS i DFS to różne strategie dokładnego przechodzenia grafu. BFS używa kolejki, aby rozszerzać przeszukiwanie od pobliskich wierzchołków, i ma tę zaletę, że zapewnia ścieżki o minimalnej liczbie krawędzi w grafach nieważonych. DFS używa rekurencji lub stosu, aby głęboko eksplorować jedną gałąź i się wycofywać, stanowiąc podstawę wielu metod operujących na strukturze grafu, w tym znajdowania spójnych składowych, cykli oraz sortowania topologicznego w DAG. ocw.mit.edu↗algs4.cs.princeton.edu↗

Oba wymagają znaczników odwiedzenia i przy użyciu list sąsiedztwa mają zwykle tę samą asymptotyczną złożoność czasową. Kluczem do wyboru między nimi nie jest zatem pojedyncza etykieta, taka jak szybkość, lecz to, co definiuje najkrótszą ścieżkę, czy krawędzie są ważone, jak należy interpretować kierunek i cykle oraz czy trzeba przetworzyć cały graf. Rozróżnienie tych warunków najpierw pozwala użyć BFS i DFS do właściwego celu.