Przeszukiwanie w głąb
Przeszukiwanie w głąb (ang. Depth-first search, w skrócie DFS) – algorytm przeszukiwania grafu. Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi wychodzących z podanego wierzchołka. Po zbadaniu wszystkich krawędzi wychodzących z danego wierzchołka algorytm powraca do wierzchołka, z którego dany wierzchołek został odwiedzony[1].
![]() Kolejność odwiedzania węzłów | |
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Pamięciowa |
h-długość najdłuższej prostej ścieżki |
Przykład
edytujGdybyśmy podany na obrazku graf chcieli przejść wykorzystując algorytm przeszukiwania w głąb, zaczynając od wierzchołka A, to węzły zostałyby odwiedzone w następującej kolejności (w nawiasach podano wierzchołki do których algorytm powraca): A, B, D, (B), F, E, (F), (B), (A), C, G, (C), (A).
Algorytm
edytujfunction VisitNode(u): oznacz u jako odwiedzony dla każdego wierzchołka v na liście sąsiedztwa u: jeżeli v nieodwiedzony: VisitNode(v) function DepthFirstSearch(Graf G): dla każdego wierzchołka u z grafu G: oznacz u jako nieodwiedzony dla każdego wierzchołka u z grafu G: jeżeli u nieodwiedzony: VisitNode(u)
Właściwości
edytujZłożoność pamięciowa
edytujZłożoność pamięciowa przeszukiwania w głąb w przypadku drzewa jest o wiele mniejsza niż przeszukiwania wszerz, gdyż algorytm w każdym momencie wymaga zapamiętania tylko ścieżki od korzenia do bieżącego węzła, podczas gdy przeszukiwanie wszerz wymaga zapamiętywania wszystkich węzłów w danej odległości od korzenia, co zwykle rośnie wykładniczo w funkcji długości ścieżki.
Złożoność czasowa
edytujZłożoność czasowa algorytmu jest uzależniona od liczby wierzchołków oraz liczby krawędzi. Algorytm musi odwiedzić wszystkie wierzchołki oraz wszystkie krawędzie, co oznacza, że złożoność wynosi O(|V|+|E|)[1].
Zupełność (kompletność)
edytujAlgorytm jest zupełny (czyli znajduje rozwiązanie lub informuje, że ono nie istnieje) dla drzew skończonych. Grafy skończone wymagają oznaczania już odwiedzonych wierzchołków. Dla grafów nieskończonych nie jest zupełny.
Zastosowania algorytmu
edytujAlgorytm stosowany jest[1]:
- do wyznaczania silnych spójnych składowych grafu skierowanego
- w algorytmie sortowania topologicznego skierowanego grafu acyklicznego
- sprawdzania, czy istnieje ścieżka między dwoma wierzchołkami w grafie (badanie spójności grafu).
Implementacja
edytujZobacz też
edytujPrzypisy
edytuj- ↑ a b c Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów.. Wyd. 8. Wydawnictwa Naukowo-Techniczne, 2007, s. 549-558. ISBN 978-83-204-3328-9.
Linki zewnętrzne
edytuj- Sylwia Sapkowska , Gdzie tu jest graf?, „Delta”, kwiecień 2025, ISSN 0137-3005 [dostęp 2025-04-10] .