1
1. Ce este DFS si ideea de baza
DFS (Depth-First Search) = parcurgere in adancime: din nodul curent, mergem cat mai departe pe un drum pana nu mai putem continua, apoi revenim si exploram alta ramura.
Analogie: explorarea unui labirint pe hartie
Tii o evidenta a nodurilor vizitate cu un creion. Alegi un drum si mergi pe el cat mai departe, marcand fiecare nod. Cand ajungi la un nod fara iesiri noi, te intorci si iei urmatorul drum neexplorat.
Idei cheie:
- Fiecare nod este vizitat exact o data (marcam cu
vizitat[]) - Implementare iterativa: folosim o stiva (LIFO)
- Implementare recursiva: stiva de apeluri a programului joaca rolul stivei
- Complexitate: O(V + E) unde V = nr. noduri, E = nr. muchii
Graful folosit in toata lectia (6 noduri, 6 muchii)
# Noduri: 0, 1, 2, 3, 4, 5 # Muchii: 0-1, 0-2, 1-3, 1-4, 2-5, 4-5 # 0 # / \ # 1 2 # / \ \ # 3 4---5
2
2. DFS iterativ in Python (cu stiva)
# DFS iterativ - Python graf = { 0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1, 5], 5: [2, 4] } def dfs_iterativ(graf, start): vizitat = set() stiva = [start] ordine = [] while stiva: nod = stiva.pop() # scoatem din varful stivei if nod not in vizitat: vizitat.add(nod) ordine.append(nod) # punem vecinii in ordine INVERSA # ca sa ii procesam in ordine crescatoare for vecin in sorted(graf[nod], reverse=True): if vecin not in vizitat: stiva.append(vecin) return ordine rezultat = dfs_iterativ(graf, 0) print("Ordine DFS (iterativ, start=0):", rezultat)
Output real (rulat cu python):
Ordine DFS (iterativ, start=0): [0, 1, 3, 4, 5, 2]
Urmarire pas cu pas (primii 4 pasi)
Stiva initiala: [0]
Pas 1: scoatem 0, vizitat={0}, punem [2,1] -> stiva=[2,1]
Pas 2: scoatem 1, vizitat={0,1}, punem [4,3] -> stiva=[2,4,3]
Pas 3: scoatem 3, vizitat={0,1,3}, niciun vecin nou -> stiva=[2,4]
Pas 4: scoatem 4, vizitat={0,1,3,4}, punem [5] -> stiva=[2,5]
...
3
3. DFS recursiv in Python
Varianta recursiva este mai eleganta. Stiva este gestionata implicit de stiva de apeluri a programului: fiecare apel
dfs(vecin) creeaza un nou cadru pe stiva sistemului.
# DFS recursiv - Python graf = { 0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1, 5], 5: [2, 4] } def dfs_recursiv(graf, nod, vizitat=None, ordine=None): if vizitat is None: vizitat = set() ordine = [] vizitat.add(nod) ordine.append(nod) for vecin in sorted(graf[nod]): if vecin not in vizitat: dfs_recursiv(graf, vecin, vizitat, ordine) return ordine print("Ordine DFS (recursiv, start=0):", dfs_recursiv(graf, 0))
Output real (rulat cu python):
Ordine DFS (recursiv, start=0): [0, 1, 3, 4, 5, 2]
Arborele de apeluri recursive
dfs(0)
dfs(1) <- primul vecin al lui 0
dfs(3) <- primul vecin al lui 1
<return> <- 3 fara vecini nevizitati
dfs(4) <- al doilea vecin al lui 1
dfs(5) <- vecinul nevizitat al lui 4
dfs(2) <- via 5
<return>
<return>
<return>
<return>
<return>
4
4. DFS recursiv in C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
La profilul intensiv implementam DFS si in C++. Diferente fata de Python: lista de adiacenta se declara ca vector<int> adj[NMAX], vectorul viz[] e de obicei global, tipurile se declara explicit, fiecare instructiune se termina cu ;.
#include <iostream> #include <vector> #include <algorithm> using namespace std; int n = 6; vector<int> adj[6]; bool viz[6]; void dfs(int nod) { viz[nod] = true; cout << nod << " "; for (int vecin : adj[nod]) if (!viz[vecin]) dfs(vecin); } int main() { adj[0] = {1, 2}; adj[1] = {0, 3, 4}; adj[2] = {0, 5}; adj[3] = {1}; adj[4] = {1, 5}; adj[5] = {2, 4}; for (int i = 0; i < n; i++) sort(adj[i].begin(), adj[i].end()); cout << "DFS recursiv (start=0): "; dfs(0); cout << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
DFS recursiv (start=0): 0 1 3 4 5 2
Acelasi algoritm, acelasi rezultat. In C++ vectorul viz[] e un array global simplu, iar dfs() apeleaza recursiv pentru fiecare vecin nevizitat.
5
5. Aplicatie: Detectia ciclurilor cu DFS
In timpul DFS, daca gasim un vecin deja vizitat care nu este parintele nodului curent, am gasit un ciclu.
# Detectie ciclu cu DFS - Python def are_ciclu(graf, n): vizitat = [False] * n def dfs(nod, parinte): vizitat[nod] = True for vecin in graf[nod]: if not vizitat[vecin]: if dfs(vecin, nod): return True elif vecin != parinte: # vizitat si nu parinte = ciclu! return True return False for i in range(n): if not vizitat[i]: if dfs(i, -1): return True return False g1 = {0:[1], 1:[0,2], 2:[1,3], 3:[2]} # lant, fara ciclu g2 = {0:[1,2], 1:[0,2], 2:[1,0]} # triunghi, cu ciclu print("Graf 0-1-2-3 are ciclu?", are_ciclu(g1, 4)) print("Graf 0-1-2-0 are ciclu?", are_ciclu(g2, 3))
Output real (rulat cu python):
Graf 0-1-2-3 are ciclu? False Graf 0-1-2-0 are ciclu? True
De ce excludem parintele?
In graful neorientat, muchia 0-1 exista si ca 1-0. Cand suntem in nodul 1 (venind din 0), nodul 0 este deja vizitat dar este parintele nostru, deci nu este ciclu real. Ciclul apare doar daca gasim alt nod vizitat, diferit de parinte.
6
6. Aplicatie: Numara componentele conexe
Un singur apel DFS pornit dintr-un nod viziteaza toata componenta conexa care contine acel nod. Dupa DFS, nodurile nevizitate apartin altor componente.
# Componente conexe cu DFS - Python def componente_conexe(graf, n): vizitat = [False] * n componente = [] def dfs(nod, comp): vizitat[nod] = True comp.append(nod) for vecin in sorted(graf.get(nod, [])): if not vizitat[vecin]: dfs(vecin, comp) for i in range(n): if not vizitat[i]: # nod nevizitat = noua componenta comp = [] dfs(i, comp) componente.append(comp) return componente # Graf cu 2 componente: {0,1,2} si {3,4} graf = {0:[1,2], 1:[0,2], 2:[0,1], 3:[4], 4:[3]} print("Componente conexe:", componente_conexe(graf, 5))
Output real (rulat cu python):
Componente conexe: [[0, 1, 2], [3, 4]]
Complexitate DFS - rezumat
Timp: O(V + E) - fiecare nod e vizitat o data (V), fiecare muchie e examinata de doua ori la grafuri neorientate.
Spatiu: O(V) - pentru vectorul vizitat + stiva de apeluri recursive (profunda maxim V in cazul unui graf-lant).