Joseph Kruskal s-a născut la New York în 29 ianuarie 1928 si a decedat în 19 septembrie 2010. A fost un american matematician, statiscian, om de știință în domeniul calculatoarelor. El a trăit 82 de ani și a scris algoritmul în 1956.
Este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat (graf în care fiecare muchie are asociat un cost). 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 un arbore parțial de cost minim pentru fiecare componentă conexă. Algoritmul lui Kruskal este un exemplu de algoritm greedy.
Descrierea algoritmului:
- se ordonează muchiile grafului după cost
- se pornește în construire de la graful parțial care conține toate nodurile izolate
- se adaugă pe rând n-1 muchii în graf (în ordinea crescătoare a costurilor) urmărind ca fiecare muchie adăugată să nu formeze un ciclu
Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă.
Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim.
Algoritmul lui Kruskal permite determinarea unui arbore parțial de cost minim (APM) într-un graf ponderat cu N noduri.
Acesta este graful original. Numerele de pe muchii reprezintă costul acestora. Nici o muchie nu este evidențiată.
Intrare: Un graf conex neorientat G cu ponderile c: E(G) - R.
Ieșire: Un arbore indus T cu pondere minimă.
(1) Sortați muchiile astfel încât c(e1) ≤ c(e2) ≤ ... ≤ c(em).
(2) Setați T: = (V (G), ∅).
(3) Pentru i: = 1 până la m faceți:
Dacă T + ei nu conține niciun circuit, atunci setați T: = T + ei.
Teorema 3. Algoritmul lui Kruskal funcționează corect.
Este clar că algoritmul construiește un arbore T indus. De asemenea, garantează condiția (b) a teoremei 2, deci T este optimă.
Durata de funcționare a algoritmului lui Kruskal este O (mn): muchiile pot fi sortate în timp O (m log m) (teorema 1.5) și testarea unui circuit într-un graf cu cel mult n muchii poate fi implementat în O(n) timp (aplicați doar DFS (sau BFS) și verificați dacă există vreo muchie care nu aparține arborelui DFS). Deoarece acest lucru se repeat m ori, obținem un timp total de funcționare de O (m log m + mn) = O (mn). Cu toate acestea, este posibilă o implementare mai eficientă:
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
