Caută în profunzime

Caută în profunzime
Pentru navigare Node
Clasă	Algoritm de căutare
Structură de date	Grafic
Cel mai rău caz din punct de vedere temporal	$O(\|V\|+\|E\|)$ ${\ displaystyle O (\| V \| + \| E \|)}$ ${\ displaystyle O (\| V \| + \| E \|)}$ (pentru grafice explicite) ^[1] $O(b^{d})$ ${\ Displaystyle O (b ^ {d})}$ ${\ Displaystyle O (b ^ {d})}$ (pentru grafice implicite) ^[2]
Cel mai rău caz spațial	$O(\|V\|)$ ${\ displaystyle O (\| V \|)}$ ${\ displaystyle O (\| V \|)}$ (pentru grafice explicite) ^[3] $O(b^{d})$ ${\ Displaystyle O (b ^ {d})}$ ${\ Displaystyle O (b ^ {d})}$ (pentru grafice implicite) ^[2]
Optim	Nu
Costum de afaceri	Nu
Manual

În teoria grafurilor , în profunzime de cercetare (în limba engleză adancime de căutare, în acronimul DFS) este un algoritm de căutare pe copaci și grafice . Spre deosebire de căutare în lățime , are caracteristica de a fi intrinsec recursive.

Definiție

Astecii derivă din faptul că, într-un copac, chiar înainte de a fi vizitat nodurile din primele generații, algoritmul se poate găsi de a vizita nodurile departe de rădăcină, astfel merge „în profunzime“. Nu întâmplător, în cazul în care rula pe un grafic, identifică un copac algoritm care este un subgraf (adică, acesta conține toate nodurile și toate și numai arcele care au fost urmate). Putem vedea algoritmul ca o largă vizită în care în loc de o coadă folosim o stivă (adică în loc să adauge elemente noi la partea de jos le adăuga la partea de sus). Strategia de căutare explorează graficul merge, în fiecare moment al execuției algoritmului, cât mai profund posibil: arcele graficului sunt explorate pornind de la ultimul vârf descoperit $v$ ${\ displaystyle v}$ $v$ că încă mai are arcade neexplorate care ies din ea. După explorarea tuturor marginilor neexplorate ale Vertex este terminat $v$ ${\ displaystyle v}$ $v$ du-te înapoi pentru a explora toate arcele de ieșire pornind de la vârful din care $v$ ${\ displaystyle v}$ $v$ „Au fost anterior descoperite. Procesul de explorare continuă până când toate nodurile din grafic au fost explorate. Subgraful predecesorilor, care este generat de vizita de adâncime, poate fi alcătuită din mai multe copaci : această subgrafic este definită ca o pădure DFS, prin urmare , compus din mai multe arbori DFS. DFS de căutare, în plus față de generarea DFS mărcilor forestiere fiecare vârf cu informații temporale precise, în special actualizări două etichete pentru fiecare nod: $d[v]$ ${\ D displaystyle [v]}$ ${\ D displaystyle [v]}$ care înregistrările atunci când vârful generic $v$ ${\ displaystyle v}$ $v$ a fost descoperit și $f[v]$ ${\ F displaystyle [v]}$ ${\ F displaystyle [v]}$ care de înregistrări atunci când întreaga lista de adiacenta a $v$ ${\ displaystyle v}$ $v$ (adică toate nodurile care pot fi atinse de ea). Nodurile sunt colorate diferit , în funcție de caz: alb, culoarea pe care fiecare nod preia înainte de timpul său $d[u]$ ${\ D displaystyle [u]}$ ${\ D displaystyle [u]}$ , Gri între timp $d[u]$ ${\ D displaystyle [u]}$ ${\ D displaystyle [u]}$ și $f[u]$ ${\ F displaystyle [u]}$ ${\ F displaystyle [u]}$ și negru în cele ce urmează. Pentru fiecare nod $tu$ ${\ displaystyle u}$ $tu$ De asemenea, se aplică $d[u]<f[u]$ ${\ Displaystyle d [u] <f [u]}$ ${\ Displaystyle d [u] <f [u]}$ .

Realizare

Punerea în aplicare a algoritmului constă în două proceduri: o procedură care începe căutarea și are grijă de colorare toate nodurile graficului cu alb, resetarea contorul de timp la nivel mondial și selectând fiecare singur nod al graficului. Pentru fiecare singur nod selectat o a doua procedură este pornit, care are sarcina de a efectua vizita efectivă.

 DFS (G)
   pentru fiecare nod u în V [G] do
     culoare [u] ← alb
     π [u] ← zero
   timp ← 0
   pentru fiecare nod u în V [G] do
     în cazul în care culoarea [u] = alb
       apoi DFS-vizită (u)

Procedura pentru a vizita nodul are grijă de colorat corespunzător toate nodurile vizitate pornind de la $tu$ ${\ displaystyle u}$ $tu$ (nodurile din lista de adiacenta $Adj[u]$ ${\ Displaystyle Adj [u]}$ ${\ Displaystyle Adj [u]}$ ), Pentru a actualiza valorile de timp și de a construi pădurea DFS.

 DFS-vizită (u)
   culoare [u] ← gri
   d [u] ← timp ← timp + 1
   pentru fiecare vârf v în Adj [u] do
     dacă culoarea [v] = alb atunci
       π [v] ← u
       DFS-vizită (v)
   culoare [u] ← negru
   f [u] ← timp ← timp + 1

Complexitate

Procedura DFS necesită timp de execuție a $\Theta (V)$ ${\ Displaystyle \ Theta (V)}$ ${\ Displaystyle \ Theta (V)}$ cu excepția timpului pentru executarea DFS-vizită. Această din urmă procedură se numește o singură dată pentru fiecare nod $v$ ${\ displaystyle v}$ $v$ și ciclul său se execută exact $\left|Adj[v]\right|$ ${\ Displaystyle \ left | Adj [v] \ dreapta |}$ ${\ Displaystyle \ left | Adj [v] \ dreapta |}$ ori, prin urmare, în total:

$\sum \left|Adj[v]\right|=\Theta (E)$ ${\ Displaystyle \ sum \$ din $stânga | Adj [v] \ dreapta | = \ Theta (E)}$ ${\ Displaystyle \ sum \ din stânga | Adj [v] \ dreapta | = \ Theta (E)}$

Deci, timpul total de execuție este egal cu $\Theta (V+E)$ ${\ Displaystyle \ Theta (V + E)}$ ${\ Displaystyle \ Theta (V + E)}$ .

Ordin

Având de a efectua operațiuni pe fiecare nod vizitat, algoritmul se poate comporta în 3 moduri diferite:

efectuează operația, apoi se amintesc pe copii (precomanda)
se amintesc pe copii, apoi să efectueze operațiunea (post-comandă)
se amintesc pe unii copii, efectua operația, se amintesc asupra copiilor rămași (vizită în ordine, interesant în arbori binari sau în grafice cu liste de adiacenta ordonate într - un anumit mod)

implementare Python

pentru grafice

 Vizita def (vertex):
    Summit - ul. a vizitat = Adevărat
    pentru adiacente în vertex. adiacente:
        în cazul în care nu este adiacent. vizitat:
            Vizita (adiacentă)

pentru copaci

 Vizita def (vertex):
    pentru adiacente în vertex. adiacente:
        Vizita (adiacentă)

Notă

^ Cunoscut numărul de noduri $|V|$ ${\ Displaystyle | V |}$ ${\ displaystyle | V |}$ și arcuri $|E|$ ${\ Displaystyle | E |}$ ${\ displaystyle | E |}$
^ ^A ^b Cunoscute factorul de ramificare $b$ ${\ displaystyle b}$ $b$ iar adâncimea maximă $d$ ${\ displaystyle d}$ $d$
^ Cunoscut numărul de noduri $|V|$ ${\ Displaystyle | V |}$ ${\ displaystyle | V |}$