Pe scurt
Algoritmii pe grafuri sunt esențiali pentru rezolvarea problemelor de drumuri minime și conectare optimă în rețele. Dijkstra găsește drumul minim de la o sursă la toate nodurile (cu ponderi nenegative), Kruskal determină arborele parțial de cost minim, iar Floyd-Warshall calculează distanțele între toate perechile de noduri (inclusiv cu ponderi negative, fără cicluri negative). Acești trei algoritmi sunt fundamentali pentru Bacalaureat, fiind testați atât ca implementare, cât și ca analiză de complexitate.
Ce este un graf și de ce avem nevoie de algoritmi pe grafuri
Teoria grafurilor reprezintă un capitol fundamental în informatica de liceu și Bacalaureat. Un
graf este o structură compusă din
noduri (vârfuri) și
muchii (arce) care leagă nodurile. Algoritmii pe grafuri rezolvă probleme practice: drumuri minime, costuri minime de conectare, rutare în rețele etc.
Algoritmul lui Dijkstra – drumul minim dintr-o sursă
Algoritmul lui
Dijkstra găsește drumul de cost minim de la un nod sursă la toate celelalte noduri, într-un graf orientat sau neorientat, cu
ponderi nenegative.
- Principiul: se menține o mulțime de noduri vizitate și la fiecare pas se selectează nodul nevizitat cu distanța minimă față de sursă, actualizând distanțele vecinilor săi.
- Complexitatea: O((N+M) log N) cu heap sau O(N²) în implementare simplă.
- Condiții de aplicabilitate: nu funcționează cu ponderi negative.
Exemplu Dijkstra
Avem un graf cu 5 noduri și muchiile: (1-2, cost 10), (1-3, cost 3), (2-3, cost 1), (2-4, cost 2), (3-4, cost 8), (3-5, cost 2), (4-5, cost 9). Sursa: nod 1.
- Pas 1: dist[1]=0, dist[2]=inf, dist[3]=inf, dist[4]=inf, dist[5]=inf. Selectăm nod 1, actualizăm vecinii: dist[2]=10, dist[3]=3.
- Pas 2: selectăm nod 3 (minim nevizitat), actualizăm: dist[2]=min(10, 3+1)=4, dist[4]=3+8=11, dist[5]=3+2=5.
- Pas 3: selectăm nod 2 (dist=4), actualizăm: dist[4]=min(11, 4+2)=6.
- Pas 4: selectăm nod 5 (dist=5), vecinii: dist[4]=min(6,5+9)=6.
- Pas 5: selectăm nod 4 (dist=6).
Rezultă distanțele minime: 1->2=4, 1->3=3, 1->4=6, 1->5=5.
Algoritmul lui Kruskal – arborele parțial de cost minim
Algoritmul lui
Kruskal determină
arborele parțial de cost minim (minimum spanning tree) într-un graf neorientat, ponderat.
- Principiul: se sortează muchiile crescător după cost și se adaugă muchia la arbore doar dacă nu creează ciclu (se verifică cu Union-Find).
- Complexitatea: O(M log M).
- Union-Find: structură pentru mulțimi disjuncte, operații de find și union cu compresie de cale și uniune după rang.
Exemplu Kruskal
Graf cu 6 noduri, muchii: (1-2, 4), (1-3, 2), (2-3, 5), (2-4, 3), (3-4, 1), (3-5, 6), (4-5, 7), (4-6, 8), (5-6, 9).
- Sortăm muchiile: (3-4,1), (1-3,2), (2-4,3), (1-2,4), (2-3,5), (3-5,6), (4-5,7), (4-6,8), (5-6,9).
- Aplicăm Union-Find: adăugăm 3-4 (cost 1), adăugăm 1-3 (cost 2), adăugăm 2-4 (cost 3) – acum avem componentele {1,2,3,4}.
- Următoarea muchie 1-2 (cost 4) ar crea ciclu (1 și 2 sunt deja în aceeași componentă), deci o sărim.
- Următoarea 2-3 (cost 5) creează ciclu, sărim.
- Adăugăm 3-5 (cost 6) – componenta {1,2,3,4,5}.
- Adăugăm 4-5 (cost 7) – ciclu, sărim.
- Adăugăm 4-6 (cost 8) – componenta finală {1,2,3,4,5,6}.
- Oprim după 5 muchii (N-1). Cost total = 1+2+3+6+8 = 20.
Algoritmul Floyd-Warshall – drumuri minime între toate perechile
Algoritmul
Floyd-Warshall calculează drumurile minime între
toate perechile de noduri dintr-un graf (dreptunghiular sau orientat) cu ponderi care pot fi
negative (dar fără cicluri negative).
- Principiul: se bazează pe programare dinamică – matricea distanțelor se actualizează iterativ, la pasul k, considerând dacă drumul trece prin nodul k.
- Complexitatea: O(N³).
- Detectarea ciclurilor negative: se verifică pe diagonala principală (dacă dist[i][i] < 0).
Exemplu Floyd-Warshall
Graf orientat cu 3 noduri, matricea distanțelor inițială: dist[1][1]=0, dist[1][2]=5, dist[1][3]=inf, dist[2][1]=inf, dist[2][2]=0, dist[2][3]=-2, dist[3][1]=3, dist[3][2]=inf, dist[3][3]=0.
- Pas k=1: pentru toate i,j, dacă dist[i][1]+dist[1][j] < dist[i][j] actualizăm. De exemplu, dist[3][2]=min(inf, 3+5)=8, dist[3][3]=min(0, 3+inf)=0.
- Pas k=2: verificăm prin nod 2: dist[1][3]=min(inf, 5+(-2))=3, dist[3][1]=min(3, 8+inf)=3.
- Pas k=3: verificăm prin nod 3: dist[1][2]=min(5, 3+inf)=5, dist[2][1]=min(inf, -2+3)=1, dist[2][2]=min(0, -2+inf)=0, dist[3][2]=min(8, 0+inf)=8.
Matricea finală: dist[1][2]=5, dist[1][3]=3, dist[2][1]=1, dist[2][3]=-2, dist[3][1]=3, dist[3][2]=8. Se observă că nu există cicluri negative deoarece diagonala rămâne 0.
Reprezentări ale grafurilor și aplicații
Grafurile pot fi reprezentate prin:
- Matrice de adiacență (cu ponderi) – utilizată pentru Floyd-Warshall
- Liste de adiacență – eficient pentru grafuri rare, utilizat pentru Dijkstra și Kruskal
În probleme tip Bac, acești algoritmi se folosesc pentru
- Dijkstra – probleme cu drum minim într-un oraș
- Kruskal – conectarea localităților cu cost minim
- Floyd-Warshall – precalcularea distanțelor între toate punctele
Atenție la condițiile de aplicabilitate: Dijkstra eșuează la ponderi negative; Floyd-Warshall detectează cicluri negative pe diagonala principală. Pentru Bac, se recomandă memorarea pseudocodurilor și a exemplelor clasice.
Verifică-te!
- Care este complexitatea algoritmului lui Dijkstra în implementarea cu heap?
- Ce structură de date se folosește în algoritmul lui Kruskal pentru a verifica dacă o muchie creează ciclu?
- Cum se detectează prezența unui ciclu negativ în algoritmul Floyd-Warshall?