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 | ) Kompletny: tak

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.

[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, przeszukiwanie zaczynając od A, odwiedzi się węzły w tej kolejności:

A, B, D, B, F, E, F, B, A, C, G.

[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] Przykład w C++

Implementacja DFS w C++:

void DFS(vector< vector<int> > &graf,int wierzcholek,vector<bool> &uzyto) {
        vector<int>::iterator iter; //iterator po sąsiadach wierzchołka
        uzyto[wierzcholek] = true; //kolorujemy odwiedzony wierzchołek
        //na tym węźle jesteśmy
        cout <<wierzcholek<<"\n";
        //przejście po sąsiadach wierzchołka
        for (iter=graf[wierzcholek].begin(); iter!=graf[wierzcholek].end(); iter++) { 
                //jeżeli wierzchołek nie odwiedzony, to wywołujemy DFS rekurencyjnie
                if (uzyto[*iter] == false) 
                        DFS(graf,*iter,uzyto);
        }
}
 
void DFS(vector< vector<int> > &graf, //wektor wektorów, w którym zapisujemy sąsiadów wierzchołka       
         int wierzcholek=0 //wierzchołek, od którego startujemy
) {
        vector <bool> uzyto(graf.size(),false);
        DFS(graf,wierzcholek,uzyto);
}

[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 związanego z informatyką. Jeśli potrafisz, rozbuduj go.