Przeszukiwanie w głąb (DFS)
Przeszukiwanie w głąb (ang. Depth-first search, DFS) to algorytm wykorzystywany do przeszukiwania grafów. Działa on poprzez badanie wszystkich krawędzi wychodzących z danego wierzchołka, a następnie powraca do wierzchołka, z którego został odwiedzony.
Przykład działania algorytmu
Rozpoczynając przeszukiwanie od wierzchołka A w grafie, węzły zostaną odwiedzone w następującej kolejności: A, B, D, F, E, C, G.
Algorytm DFS
Podstawowe funkcje algorytmu można zdefiniować w następujący sposób:
function VisitNode(u):
oznacz u jako odwiedzony
dla każdego wierzchołka v w sąsiedztwie u:
jeżeli v nieodwiedzony:
VisitNode(v)
function DepthFirstSearch(Graf G):
dla każdego wierzchołka u w G:
oznacz u jako nieodwiedzony
dla każdego wierzchołka u w G:
jeżeli u nieodwiedzony:
VisitNode(u)
Właściwości algorytmu
Złożoność pamięciowa
Złożoność pamięciowa algorytmu DFS jest znacznie mniejsza w porównaniu do przeszukiwania wszerz. Wymaga on zapamiętania jedynie ścieżki od korzenia do bieżącego węzła.
Złożoność czasowa
Złożoność czasowa DFS zależy od liczby wierzchołków (|V|) oraz krawędzi (|E|) w grafie, wynosząc O(|V| + |E|).
Zupełność (kompletność)
Algorytm jest zupełny dla skończonych drzew, jednak w przypadku grafów nieskończonych nie gwarantuje znalezienia rozwiązania.
Zastosowania algorytmu
- Wyznaczanie silnych spójnych składowych w grafach skierowanych.
- Sortowanie topologiczne w grafach acyklicznych.
- Sprawdzanie istnienia ścieżki między wierzchołkami (badanie spójności grafu).
Implementacja
Przykłady implementacji algorytmu można znaleźć na stronie Wikibooks.
