- Curent
- Pe stivă
- Terminate
- Drum
Căutarea în adâncime (DFS)
Căutarea în adâncime explorează un graf ca cineva care străbate un labirint cu o mână pe perete: urmează un drum cât de departe se poate și se întoarce doar când nu mai are unde merge. Face asta cu o stivă. Faceți clic pe un nod pentru a porni din el, alegeți o țintă dacă doriți și parcurgeți căutarea pas cu pas pentru a vedea cum stiva crește și scade, cum fiecare nod primește numărul de vizită și ce muchii închid un ciclu. Apăsați Redare pentru a urmări căutarea sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Faceți clic pe un nod ca să devină start; comutați clicul pe Țintă și faceți clic pe alt nod pentru a căuta un drum până la el. Numărul de pe fiecare nod este ordinea în care a fost vizitat, iar rândul de sub graf este stiva, de la start până la nodul din vârf. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Faceți clic pe un nod ca să devină start. Pentru a căuta un drum, comutați clicul pe Țintă și faceți clic pe alt nod.
- Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde în căutare.
- Urmăriți stiva de sub graf și numărul de vizită de pe fiecare nod. Graf nou creează alt graf de încercat.
Cum funcționează căutarea în adâncime
Puneți nodul de start pe stivă. Apoi repetați: priviți următorul vecin al nodului din vârful stivei. Un vecin care nu a fost încă văzut primește următorul număr de vizită, reține nodul din care a fost atins și intră în vârful stivei, astfel încât căutarea continuă de acolo. Când nodul din vârf nu mai are vecini de verificat, este terminat și iese de pe stivă, iar căutarea se întoarce la nodul de dedesubt. Când stiva este goală, toate nodurile care pot fi atinse au fost vizitate.
Ce vă spune stiva
Deoarece căutarea continuă mereu de la cel mai nou nod, stiva este mereu un drum de la start la nodul examinat. Când ținta este atinsă, stiva este un drum până la ea, deși de obicei nu cel mai scurt: pe acela îl găsește căutarea în lățime. Într-un graf neorientat, o muchie spre un nod aflat încă pe stivă, altul decât cel din care tocmai s-a venit, închide un ciclu. Nodurile reținute formează un arbore, arborele de căutare în adâncime, iar ordinea în care nodurile sunt terminate este cheia sortării topologice.
Întrebări frecvente
Ce este căutarea în adâncime?
Un mod de a explora un graf pornind dintr-un nod de start: urmează un drum cât de adânc se poate și se întoarce să încerce altă ramură doar când nu mai are unde merge. Folosește o stivă, sau recursivitate, pentru a ține minte drumul înapoi.
Găsește căutarea în adâncime cel mai scurt drum?
Nu. Găsește un drum până la țintă, dacă există, dar acesta poate fi mult mai lung decât e nevoie, pentru că DFS se ține de prima ramură pe care o încearcă. Folosiți căutarea în lățime pentru cele mai puține muchii sau algoritmul lui Dijkstra când muchiile au lungimi.
Care este diferența dintre DFS și BFS?
Căutarea în adâncime folosește o stivă și merge adânc pe un drum înainte să se întoarcă. Căutarea în lățime folosește o coadă și se extinde uniform, inel cu inel. Amândouă vizitează fiecare nod accesibil într-un timp care crește cu numărul de noduri plus muchii; BFS găsește drumuri minime, iar DFS este alegerea firească pentru cicluri, labirinturi și sortare topologică.
Cum găsește DFS un ciclu?
Într-un graf neorientat, dacă căutarea întâlnește o muchie spre un nod aflat încă pe stivă, iar acel nod nu este cel din care tocmai a venit, muchia închide o buclă. În aplicație, linia de stare vă spune când se întâmplă asta.
Este graful meu trimis undeva?
Nu. Graful este creat și parcurs în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor