Hloubka první Hledat nebo Hloubka traversal je rekurzivní algoritmus pro prohledávání všech vrcholů grafu nebo stromové datové struktury. Traversal znamená návštěvu všech uzlů grafu.

Hloubka První Hledat Algoritmus

standardní DFS provádění klade každý vrchol grafu do jedné ze dvou kategorií:

1. Navštívil
2. Nenavštívil

cílem algoritmu je, aby označit každý vrchol jako navštívené, zatímco vyhnout se cykly.,

algoritmus DFS funguje následovně:

1. Začněte tím, že umístíte některý z vrcholů grafu na horní část zásobníku.
2. vezměte horní položku zásobníku a přidejte ji do navštíveného seznamu.
3. Vytvořte seznam sousedních uzlů tohoto vrcholu. Přidejte ty, které nejsou v navštíveném seznamu, do horní části zásobníku.
4. opakujte kroky 2 a 3, dokud není zásobník prázdný.

depth first Search Example

podívejme se, jak algoritmus hloubkového vyhledávání funguje s příkladem. Používáme neřízený graf s 5 vrcholy.,

začneme od vrcholu 0, DFS algoritmus začíná tím, že v Navštívených seznamu a uvedení všech jeho sousední vrcholy v zásobníku.

Další, navštívíme prvek na vrcholu zásobníku, tj 1 a jít na své sousední uzly. Vzhledem k tomu, že 0 již bylo navštíveno, místo toho navštívíme 2.,

Vertex 2 má nenavštívené přilehlé vrcholy ve 4, tak jsme dodat, že na vrcholu zásobníku a navštívit ji.

po návštěvě posledního prvku 3 nemá žádné nenavštívené sousední uzly, takže jsme dokončili hloubku první Průchozí grafu.,

DFS Pseudocode (rekurzivní implementace)

pseudocode pro DFS je uveden níže. Ve funkci init() si všimněte, že na každém uzlu spustíme funkci DFS. Je to proto, že graf může mít dvě různé odpojené části, abychom se ujistili, že pokryjeme každý vrchol, můžeme také spustit algoritmus DFS na každém uzlu.,

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)}

DFS Implementace v jazyce Python, Java a C/C++

kód pro Hloubku První Vyhledávací Algoritmus příklad je uveden níže. Kód byl zjednodušen, abychom se mohli zaměřit spíše na algoritmus než na jiné detaily.

Složitost Hloubka První Hledat

časová složitost DFS algoritmus je zastoupena v podobě O(V + E), kde V je počet uzlů a E je počet hran.

prostorová složitost algoritmu je O(V).,

Aplikace DFS Algoritmus

1. Pro nalezení cesty
2. otestovat, zda je graf bipartitní
3. Pro hledání v silně souvislé komponenty grafu
4. Pro detekci cyklů v grafu