Przeszukiwanie w głąb (ang.Depth-first search, w skrócie DFS) – algorytmprzeszukiwania 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].
Przykład
Graf wykorzystany w przykładzie
Gdybyś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
function 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
Złożoność pamięciowa
Zł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
Zł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ść)
Algorytm 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.
