Kruskalov postopek

Iz MaFiRaWiki

S pomočjo Kruskalovega postopka iščemo minimalna vpeta drevesa v neusmerjenem grafu. Kruskalov postopek deluje tako, da začnemo z najcenejšo povezavo v grafu in jo označimo. Nato označimo še vse preostale povezave s to ceno, tako da ne naredimo cikla. Potem izmed preostalih povezav zopet izberemo najcenejšo povezavo in jo dodamo. Povezave dodajamo tako, da imamo na koncu povezana vsa vozlišča in da ne dobimo cikla. Torej imamo na tekočem koraku nekaj minimalnih vpetih dreves (posamezno vozlišče je tudi minimalno vpeto drevo). Če povzamemo razlago, povežemo tisti vpeti drevesi, ki ju je najceneje povezati.

Članek je že objavljen pod drugim naslovom:

Kruskalov algoritem

Osebna orodja