Algoritmul lui Kruskal
Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat. Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului. Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de algoritm greedy.
Algoritmul funcționează în felul următor:
- creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat
- creează o mulțime S care conține toate muchiile din graf
- atât timp cât S este nevidă
- elimină o muchie de cost minim din S
- dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur
- altfel, ignoră muchia
La sfârșitul algoritmului, pădurea are doar o componentă care reprezintă un arbore parțial de cost minim al grafului.
Acest algoritm a fost scris de Joseph Kruskal, în 1956.
Alți algoritmi pentru această problemă sunt Algoritmul lui Prim și Algoritmul lui Borůvka.
Exemplu modificare
|
Acesta este graful original. Numerele de pe muchii reprezintă costul acestora. Nici o muchie nu este evidențiată. |
|
AD și CE sunt cele mai scurte muchii, de cost 5, iar AD a fost arbitrar aleasă, deci este evidențiată. |
|
CE este muchia de cost minim care nu formează un ciclu, deci este evidențiată. |
|
Următoarea muchie, DF, de cost 6, este evidențiată în același fel. |
|
Următoarele muchii de cost minim sunt AB și BE, de cost 7. AB este aleasă arbitrar și este evidențiată. Muchia BD este marcată cu roșu, deoarece ar forma ciclul ABDA dacă ar fi aleasă. |
|
Procesul continuă cu evidențierea următoarei muchii, BE, de cost 7. Mai multe muchii sunt marcate cu roșu la acest pas: BC, deoarece ar forma ciclul BCEB, DE, deoarece ar forma ciclul DEBAD și FE deoarece ar forma ciclul FEBADF. |
|
În sfârșit, procesul se încheie cu muchia EG de cost 9, iar arborele parțial de cost minim este găsit. |
Pseudocod modificare
1 funcția Kruskal(G)
2 pentru fiecare vârf v în G execută
3 Definește un grup elementar C(v) ← {v}.
4 Creează o coadă cu priorități Q care conține muchiile din G, având costul drept cheie.
5 Definește un arbore T ← Ø //T va conține în final toate muchiile din APCM
6 // n este numărul total de vârfuri
7 cât timp T are mai puțin de n-1 muchii execută
8 // muchia u,v este drumul minim de la u la v
9 (u,v) ← Q.eliminăMin()
10 Fie C(v) grupul care îl conține pe v și C(u) grupul care îl conține pe u.
11 dacă C(v) ≠ C(u) atunci
12 Adaugă muchia (v,u) la T.
13 Unește C(v) și C(u) într-un grup, adică reuniune între C(v) și C(u).
14 returnează arborele T