Algoritmul lui Kruskal

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

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 | modificare sursă]

Prim Algorithm 0.svg Acesta este graful original. Numerele de pe muchii reprezintă costul acestora. Nici o muchie nu este evidențiată.
Kruskal Algorithm 1.svg AD și CE sunt cele mai scurte muchii, de cost 5, iar AD a fost arbitrar aleasă, deci este evidențiată.
Kruskal Algorithm 2.svg CE este muchia de cost minim care nu formează un ciclu, deci este evidențiată.
Kruskal Algorithm 3.svg Următoarea muchie, DF, de cost 6, este evidențiată în același fel.
Kruskal Algorithm 4.svg 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ă.
Kruskal Algorithm 5.svg 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.
Kruskal Algorithm 6.svg Î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 | modificare sursă]

 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

Vezi și[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]