Przeczytaj

Jak działa przeszukiwanie grafu w głąb?

Przeszukiwanie w głąb, nazywane w skrócie DFSDFSDFS, to jedna z metod przeszukiwania grafów nieskierowanych lub skierowanych. Jak sama nazwa wskazuje, algorytm przechodzi graf, sięgając tak głęboko, jak to tylko możliwe. Jeśli algorytm dotrze do wierzchołka, którego wszyscy sąsiedzi zostali już odwiedzeni, zawraca do ostatniego wierzchołka, który ma jeszcze nieodwiedzonych sąsiadów. Jest to działanie podobne do trawersowania drzewa w kolejności pre‑ordertrawersowanie pre‑ordertrawersowania drzewa w kolejności pre‑order.

Algorytm przeszukiwania w głąb przechodzi przez graf w sposób, który przypomina przemierzanie labiryntu. Po wybraniu wierzchołka startowego przechodzimy po kolejnych krawędziach najdalej, jak to tylko możliwe. W labiryncie nie zawracamy, dopóki mamy przed sobą jeszcze jakieś nieodwiedzone ścieżki. Robimy to dopiero wtedy, gdy trafimy na ślepy zaułek. Analogicznie podczas przeszukiwania w głąb odwiedzane są kolejne sąsiadujące ze sobą wierzchołki grafu, dopóki nie trafimy na wierzchołek, którego wszyscy sąsiedzi zostali już odwiedzeni. W takim wypadku cofamy się do poprzedniego wierzchołka posiadającego nieodwiedzonych sąsiadów i to od niego kontynuujemy przeszukiwanie.

Podczas przeszukiwania w głąb wykonywane są dwie zasadnicze czynności:

oznaczanie wierzchołka jako odwiedzonego,
badanie wierzchołka, czyli wywołanie rekurencyjnejrekurencjarekurencyjnej funkcji DFS() dla wszystkich sąsiednich wierzchołków nieodwiedzonych.

Polecenie 1

Zapoznaj się z prezentacją przedstawiającą przykład przeszukiwania grafu w głąb.

R11QmoLaNALec1

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Przeanalizujmy algorytm rekurencyjny przeszukiwania grafu w głąb zapisany za pomocą pseudokodu. Algorytm podzielono tu na dwie funkcje. Pierwsza z nich, czyli DFS(), jest wywoływana rekurencyjnie i zaznacza kolejne wierzchołki jako odwiedzone. Funkcja StartDFS() inicjalizuje wierzchołki grafu jako nieodwiedzone i uruchamia funkcję DFS(), począwszy od wierzchołka start.

Specyfikacja:

Dane:

listaSasiedztwa – lista sąsiedztwa reprezentująca przeszukiwany graf
V – liczba naturalna dodatnia; liczba wierzchołków grafu

Wynik:

odwiedzone – V-elementowa tablica zawierająca listę wierzchołków wypisanych w kolejności odwiedzin

graf reprezentuje lista sąsiedztwa "listaSasiedztwa"

funkcja DFS(v):
	wypisz v
	oznacz wierzchołek "v" jako odwiedzony
	dla każdego "w" z listaSasiedztwa[v] wykonuj:
		jeżeli wierzchołek "w" nie został odwiedzony:
			DFS(w)

funkcja startDFS(start):
	oznacz wszystkie wierzchołki grafu jako nieodwiedzone
	DFS(start)

Zwykle wierzchołki oznaczamy jako odwiedzone w tablicy (nazwanej w pseudokodzie odwiedzone), w której i-ty wyraz odpowiada wierzchołkowi o indeksie i. Jeśli wartość odwiedzone[i] jest równa prawda, oznacza to, że wierzchołek został odwiedzony. W przeciwnym razie wierzchołek uznajemy za nieodwiedzony. Oto zapisany za pomocą pseudokodu program przeszukiwania w głąb, korzystający z takiej tablicy:

graf reprezentuje lista sąsiedztwa "listaSasiedztwa"
utwórz tablicę odwiedzone[0..V-1]

funkcja DFS(v):
	wypisz v
	odwiedzone[v] ← prawda
	dla każdego "w" z listaSasiedztwa[v] wykonuj:
		jeżeli odwiedzone[w] = fałsz:
			DFS(w)

funkcja startDFS(start):
	dla i = 0, 1, ..., V-1 wykonuj:
		odwiedzone[i] ← fałsz
	DFS(start)

Istnieje iteracyjna wersja algorytmu przeszukiwania grafu w głąb, która korzysta ze stosustosstosu LIFO, przechowującego indeksy wierzchołków. Oto przykład zapisanego za pomocą pseudokodu iteracyjnego algorytmu DFS:

graf reprezentuje lista sąsiedztwa "listaSasiedztwa"
utwórz tablicę odwiedzone[0..V-1]

funkcja iteracyjnyDFS(start):
	dla i = 0, 1, ..., V-1 wykonuj:
		odwiedzone[i] ← fałsz

	utwórz pusty stos "stos"
	dodaj wierzchołek "start" na stos 
	dopóki rozmiar(stos) > 0 wykonuj:
		v ← zdejmij wierzchołek z góry stosu
		wypisz v
		odwiedzone[v] ← prawda
		dla każdego "w" z listaSasiedztwa[v] wykonuj:
			jeżeli odwiedzone[w] = fałsz:
				dodaj wierzchołek "w" na stos

Słownik

DFS

ang. depth‑first search – algorytm przeszukiwania/przejścia grafu w głąb polegający na przechodzeniu przez wierzchołki, do których prowadzą ścieżki; algorytm DFS gwarantuje, że żaden wierzchołek nie zostanie pominięty

rekurencja

technika programowania, w której funkcja wywołuje samą siebie, aż do napotkania przypadku podstawowego, czyli takiego, którego nie da się rozłożyć na mniejsze problemy; przykład przypadku podstawowego dla obliczania piątego wyrazu ciągu Fibonacciego:

f i b (4) = f i b (3) + f i b (2) = (f i b (2) + f i b (1)) + (f i b (1) + f i b (0)) =

= ((f i b (1) + f i b (0)) + f i b (1)) + (f i b (1) + f i b (0)) =

= ((1 + 0) + 1) + (1 + 0) = 3

stos

dynamiczna struktura danych, dla której możemy dodać nowy element jedynie na samym szczycie; usuwanie elementów ze stosu ma podobną formę co dodawanie, ponieważ możemy usunąć element znajdujący się tylko na szczycie

trawersowanie pre‑order

odwiedzenie węzłów drzewa w określonej kolejności: przechodząc najpierw przez korzeń, później lewe poddrzewo korzenia, a następnie prawe poddrzewo korzenia.

Wprowadzenie

Symulacja interaktywna

Jak działa przeszukiwanie grafu w głąb?

Słownik