Căutați în profunzime

Căutați în profunzime
Ordinea de navigare a nodului
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 graficelor , cercetarea aprofundată (în engleză depth-first search, în acronimul DFS) este un algoritm de căutare pe arbori și grafice . Spre deosebire de căutarea în lățime , are caracteristica de a fi recursiv intrinsec.

Definiție

Numele derivă din faptul că într-un copac, chiar înainte de a fi vizitat nodurile primelor generații, algoritmul se poate găsi vizitând vârfuri departe de rădăcină, mergând astfel „în profunzime”. Nu întâmplător, dacă este rulat pe un grafic, algoritmul identifică un arbore care este un subgraf (adică conține toate vârfurile și toate și numai arcele care au fost urmate). Putem vedea algoritmul ca pe o vizită largă în care în loc de o coadă folosim o stivă (adică în loc să adăugăm noile elemente în partea de jos le adăugăm în partea de sus). Strategia de căutare explorează graficul în fiecare instanță de execuție a algoritmului, cât mai profund posibil: arcurile graficului sunt explorate începând cu ultimul vârf descoperit $v$ ${\ displaystyle v}$ $v$ că are încă arcuri neexplorate care ies din ea. Odată ce explorarea tuturor marginilor neexplorate ale vârfului este terminată $v$ ${\ displaystyle v}$ $v$ întoarce-te pentru a explora toate arcele de ieșire începând de la vârful din care $v$ ${\ displaystyle v}$ $v$ 'fusese descoperit anterior. Procesul de explorare continuă până când toate vârfurile grafului au fost explorate. Subgraful predecesorilor, care este generat de vizita în adâncime, poate fi alcătuit din mai mulți arbori : acest subgraf este definit ca o pădure DFS , deci compusă din mai mulți arbori DFS . Căutarea DFS, pe lângă generarea pădurii DFS, marchează fiecare vârf cu informații temporale precise, în special actualizează două etichete pentru fiecare vârf: $d[v]$ ${\ displaystyle d [v]}$ ${\ displaystyle d [v]}$ care înregistrează când vârful generic $v$ ${\ displaystyle v}$ $v$ a fost descoperit și $f[v]$ ${\ displaystyle f [v]}$ ${\ displaystyle f [v]}$ care înregistrează când întreaga listă de adiacență a $v$ ${\ displaystyle v}$ $v$ (adică toate vârfurile la care se poate ajunge din acesta). Vârfurile sunt colorate diferit în funcție de caz: alb , culoarea pe care o ia fiecare vârf înainte de timpul său $d[u]$ ${\ displaystyle d [u]}$ ${\ displaystyle d [u]}$ , gri între timp $d[u]$ ${\ displaystyle d [u]}$ ${\ displaystyle d [u]}$ și $f[u]$ ${\ displaystyle f [u]}$ ${\ displaystyle f [u]}$ și negru în cele ce urmează. Pentru fiecare vârf $tu$ ${\ displaystyle u}$ $tu$ se aplică, de asemenea $d[u]<f[u]$ ${\ displaystyle d [u] <f [u]}$ ${\ displaystyle d [u] <f [u]}$ .

Realizare

Implementarea algoritmului constă din două proceduri: o procedură care începe căutarea și se ocupă de colorarea tuturor vârfurilor graficului cu alb , resetarea contorului global de timp și selectarea fiecărui nod unic al graficului. Pentru fiecare nod selectat se începe o a doua procedură care are sarcina de a efectua vizita efectivă.

 DFS (G)
   pentru fiecare vârf u în V [G] do
     culoare [u] ← alb
     π [u] ← zero
   timp ← 0
   pentru fiecare vârf u în V [G] do
     dacă culoarea [u] = alb
       apoi DFS-Visit (u)

Procedura de vizitare a nodului are grijă de colorarea corespunzătoare a tuturor vârfurilor vizitate începând de la $tu$ ${\ displaystyle u}$ $tu$ (vârfurile din lista de adiacență $Adj[u]$ ${\ displaystyle Adj [u]}$ ${\ displaystyle Adj [u]}$ ), pentru a actualiza valorile de timp și a construi pădurea DFS.

 Vizita DFS (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
       Vizita DFS (v)
   culoare [u] ← negru
   f [u] ← timp ← timp + 1

Complexitate

Procedura DFS necesită un timp de execuție de $\Theta (V)$ ${\ displaystyle \ Theta (V)}$ ${\ displaystyle \ Theta (V)}$ cu excepția timpului pentru executarea DFS-Visit . Ultima procedură se numește o dată pentru fiecare vârf $v$ ${\ displaystyle v}$ $v$ iar ciclul său rulează exact $\left|Adj[v]\right|$ ${\ displaystyle \ left | Adj [v] \ right |}$ ${\ displaystyle \ left | Adj [v] \ right |}$ ori, deci în total:

$\sum \left|Adj[v]\right|=\Theta (E)$ ${\ displaystyle \ sum \ left | Adj [v] \ right | = \ Theta (E)}$ ${\ displaystyle \ sum \ left | Adj [v] \ right | = \ 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 efectuat operațiuni pe fiecare vârf vizitat, algoritmul se poate comporta în 3 moduri diferite:

efectuează operația, apoi se reamintește asupra copiilor ( precomandă )
reamintiți-vă copiii, apoi efectuați operația ( după comandă )
reamintește-te pe unii copii, efectuează operația, reamintește-te pe copiii rămași ( vizită în ordine , interesant în copaci binari sau în grafice cu liste de adiacență ordonate într-un mod special)

Implementare Python

Pentru grafice

 vizită definitivă ( vârf ):
    summit . vizitat = Adevărat
    pentru adiacent în vârf . adiacent :
        dacă nu adiacent . vizitat :
            vizita ( adiacent )

Pentru copaci

 vizită definitivă ( vârf ):
    pentru adiacent în vârf . adiacent :
        vizita ( adiacent )

Notă

^ Cunoscut numărul de vârfuri $|V|$ ${\ displaystyle | V |}$ ${\ displaystyle | V |}$ și de arcade $|E|$ ${\ displaystyle | E |}$ ${\ displaystyle | E |}$
^ ^a ^b Cunoscut factorul de ramificare $b$ ${\ displaystyle b}$ $b$ iar adâncimea maximă $d$ ${\ displaystyle d}$ $d$
^ Cunoscut numărul de vârfuri $|V|$ ${\ displaystyle | V |}$ ${\ displaystyle | V |}$