Przeszukiwanie w głąb

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Przeszukiwanie w głąb
Depth-first-tree.png
Kolejność odwiedzania węzłów
Rodzaj Przeszukiwanie grafu
Struktura danych graf, drzewo
Złożoność
Czasowa O(|V|+|E|)
Pamięciowa 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


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


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) – jeden z algorytmów 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

   function VisitNode(u):
       kolor[u] = SZARY
       czas = czas + 1
       poczatek[u] = czas
       dla każdego wierzchołka v na liście sąsiedztwa u:
           jeżeli v jest biały:
               rodzic[v] = u
               VisitNode(v)
       kolor[u] = CZARNY
       czas = czas + 1
       koniec[u] = czas
   function DepthFirstSearch(Graf G):
       dla każdego wierzchołka u z grafu G:
           kolor[u] = BIAŁY
           poczatek[u] = koniec[u] = 0
           rodzic[u] = NIL
       czas = 0
       dla każdego wierzchołka u z grafu G:
           jeżeli u jest biały:
               VisitNode(u) 

Właściwości[edytuj | edytuj kod]

Złożoność pamięciowa[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ść)[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Algorytm stosowany jest[1]:

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[potrzebne źródło].

Implementacja[edytuj | edytuj kod]

Przypisy

  1. 1,0 1,1 1,2 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.

Zobacz też[edytuj | edytuj kod]