Căutare în adâncime (DFS)
Explorează un graf urmând un drum cât de adânc se poate, apoi se întoarce la ultima ramificație. Stiva de pe ecran este chiar acel drum.
- timp O(V + E)
- memorie O(V)
- folosește o stivă
Ce înseamnă acești termeni?
- Nod: un punct al grafului, desenat aici ca un cerc cu o literă.
- Muchie: o linie care unește două noduri. Aici o poți parcurge în ambele sensuri.
- Vecini: nodurile legate de un nod printr-o muchie. Sunt verificați în ordine alfabetică.
- Coadă: primul intrat, primul ieșit. BFS ia mereu nodul care a așteptat cel mai mult.
- Stivă: ultimul intrat, primul ieșit. DFS continuă mereu din nodul la care a ajuns ultima dată.
- V și E: numărul de noduri (vertices) și de muchii (edges). O(V + E) înseamnă că fiecare nod și fiecare muchie sunt tratate de un număr fix de ori.
- pe stivă
- curent
- gata
- muchie din arborele de căutare
- muchie sărită
Începe de la A. Apasă pe redare sau parcurge căutarea pas cu pas.
Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.
Încearcă: Alege graful cu cicluri. Fiecare muchie cu linie întreruptă duce înapoi la un nod care e deja pe stivă sau e gata: acea muchie închide un ciclu.
Cum funcționează
DFS se apelează pe sine pentru primul vecin pe care nu l-a văzut încă, apoi pentru primul vecin nou al acestuia și așa mai departe. Când un nod nu mai are vecini noi, apelul lui se încheie, iar DFS se întoarce un pas ca să încerce acolo următorul vecin. Apelurile deschise formează o stivă, care e mereu drumul de la start la nodul curent. Numărul de lângă un nod arată în ce ordine a fost vizitat.
Când este o alegere bună
Folosește DFS ca să afli la ce se poate ajunge, ca să găsești cicluri, ca să treci printr-un labirint sau ca să pui în ordine sarcini care depind unele de altele. Nu găsește drumul cel mai scurt.