Pe scurt
Un graf neorientat este o pereche G=(V, M) formată din noduri și muchii neordonate. Reprezentarea principală se face prin matricea de adiacență (acces rapid, dar memorie O(n²)) sau lista de adiacență (eficientă pentru grafuri rare, memorie O(n+m)). Parcurgerile BFS (cu coadă) și DFS (cu stivă/recursivitate) sunt algoritmi fundamentali de explorare, având complexitatea O(n+m) și aplicații precum determinarea distanței minime sau a componentelor conexe.
Definiția și reprezentarea grafurilor neorientate
Un graf neorientat este o pereche G=(V, M), unde
- V este o mulțime finită de noduri (vârfuri)
- M este o mulțime de muchii, fiecare muchie fiind o pereche neordonată de noduri distincte
Într-un graf neorientat, muchia (u,v) este identică cu (v,u), iar relația de adiacență este simetrică.
Matricea de adiacență
- Este o matrice pătratică A de dimensiune n x n (n = numărul de noduri)
- A[i][j] = 1 dacă există muchie între nodul i și nodul j, altfel 0
- Avantaj: acces rapid O(1) la verificarea adiacenței
- Dezavantaj: memorie O(n²), ineficientă pentru grafuri rare
Lista de adiacență
- Este un vector de liste (sau vectori) de dimensiune n
- Pentru fiecare nod i se păstrează o listă cu vecinii săi
- Memorie: O(n+m), unde m este numărul de muchii
- Avantaj: eficientă pentru grafuri rare
Exemplu: Reprezentare prin liste de adiacență pentru graful cu 5 noduri (1-2, 1-3, 2-4, 3-5):
- nodul1: [2,3]
- nodul2: [1,4]
- nodul3: [1,5]
- nodul4: [2]
- nodul5: [3]
Matricea de adiacență: o matrice 5x5 cu 1 pe pozițiile (1,2),(1,3),(2,1),(2,4),(3,1),(3,5),(4,2),(5,3), restul 0.
Parcurgerea BFS (Breadth-First Search)
BFS explorează graful pe niveluri, plecând de la un nod sursă
- Vizitează mai întâi toți vecinii direcți
- Apoi vecinii acestora etc.
- Se implementează cu o coadă (queue)
- Este potrivit pentru găsirea celui mai scurt drum în grafuri neponderate
Exemplu: Parcurgere BFS pe un graf cu 5 noduri (1-2, 1-3, 2-4, 3-5):
- Se pornește de la nodul 1: se vizitează nodul 1, se adaugă în coadă
- Se extrag vecinii nevizitați: 2 și 3. Se vizitează 2, apoi 3
- Din coadă, urmează nodul 2 care are vecinii 1 (vizitat) și 4 (nevizitat) - se vizitează 4
- Apoi nodul 3 are vecinii 1 (vizitat) și 5 (nevizitat) - se vizitează 5
Ordinea BFS: 1, 2, 3, 4, 5
Parcurgerea DFS (Depth-First Search)
DFS explorează în profunzime
- Merge cât mai departe pe o ramură
- Apoi se întoarce (backtracking)
- Se implementează recursiv sau cu o stivă
- Este util pentru detectarea ciclurilor, sortare topologică (în grafuri orientate) sau determinarea componentelor conexe
Exemplu: Parcurgere DFS pe același graf
- Pornind de la nodul 1: se vizitează 1, se merge recursiv la un vecin, de exemplu 2
- Din 2 se merge la 4 (nevizitat)
- Din 4 nu mai sunt vecini nevizitați, returnează
- Revenind la 2, nu mai sunt alți vecini, returnează la 1
- Apoi se merge la 3, apoi la 5
Ordinea DFS: 1, 2, 4, 3, 5
Aspecte comune și aplicații
Parcurgerea corectă necesită marcarea nodurilor vizitate pentru a evita bucle infinite.
Complexitatea: Ambele metode au complexitatea O(n+m) la parcurgerea întregului graf.
Diferențe cheie
- BFS folosește coadă și garantează distanța minimă
- DFS folosește stivă/recursivitate și este mai simplu pentru explorare completă
Aplicații la nivel de Bac
- Numărarea componentelor conexe
- Determinarea distanței minime (BFS)
- Verificarea existenței unui drum
Verifică-te!
- Care este diferența principală între matricea de adiacență și lista de adiacență din punctul de vedere al memoriei utilizate?
- În ce ordine sunt vizitate nodurile la parcurgerea BFS față de DFS, pornind de la același nod sursă?
- Ce structură de date se folosește pentru implementarea BFS și ce garanție oferă această parcurgere?