adâncime prima căutare sau adâncime prima traversare este un algoritm recursiv pentru căutarea toate vârfurile unui grafic sau structura de date copac. Traversal înseamnă vizitarea tuturor nodurilor unui grafic.

Adâncime Primul Algoritm de Căutare

Un standard DFS implementarea pune fiecare nod din graf în una din două categorii:

1. a Vizitat
2. Nu a Vizitat

scopul algoritmului este de a marca fiecare nod vizitat evitând în același timp cicluri.,

algoritmul DFS funcționează după cum urmează:

1. începeți prin a pune oricare dintre vârfurile graficului deasupra unei stive.
2. luați elementul de sus al stivei și adăugați-l la lista vizitată.
3. creati o lista a nodurilor adiacente acelui nod. Adăugați cele care nu se află în lista vizitată în partea de sus a stivei.
4. continuați să repetați pașii 2 și 3 până când stiva este goală.

exemplu de căutare în profunzime

Să vedem cum funcționează algoritmul de căutare în profunzime cu un exemplu. Folosim un grafic nedirecționat cu 5 noduri.,

Vom începe de la nodul 0, DFS algoritm incepe prin a pune-l în lista de Vizitat și de a pune toate nodurile sale adiacente în stivă.

Apoi, vom vizita elementul de la partea de sus a stivei, adică 1 și du-te la nodurile sale adiacente. Deoarece 0 a fost deja vizitat, vizităm 2 în schimb.,

Vertex 2 are o nevizitate adiacente nodurilor în 4, deci vom adăuga că la partea de sus a stivei și-l viziteze.

după ce vizităm ultimul element 3, acesta nu are noduri adiacente nevizitate, așa că am finalizat prima traversare a adâncimii graficului.,

DFS Pseudocod (implementare recursivă)

pseudocod pentru DFS este prezentat mai jos. În funcția init (), observați că rulăm funcția DFS pe fiecare nod. Acest lucru se datorează faptului că graficul ar putea avea două părți diferite deconectate, astfel încât să ne asigurăm că acoperim fiecare nod, putem rula algoritmul DFS pe fiecare nod.,

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

implementarea DFS în Python, Java și C/C++

codul pentru algoritmul de căutare în profunzime cu un exemplu este prezentat mai jos. Codul a fost simplificat astfel încât să ne putem concentra mai degrabă pe algoritm decât pe alte detalii.

Complexitatea Adâncime în Primul rând de Căutare

complexitatea timp a DFS algoritm este reprezentat în formă de O(V + E), unde V este numărul de noduri și E este numărul de muchii.

complexitatea spațiului algoritmului este O(V).,

aplicarea algoritmului DFS

1. Pentru a găsi calea
2. pentru a testa dacă graficul este bipartit
3. pentru a găsi componentele puternic conectate ale unui grafic
4. pentru detectarea ciclurilor într-un grafic