Depth first Search lub Depth first traversal jest rekursywnym algorytmem do przeszukiwania wszystkich wierzchołków wykresu lub struktury danych drzewa. Traversal oznacza odwiedzanie wszystkich węzłów wykresu.
algorytm pierwszego wyszukiwania głębokości
standardowa implementacja DFS umieszcza każdy wierzchołek grafu w jednej z dwóch kategorii:
- odwiedzony
- nie odwiedzony
celem algorytmu jest oznaczanie każdego wierzchołka jako odwiedzonego, unikając cykli.,
algorytm DFS działa w następujący sposób:
- zacznij od umieszczenia dowolnego wierzchołka grafu na stosie.
- weź górną pozycję stosu i dodaj ją do odwiedzanej listy.
- Utwórz listę sąsiednich węzłów tego wierzchołka. Dodaj te, których nie ma na liście odwiedzonych, do górnej części stosu.
- powtarzaj kroki 2 i 3, aż stos będzie pusty.
Depth First Search Example
zobaczmy, jak algorytm wyszukiwania Depth First działa z przykładem. Używamy wykresu bezokierunkowego z 5 wierzchołkami.,
zaczynamy od wierzchołka 0, algorytm DFS rozpoczyna się od umieszczenia go na liście odwiedzanych i umieszczenia wszystkich sąsiednich wierzchołków na stosie.
następnie odwiedź element u góry stosu tj. 1 i przejdź do jego sąsiednich węzłów. Ponieważ 0 zostało już odwiedzone, odwiedzamy 2 zamiast.,
wierzchołek 2 ma nieodwiedziony sąsiadujący wierzchołek w 4, więc dodajemy go do górnej części stosu i odwiedzamy go.
po odwiedzeniu ostatniego elementu 3, nie ma on żadnych nieodwiedzianych sąsiednich węzłów, więc ukończyliśmy głębokość pierwszego przejścia wykresu.,
Pseudokod DFS (implementacja rekurencyjna)
pseudokod DFS jest pokazany poniżej. W funkcji init() zauważ, że uruchamiamy funkcję DFS na każdym węźle. Dzieje się tak, ponieważ Wykres może mieć dwie różne odłączone części, więc aby upewnić się, że obejmujemy każdy wierzchołek, możemy również uruchomić algorytm DFS na każdym węźle.,
DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}
implementacja DFS w Pythonie, Javie i C/C++
kod dla algorytmu wyszukiwania głębokości z przykładem jest pokazany poniżej. Kod został uproszczony, dzięki czemu możemy skupić się na algorytmie, a nie na innych szczegółach.
złożoność pierwszego wyszukiwania głębokości
złożoność czasowa algorytmu DFS jest reprezentowana w postaciO(V + E), gdzieV jest liczbą węzłów, aE jest liczbą krawędzi.
złożoność przestrzeni algorytmu wynosi O(V).,
zastosowanie algorytmu DFS
- do znajdowania ścieżki
- do testowania, czy Graf jest dwudzielny
- do znajdowania silnie połączonych składników grafu
- do wykrywania cykli w grafie