Opis postopka
Kruskalov algoritem uporablja požrešno metodo:
rešitev gradimo korakoma in na vsakem koraku dodamo naslednjo najcenejšo dopustno povezavo.
Končno rešitev sestavlja seznam n-1 povezav.
Torej takole:
-
Začnemo z n posameznimi vozlišči.
-
Izberemo najcenejšo povezavo.
-
Izberemo drugo najcenejšo povezavo.
-
itd.
Na i-tem koraku:
-
Izberemo najcenejšo še neizbrano povezavo.
-
Pogledamo, ali je dopustna: če sta krajišči te povezave že povezani,
je ne smemo izbrati, ker bi dobili cikel; rešitev pa mora biti drevo (graf brez ciklov).
-
Če vozlišči še nista povezani, povezavo dodamo k rešitvi in označimo, katera vozlišča so na
novo povezana.
Postopek ponavljamo, dokler nimamo n-1 povezav - število korakov torej vemo že v začetku.
Ves čas moramo voditi evidenco o tem, katere povezave smo že izbrali oziroma katera
vozlišča so že povezana.