Căutarea în adâncime (DFS)
Intrați într-un labirint, mergeți până dați de o fundătură, apoi întoarceți-vă la ultima bifurcație și încercați următorul drum. Căutarea în adâncime explorează un graf la fel. Este unul dintre cei mai simpli algoritmi pe grafuri, iar stiva pe care o ține vă spune mai mult decât v-ați aștepta.
Ideea
Un graf este o mulțime de noduri unite prin muchii: camere și uși, pagini web și linkuri, sarcini și sarcinile de care depind. Căutarea în adâncime vizitează fiecare nod pe care îl poate atinge dintr-un start, dar într-o anumită ordine: continuă mereu de la nodul atins cel mai recent. Ține o stivă cu nodurile în care se află. Un nod nou intră în vârf, iar un nod iese doar când tot ce e în jurul lui a fost explorat.
Pas cu pas
Puneți startul pe stivă și dați-i numărul de vizită 1. Priviți următorul vecin al nodului din vârf. Dacă nu a fost văzut, dați-i următorul număr de vizită, rețineți nodul din care a fost atins și puneți-l în vârful stivei. Dacă a mai fost văzut, săriți peste el. Când nodul din vârf nu mai are vecini de verificat, este terminat: scoateți-l și continuați cu nodul de dedesubt. Opriți-vă când stiva este goală sau când ținta este atinsă.
Un exemplu
Luați un graf cu muchiile A–B, A–C, B–D, C–D, C–E și D–F, porniți din A și verificați vecinii în ordine alfabetică. Din A, căutarea merge la B, din B la D, din D la C și din C la E, deci stiva este A, B, D, C, E. Pe drum, C îl vede pe A, care este încă pe stivă: muchia C–A închide ciclul A, B, D, C. E nu are nimic nou, deci este terminat, apoi C, iar căutarea se întoarce la D, care mai are F. Ordinea vizitării este A, B, D, C, E, F. Cu E ca țintă, DFS se oprește cu drumul A → B → D → C → E, patru muchii, deși A → C → E are doar două.
La ce este bună
Stiva este mereu un drum de la start la nodul curent, ceea ce face DFS potrivită pentru labirinturi și puzzle-uri: este ideea din spatele metodei backtracking. Într-un graf neorientat, o muchie spre un nod aflat încă pe stivă închide un ciclu. Într-un graf orientat, listarea nodurilor în ordinea inversă terminării lor dă o ordine topologică, astfel încât sarcinile vin după sarcinile de care depind. Căutarea în adâncime găsește și componentele conexe, punțile și punctele de articulație, iar varianta ei aleatorie este un mod clasic de a genera labirinturi.
Istoric
În secolul al XIX-lea, matematicianul francez Charles Pierre Trémaux a descris o metodă de a ieși din orice labirint marcând culoarele, adică o căutare în adâncime făcută cu creta. În 1972 și 1973, Robert Tarjan și John Hopcroft au arătat că DFS rezolvă multe probleme pe grafuri în timp liniar, de la componentele tare conexe până la a testa dacă un graf poate fi desenat fără intersecții. Au primit Premiul Turing în 1986, în parte pentru această lucrare.
Explorați
Deschideți aplicația și apăsați Pas. Nodul ai cărui vecini sunt verificați este evidențiat, nodurile de pe stivă sunt albastre, iar cele terminate sunt verzi, fiecare cu numărul său de vizită. Stiva apare sub graf, de la start până la nodul din vârf. Urmăriți linia de stare pentru muchiile care închid un ciclu și alegeți o țintă ca să vedeți cât de lung poate fi drumul găsit în comparație cu căutarea în lățime.
Întrebări frecvente
Care este complexitatea în timp a DFS?
O(V + E) pentru V noduri (vârfuri) și E muchii: fiecare nod intră și iese de pe stivă o singură dată, iar fiecare muchie este examinată de la ambele capete. Are nevoie de O(V) memorie suplimentară pentru stivă și marcaje.
De ce folosește DFS o stivă?
Pentru că principiul ultimul intrat, primul ieșit face căutarea să continue de la cel mai nou nod și să se întoarcă la cel dinaintea lui. Recursivitatea face același lucru cu stiva de apeluri a programului. Cu o coadă în loc de stivă, căutarea s-ar extinde inel cu inel: aceasta este căutarea în lățime.
Este DFS recursivă o problemă pentru grafuri mari?
Poate fi: un drum lung înseamnă recursivitate adâncă, iar multe limbaje limitează cât de adânc pot merge apelurile. O stivă explicită într-o buclă evită această limită și vizitează nodurile în aceeași ordine.
Unde se folosește DFS?
La rezolvarea labirinturilor și puzzle-urilor prin backtracking, găsirea ciclurilor, ordonarea sarcinilor după dependențe (sortare topologică), găsirea componentelor conexe și tare conexe, generarea labirinturilor și în compilatoare și instrumente de build care parcurg grafuri de dependențe.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați căutarea în adâncime