Przeszukiwanie w głąb

Z Wikipedii

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

Najważniejsze pojęcia graf podgraf cykl klika stopień wierzchołka 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 Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

Przeszukiwanie w głąb
Kolejność odwiedzania węzłów
Podstawowe informacje
Klasa algorytmu: przeszukiwania Struktura danych: graf, drzewo Złożoność czasowa: O( | V | + | E | ) Złożoność pamięciowa: O( | V | + | E | ) Optymalny: nie Kompletny: nie

Przeszukiwanie w głąb (ang. Depth-first search, w skrócie DFS) – w informatyce algorytm przeszukiwania grafu używany do przechodzenia lub przeszukiwania drzewa lub grafu. Przeszukiwanie zaczyna się od korzenia i porusza się w dół do samego końca gałęzi, po czym wraca się o jeden poziom i próbuje kolejne gałęzie itd.

Spis treści 1 Przykład 2 Algorytm rekurencyjny (pseudokod) 3 Właściwości 3.1 Złożoność pamięciowa 3.2 Złożoność czasowa 3.3 Kompletność 4 Zastosowania algorytmu 5 Bibliografia

[edytuj] Przykład

Przyjrzyjmy się poniższemu grafowi:

.

Zakładając że najpierw wybiera się węzły z lewej strony, później te z prawej, oraz zakładając, że przeszukiwanie będzie pamiętało które wierzchołki są już odwiedzone, przeszukiwanie zaczynając od A, odwiedzi się węzły w tej kolejności: A, B, D, F, E, C, G.

Przeszukując bez pamiętania które wierzchołki się już odwiedziło, kolejność będzie taka: A, B, D, F, E, A, B, D, F, E, itd. w nieskończoność, będąc uwięzionym w cyklu A, B, D, F, E i nigdy nie docierając do C lub G.

[edytuj] Algorytm rekurencyjny (pseudokod)

DFS(Wierzchołek, Cel)
{
  jeżeli Wierzchołek nieodwiedzony
     jeżeli Wierzchołek jest równy Cel
     {
         zwróć Wierzchołek jako wynik (i zakończ to wywołanie funkcji)
     }
     w przeciwnym wypadku, jeżeli Wierzchołek jest różny od Cel, wykonaj
     {
         zaznacz Wierzchołek jako odwiedzony
         dodaj Wierzchołek na Stos
         dopóki Stos jest niepusty wykonuj
         {
             zdejmij węzeł ze szczytu Stosu i nazwij go Wierzchołek2
             wywołaj DFS(Wierzchołek2, Cel)
         }
     }
}

[edytuj] Właściwości

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

Złożoność pamięciowa przeszukiwania w głąb jest o wiele mniejsza niż przeszukiwania wszerz.

[edytuj] Złożoność czasowa

Złożoność czasowa obu algorytmów jest proporcjonalna do sumy liczby wierzchołków i liczby krawędzi w przeszukiwanym grafie.

[edytuj] Kompletność

[edytuj] Zastosowania algorytmu

Przeszukiwanie w głąb jest często stosowanym algorytmem w teorii grafów. Używa się go m.in. do:

• Znajdywania najkrótszych ścieżek między dwoma wierzchołkami w drzewie.
• Sprawdzania, czy istnieje ścieżka między dwoma wierzchołkami w grafie.
• Wyznaczania spójnych składowych.

Rozwiązania poniższych problemów teoriografowych opierają się na przeszukiwaniu w głąb:

• Wyznaczanie silnie spójnych składowych w grafie skierowanym.
• Sortowanie topologiczne skierowanego grafu acyklicznego.

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.

[edytuj] Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, WNT 2005, ISBN 83-204-3149-2

To jest tylko zalążek artykułu z dziedziny informatyki. Jeśli możesz, rozbuduj go.