Graf oraz przeszukiwanie wszerz i w głąb

Podcast

Algorytmy Przeszukiwania Grafów: BFS i DFS0:00 / 11:51

0:001:00 pozostało

1x

Grafy stanowią fundamentalną strukturę danych w informatyce, pozwalającą modelować złożone relacje między obiektami. Zrozumienie, jak je przeszukiwać, jest kluczowe dla wielu algorytmów i aplikacji. Ten artykuł wyjaśnia podstawy grafów oraz przedstawia dwie najważniejsze techniki przeszukiwania: przeszukiwanie wszerz (BFS) i przeszukiwanie w głąb (DFS), które studenci informatyki i nie tylko muszą opanować.

Czym jest graf i jak go reprezentować?

Graf to zbiór wierzchołków (obiektów) połączonych krawędziami (relacjami). Służy do modelowania różnorodnych problemów, od sieci społecznościowych po mapy drogowe.

Rodzaje grafów

• Graf nieskierowany: Krawędzie nie mają określonego kierunku (np. przyjaźń). Krawędź (A, B) jest taka sama jak (B, A).
• Graf skierowany (digraf): Krawędzie mają kierunek (np. jednokierunkowa ulica). Krawędź (A, B) pozwala na przejście z A do B, ale niekoniecznie z B do A.
• Graf ważony: Krawędzie posiadają wartości liczbowe (wagi), np. odległość, koszt.
• Graf nieważony: Krawędzie nie mają przypisanych wag; wszystkie są traktowane jednakowo.

Jak przechowywać grafy? Reprezentacja grafu

Aby algorytmy mogły przetwarzać grafy, muszą być one odpowiednio zapisane w pamięci komputera. Istnieją dwie główne metody:

1. Macierz sąsiedztwa (Adjacency Matrix):

• Dwuwymiarowa tablica V × V, gdzie V to liczba wierzchołków. macierz[i][j] wynosi 1 (lub wagę krawędzi), jeśli istnieje krawędź z i do j, i 0 (lub nieskończoność), jeśli nie.
• Zalety: Szybkie sprawdzanie istnienia krawędzi (O(1)), łatwa implementacja, dobra dla grafów gęstych.
• Wady: Duże zużycie pamięci (O(V²)), nawet dla grafów rzadkich. Iterowanie po sąsiadach wierzchołka to O(V).

2. Lista sąsiedztwa (Adjacency List):

• Tablica list, gdzie każdy indeks i zawiera listę wierzchołków połączonych z i.
• Zalety: Efektywna pamięciowo dla grafów rzadkich (O(V + E), gdzie E to liczba krawędzi). Łatwe iterowanie po sąsiadach (czas proporcjonalny do ich liczby).
• Wady: Sprawdzanie istnienia krawędzi wymaga przeszukania listy sąsiedztwa (O(stopień wierzchołka)).

Wybór metody zależy od charakterystyki grafu i najczęściej wykonywanych operacji.

Przeszukiwanie wszerz (BFS) w grafie: warstwa po warstwie

Algorytm przeszukiwania wszerz (BFS – Breadth-First Search) rozpoczyna od wierzchołka startowego i odwiedza wszystkie jego bezpośrednie sąsiady, potem sąsiadów tych sąsiadów i tak dalej, poruszając się warstwami. To jak rozchodząca się fala.

Jak działa BFS? Kroki algorytmu

BFS wykorzystuje kolejkę (FIFO – First In, First Out) do przechowywania wierzchołków do odwiedzenia. Kluczowe kroki to:

1. Utwórz pustą kolejkę i dodaj do niej wierzchołek początkowy s.
2. Oznacz wierzchołek s jako odwiedzony.
3. Dopóki kolejka nie jest pusta: a. Pobierz wierzchołek u z początku kolejki. b. Dla każdego nieodwiedzonego sąsiada v wierzchołka u: i. Oznacz v jako odwiedzony. ii. Dodaj v do kolejki. iii. Jeśli celem jest znalezienie najkrótszej ścieżki, zapisz, że u jest poprzednikiem v.

Zastosowania i złożoność BFS

Najważniejszym zastosowaniem BFS jest znajdowanie najkrótszej ścieżki w grafie nieważonym (mierzonej liczbą krawędzi) od wierzchołka początkowego do wszystkich innych osiągalnych wierzchołków. Dzieje się tak, ponieważ BFS zawsze eksploruje graf w kolejności rosnącej odległości od wierzchołka startowego.

Złożoność obliczeniowa BFS dla listy sąsiedztwa wynosi O(V + E), gdzie V to liczba wierzchołków, a E to liczba krawędzi. Dla macierzy sąsiedztwa złożoność wynosi O(V²).

Przykład działania BFS krok po kroku

Rozważmy graf nieskierowany z wierzchołkami {A, B, C, D, E, F} i krawędziami: (A,B), (A,C), (B,D), (C,E), (D,F), (E,F). Startujemy z wierzchołka A:

1. Kolejka: [A]. Odwiedzone: {A}.
2. Pobierz A. Sąsiedzi A: B, C.

• Dodaj B do kolejki. Odwiedzone: {A, B}.
• Dodaj C do kolejki. Odwiedzone: {A, B, C}. Kolejka: [B, C].

3. Pobierz B. Sąsiedzi B: A (odwiedzone), D.

• Dodaj D do kolejki. Odwiedzone: {A, B, C, D}. Kolejka: [C, D].

4. Pobierz C. Sąsiedzi C: A (odwiedzone), E.

• Dodaj E do kolejki. Odwiedzone: {A, B, C, D, E}. Kolejka: [D, E].

5. Pobierz D. Sąsiedzi D: B (odwiedzone), F.

• Dodaj F do kolejki. Odwiedzone: {A, B, C, D, E, F}. Kolejka: [E, F].

6. Pobierz E. Sąsiedzi E: C (odwiedzone), F (odwiedzone). Kolejka: [F].
7. Pobierz F. Sąsiedzi F: D (odwiedzone), E (odwiedzone). Kolejka: [].

Kolejność odwiedzania wierzchołków: A, B, C, D, E, F.

Znajdowanie najkrótszej ścieżki za pomocą BFS

BFS jest idealny do znajdowania najkrótszej ścieżki w grafach nieważonych, ponieważ eksploruje graf warstwami. Aby odtworzyć ścieżkę, podczas działania BFS należy przechowywać informację o poprzedniku każdego wierzchołka. Gdy algorytm się zakończy, można odtworzyć ścieżkę od wierzchołka docelowego do źródłowego, cofając się po poprzednikach.

Przykład odtworzenia ścieżki do F z BFS (start A):

• odległość[E]=2, poprzednik[E]=C.
• odległość[D]=2, poprzednik[D]=B.
• odległość[F]=3, poprzednik[F]=D.

Ścieżka do F:

• F ma poprzednika D.
• D ma poprzednika B.
• B ma poprzednika A.

Ostatecznie ścieżka to A → B → D → F. Długość ścieżki to 3 krawędzie (odległość[F] = 3).

Przeszukiwanie w głąb (DFS) w grafie: eksploracja do końca

Algorytm przeszukiwania w głąb (DFS – Depth-First Search) rozpoczyna od wierzchołka początkowego i eksploruje tak daleko, jak to możliwe, wzdłuż jednej gałęzi, zanim się cofnie. To jak poruszanie się po labiryncie, idąc jedną drogą do końca, a po ślepej uliczce, cofając się do ostatniego rozwidlenia i próbując inną ścieżkę.

Jak działa DFS? Kroki algorytmu

DFS wykorzystuje stos (LIFO – Last In, First Out) lub rekurencję (która wewnętrznie używa stosu wywołań) do przechowywania wierzchołków do odwiedzenia.

Wersja iteracyjna z użyciem stosu:

1. Utwórz pusty stos i dodaj do niego wierzchołek początkowy s.
2. Dopóki stos nie jest pusty: a. Pobierz wierzchołek u ze szczytu stosu. b. Jeśli u nie został jeszcze odwiedzony: i. Oznacz u jako odwiedzony. ii. Dla każdego nieodwiedzonego sąsiada v wierzchołka u (w dowolnej kolejności):

• Dodaj v do stosu.

Wersja rekurencyjna:

1. Funkcja DFS(u): a. Oznacz u jako odwiedzony. b. Dla każdego nieodwiedzonego sąsiada v wierzchołka u: i. Wywołaj DFS(v).

Zastosowania i złożoność DFS

DFS jest używany do wykrywania cykli w grafach, znajdowania spójnych składowych, sortowania topologicznego (dla grafów skierowanych acyklicznych), rozwiązywania problemów z labiryntami oraz w algorytmach związanych z przeszukiwaniem drzew.

Złożoność obliczeniowa DFS, podobnie jak BFS, dla listy sąsiedztwa wynosi O(V + E). Dla macierzy sąsiedztwa złożoność to O(V²).

Przykład działania DFS krok po kroku

Użyjmy tego samego grafu {A, B, C, D, E, F} i krawędzi. Startujemy z wierzchołka A:

1. Stos: [A]. Odwiedzone: {}.
2. Pobierz A. A nieodwiedzone. Oznacz A. Odwiedzone: {A}. Sąsiedzi A: B, C. Dodaj C, potem B do stosu (kolejność może się różnić). Stos: [C, B].
3. Pobierz B. B nieodwiedzone. Oznacz B. Odwiedzone: {A, B}. Sąsiedzi B: A (odwiedzone), D. Dodaj D. Stos: [C, D].
4. Pobierz D. D nieodwiedzone. Oznacz D. Odwiedzone: {A, B, D}. Sąsiedzi D: B (odwiedzone), F. Dodaj F. Stos: [C, F].
5. Pobierz F. F nieodwiedzone. Oznacz F. Odwiedzone: {A, B, D, F}. Sąsiedzi F: D (odwiedzone), E. Dodaj E. Stos: [C, E].
6. Pobierz E. E nieodwiedzone. Oznacz E. Odwiedzone: {A, B, D, F, E}. Sąsiedzi E: C, F (odwiedzone). Dodaj C. Stos: [C, C].
7. Pobierz C. C nieodwiedzone. Oznacz C. Odwiedzone: {A, B, D, F, E, C}. Sąsiedzi C: A (odwiedzone), E (odwiedzone). Stos: [C].
8. Pobierz C. C jest już odwiedzone. Pomiń. Stos: [].

Kolejność odwiedzania wierzchołków (pierwsze odwiedzenie): A, B, D, F, E, C. Zauważ, że kolejność jest inna niż w BFS, co pokazuje fundamentalne różnice w ich strategiach.

Porównanie BFS i DFS: kluczowe różnice

Chociaż oba algorytmy służą do przeszukiwania grafów, ich strategie i zastosowania znacząco się różnią:

Typowe błędy i pułapki podczas implementacji grafów

Podczas pracy z algorytmami grafowymi łatwo o błędy, które mogą prowadzić do niepoprawnych wyników lub zwiększonej złożoności:

• Zapominanie o oznaczaniu wierzchołków jako odwiedzonych: Bez prawidłowego oznaczania algorytm może wpaść w nieskończoną pętlę w grafach z cyklami lub wielokrotnie przetwarzać te same wierzchołki.
• Niewłaściwe użycie struktur danych: Użycie stosu zamiast kolejki dla BFS lub odwrotnie sprawi, że algorytm nie będzie działał zgodnie z przeznaczeniem (np. DFS nie znajdzie najkrótszej ścieżki w grafie nieważonym).
• Błędne założenia dotyczące najkrótszej ścieżki: BFS znajduje najkrótszą ścieżkę tylko w grafach nieważonych. Dla grafów ważonych potrzebne są algorytmy takie jak algorytm Dijkstry czy Bellmana-Forda.
• Niezrozumienie złożoności: Mylenie złożoności O(V + E) dla listy sąsiedztwa ze złożonością O(V²) dla macierzy sąsiedztwa. Wybór reprezentacji grafu jest kluczowy dla efektywności.

Symulacje algorytmów przeszukiwania grafów: nauka przez doświadczenie

Interaktywna symulacja algorytmów przeszukiwania grafów to nieocenione narzędzie dla studentów. Pozwala ona na głębsze zrozumienie ich działania krok po kroku. Użytkownik może:

• Tworzyć własne grafy: Dodawać/usuwać wierzchołki i krawędzie, zmieniać ich kierunek i wagi.
• Wybierać wierzchołek startowy: Obserwować wpływ na kolejność odwiedzania.
• Krok po kroku wykonywać BFS i DFS: Wizualizować stan kolejki/stosu, podświetlać przetwarzane wierzchołki i ich sąsiadów, śledząc logikę algorytmu.
• Obserwować różnice w kolejności odwiedzania: Porównywać, jak BFS i DFS eksplorują ten sam graf.
• Wizualizować najkrótszą ścieżkę: W przypadku BFS, zobaczyć, jak algorytm odkrywa najkrótsze ścieżki i odtworzyć je do wybranego wierzchołka docelowego.
• Analizować złożoność: Chociaż symulacja nie pokaże O(V+E) wprost, wizualizacja operacji da intuicyjne zrozumienie efektywności algorytmów dla grafów rzadkich.

Eksperymentowanie z różnymi konfiguracjami grafów (gęste, rzadkie, z cyklami, bez cykli) i obserwowanie, jak algorytmy sobie radzą, to najlepszy sposób na utrwalenie wiedzy teoretycznej i rozwinięcie intuicji algorytmicznej.

FAQ: Najczęściej zadawane pytania studentów o grafy i przeszukiwanie

Jakie są główne różnice między BFS a DFS?

Kluczową różnicą jest strategia przeszukiwania: BFS eksploruje graf warstwami (najpierw najbliższe wierzchołki), używając kolejki, podczas gdy DFS idzie w głąb każdej ścieżki, zanim się cofnie, używając stosu lub rekurencji.

Kiedy powinienem użyć BFS, a kiedy DFS?

Użyj BFS, gdy potrzebujesz znaleźć najkrótszą ścieżkę w grafie nieważonym lub chcesz odwiedzić wierzchołki w kolejności ich odległości od źródła. Użyj DFS do wykrywania cykli, sortowania topologicznego, znajdowania spójnych składowych, czy rozwiązywania problemów typu labirynt.

Czy BFS działa dla grafów ważonych?

Nie, BFS nie znajduje najkrótszej ścieżki w grafach ważonych, chyba że wszystkie wagi są równe. Dla grafów ważonych należy użyć algorytmów takich jak algorytm Dijkstry, który uwzględnia wagi krawędzi.

Czym jest złożoność obliczeniowa O(V+E)?

Złożoność O(V+E) oznacza, że czas działania algorytmu jest proporcjonalny do sumy liczby wierzchołków (V) i liczby krawędzi (E) w grafie. Jest to efektywna złożoność dla grafów reprezentowanych listą sąsiedztwa, ponieważ każdy wierzchołek i każda krawędź są przetwarzane stałą liczbę razy.

Czy rekurencja w DFS jest lepsza od stosu?

Obie metody (rekurencja i stos iteracyjny) są równoważne, ponieważ rekurencja wewnętrznie korzysta ze stosu wywołań. Rekurencyjna wersja DFS jest często bardziej zwięzła i czytelna, ale może prowadzić do przepełnienia stosu dla bardzo głębokich grafów, gdzie stos iteracyjny oferuje większą kontrolę.