Algoritmul lui Kruskal
De la Wikipedia, enciclopedia liberă
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 reprezină 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.
Cuprins |
[modifică] Exemplu
 |
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 ABD dacă ar fi aleasă. |
 |
Procesul continuă cu evidenţiarea următoarei muchii, BE, de cost 7. Mai multe muchii sunt marcate cu roşu la acest pas: BC, deoarece ar forma ciclul BCE, DE, deoarece ar forma ciclul DEBA şi FE deoarece ar forma ciclul FEBAD. |
 |
În sfârşit, procesul se încheiecu muchia EG de cost 9, iar arborele parţial de cost minim este găsit. |
[modifică] Pseudocod
1 function Kruskal(G)
2 for each vârf v în G do
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 while T are mai puţin de n-1 muchii do
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 if C(v) ≠ C(u) then
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 return arborele T
[modifică] Vezi şi
- Algoritmul lui Prim
- Algoritmul lui Borůvka
- Algoritmul lui Dijkstra
