Depth-first search.html



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

Najważniejsze pojęcia graf drzewo 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
	uzytowierzcholek = true; //kolorujemy odwiedzony wierzchołek
	//na tym węźle jesteśmy
	cout <<wierzcholek<<"\n";
	//przejście po sąsiadach wierzchołka
	for (iter=grafwierzcholek.begin(); iter!=grafwierzcholek.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