Kruskalov algoritam

Kruskalov algoritam je pohlepni algoritam koji pronalazi minimalno razapinjuće stablo za povezani težinski graf. Ovo znači da pronalazi podskup grana koje sadrže sve čvorove, tako da je ukupna težina svih grana u stablu minimalna. Ako graf nije povezan, onda pronalazi minimalnu razapinjuću šumu (minimalno razapinjuće stablo za svaku komponentu povezanosti).

Ovaj algoritam se prvi put javlja u Proceedings of the American Mathematical Society, Džozefa Kruskala, 1956. godine.

Drugi algoritmi za ovaj problem uključuju Primov algoritam, Obrnuto-Brisanje i Boruvka alogritam.

Opis

• Napravi šumu F (skup stabala), gde je svaki čvor u grafu posebno stablo.
• Napravi skup S koji sadrži sve grane u grafu.
• Dok je S neprazno i F još uvek nije razapinjuće:
  • ukloni granu najmanje težine iz S;
  • ako grana povezuje dva različata stabla, dodaj je u šumu, kombinujući dva stabla u jedno;
  • inače, odbaci tu granu.

Na kraju algoritma, šuma formira minimalno razapinjuće stablo od grafa. Ako je graf povezan, šuma ima jednu komponentu i formira minimalno razapinjuće stablo.

Pseudokod

Naredni kod je implementiran korišćenjem strukture razdvojenih skupova:

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

Složenost

Ako je E broj grana u grafu i V broj čvorova, za Kruskalov algoritam se može pokazati da se izvršava u vremenskoj složenosti O(E log E) ili ekvivalentnoj O(E log V), sve za jednostavne strukture podataka. Ova vremena izvršavanja su ekvivalentna zato što:

• E je najviše V² i $\log V^{2}=2\log V$ $\;$ je O(log V).
• Svaki izolovani čvor je odvojena komponenta minimalne razapinjuće šume. Ako ignorišemo izolovane čvorove dobijamo V ≤ E+1, pa log V je O(log E).

Možemo da postignemo ovu granicu na sledeći način: prvo sortiramo čvorove po težini koristeći sortiranje poređenjem (eng. comparison sort) i vreme O(E log E); ovo dopušta korak „ukloni granu sa minimalnom težinom iz S“ da bismo operisali u konstantnom vremenu. Sledeće, koristimo strukturu razdvojenih skupova da bismo sačuvali evidenciju koji čvorovi su u kojim komponentama. Potrebno je da izvršimo O(E) operacija u O(E log V) vremenu. Dovde je ukupno vreme O(E log E) = O(E log V).

Ako obezbedimo da su grane ili već sortirane ili da mogu da budu sortirane za linearno vreme (npr. korišćenjem counting sort-a ili radiks sorta, algoritam može da koristi prefinjeniju strukturu razdvojenih skupova, kako bi se izvršavao u O(E α(V)) vremenu, gde je α ekstremno sporo rastući inverz Akermanove funkcije sa jednom vrednošću.

Primer

Slika	Opis
	AD i CE su najkraće grane, dužine 5 i AD je proizvoljno izabrana, pa je označena.
	CE je sada najkraća grana koja ne formira cikl, sa dužinom 5, pa je označena kao druga grana.
	Sledeća grana, DF sa dužinom 6, označena je koristeći isti metod.
	Naredne najkraće grane su AB i BE, obe dužine 7. AB je proizvoljno izabrana i označena. Grana BD je označena crvenom bojom, jer već postoji put (zelene boje) između B i D, pa bi formirala cikl (ABD) da je izabrana.
	Proces se nastavlja za narednu najkraću granu BE sa dužinom 7. Još dosta grana je označeno crvenom bojom u ovom trenutku: BC jer bi formirala petlju BCE, DE jer bi formirala petlju DEBA i FE jer bi formirala FEBAD.
	Najzad, proces se završava sa granom EG dužine 9 i pronađeno je minimalno razapinjuće stablo.

Dokaz korektnosti

Dokaz se sastoji iz dva dela. Prvo, dokazuje se da algoritam proizvodi povezujuće stablo. Drugo, dokazuje se da je konstruisano povezujuće stablo minimalne težine.

Povezujuće stablo

Neka je $P$ povezan, težinski graf i neka je $Y$ podgraf od $P$, dobijen algoritmom. $Y$ ne može da ima cikl, jer bi poslednja dodata grana bila podstablo, a ne između dva različita stabla. $Y$ ne može biti nepovezan, jer bi prva grana na koju naiđemo, a koja spaja dve komponente iz $Y$, bila dodata algoritmom. Prema tome, $Y$ je povezujuće stablo od $P$.

Minimalnost

Pokazujemo da je naredna pretpostavka P tačna indukcijom: ako je F skup grana izabranih u bilo kom stadijumu algoritma, onda postoji minimalno razapinjuće stablo koje sadrži F.

• Očigledno, P je tačno na početku, kada je F prazno: bilo koje minimalno razapinjuće stablo će biti, a postoji jedno, jer težinski povezani graf uvek ima minimalno razapinjuće stablo.
• Sada pretpostavimo da je P tačno za neki beskonačan skup F i neka je T minimalno razapinjuće stablo koje sadrži F. Ako je naredna izabrana grana e takođe u T, onda je P tačno za F + e. Inače, T + e ima cikl C i postoji još jedna grana f koja je u C, a nije u F. (Da nema takve grane f, e ne bi bila dodata u F, pošto bi se tako kreirao cikl C). Zatim, T - f + e je stablo i ima istu težinu kao T, pošto T ima minimalnu težinu i težina od f ne može biti manja od težine e, inače bi algoritam izabrao f umesto e. Tako je T – f + e minimalno razapinjuće stablo koje sadrži F + e i još jednom, P stoji.
• Zbog toga, po principu indukcije, P stoji kada F postane razapinjuće stablo, što je jedino moguće ako je samo F minimalno razapinjuće stablo.

Vidi još

• Algoritam: Obrnuto-Brisanje
• Dajkstrin algoritam
• Primov algoritam

Reference

• Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.
• Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java, Fourth Edition. John Wiley & Sons, Inc., 2006.