Przeszukiwanie w głąb

Przeszukiwanie w głąb
Kolejność odwiedzania węzłów
Rodzaj	Przeszukiwanie grafu
Struktura danych	graf, drzewo
Złożoność
Czasowa	${\displaystyle O(|V|+|E|)}$
Pamięciowa	${\displaystyle O(h)}$ h-długość najdłuższej prostej ścieżki

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

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].

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.

Zastosowania algorytmu

Algorytm 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).

Ponadto algorytm ten jest często spotykany w rozwiązaniach typu brute force problemów z innych dziedzin. Bazuje na nim zdecydowana większość algorytmów służących do przeglądania drzewa gry, np. min-max, czy też alpha-beta.

Implementacja

• Zobacz przykłady implementacji tego algorytmu na stronie Wikibooks

Przypisy

Zobacz też

• Przeszukiwanie wszerz