INF.04Algorytmika i Struktury Danych
Przeszukiwanie grafu: DFS i BFS
Dwa podstawowe algorytmy przeszukiwania grafów: DFS eksploruje ścieżki w głąb przy użyciu stosu/rekurencji, a BFS warstwami przy użyciu kolejki FIFO.
Porównanie DFS i BFS:
| Cecha | DFS (Depth-First Search) | BFS (Breadth-First Search) |
|---|---|---|
| Koncepcja | Przeszukiwanie w głąb (schodzi jak najgłębiej wzdłuż ścieżki) | Przeszukiwanie wszerz (odwiedza wszystkich sąsiadów warstwa po warstwie) |
| Struktura danych | Stos (LIFO) lub rekurencja | Kolejka (FIFO) |
| Zastosowanie | Cykle w grafie, sortowanie topologiczne, labirynty | Najkrótsza ścieżka w grafie nieważonym, systemy nawigacji |
| Złożoność | O(V + E) | O(V + E) (gdzie V - wierzchołki, E - krawędzie) |
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Przeszukiwanie grafu: DFS i BFS lub rozpocznij trening.