INF.04Algorytmika i Struktury Danych
Przeszukiwanie grafów: W głąb (DFS) i Wszerz (BFS)
Fundamentalne algorytmy przechodzenia wierzchołków grafu: DFS eksploruje ścieżkę jak najgłębiej przy użyciu stosu/rekurencji, a BFS bada warstwami sąsiadów przy użyciu kolejki FIFO.
Porównanie przeszukiwania DFS vs BFS
| Cecha | Przeszukiwanie w głąb (DFS - Depth-First Search) | Przeszukiwanie wszerz (BFS - Breadth-First Search) |
|---|---|---|
| Używana struktura danych | Stos (LIFO) lub Rekurencja | Kolejka (FIFO) |
| Sposób eksploracji | Idzie wzdłuż jednej gałęzi tak głęboko, jak to możliwe, a po osiągnięciu ślepego zaułka cofa się (Backtracking) | Eksploruje graf 'warstwami' (promieniście) – najpierw wszyscy bezpośredni sąsiedzi, potem sąsiedzi sąsiadów |
| Najkrótsza ścieżka | Nie gwarantuje najkrótszej drogi | Gwarantuje znalezienie najkrótszej ścieżki w grafie nieważonym (o stałej wadze krawędzi) |
| Złożoność czasowa | O(V + E) dla reprezentacji listą sąsiedztwa | O(V + E) dla reprezentacji listą sąsiedztwa |
| Zastosowania | Wykrywanie cykli w grafie, sortowanie topologiczne, labirynty, spójne składowe | Najkrótsza ścieżka w grafie nieważonym, algorytm Web Crawlera, znajdowanie relacji znajomych w social media |
Tablica odwiedzonych wierzchołków (visited[]):
W obu algorytmach niezbędna jest tablica/zbiór bool visited[], zapobiegająca zapętleniu się w cyklach grafu.
Pułapki na egzaminie INF.04:
- DFS wykorzystuje Stos (lub rekurencję), natomiast BFS wykorzystuje Kolejkę FIFO.
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Przeszukiwanie grafów: W głąb (DFS) i Wszerz (BFS) lub rozpocznij trening.