Kruskalov algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

V podčlanku /NeznanAvtor najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Kruskalov algoritem je algoritem, ki se uporablja za iskanje najcenejšega vpetega drevesa v omrežju (minimalno vpeto drevo). Drevo začnemo graditi iz najcenejše povezave, ki je že sama zase vpeto drevo in nato iščemo naprej najcenejše povezave, dokler nimamo celega vpetega devesa (pri tem smo pozorni, da ne pride do cikla).


Vsebina

Algoritem

  • Uredimo povezave po velikosti od največje do najmanjše.
  • Začnemo z najcenejšo povezavo.
  • Dokler ne dodamo n-2 vozlišč ponavljamo:
    • Trenutno povezavo dodamo v drevo, če s tem ne naredimo cikla. (To je osnovni korak). Če sta dve povezavi z enakimi cenami, izberemo tisto, katera ne naredi cikla. Če nobena povezava ne naredi cikla, ni pomembno katero izberemo.
    • To povezavo dodamo in ponavljamo, dokler nam ostane še kaj prostih vozlišč.


Časovna zahtevnost

Kruskalov algoritem se odvija v O(ElogE) času, kjer je E število povezav in V število vozlišč. Oziroma v O(ElogV) času, kar je ekvivalentno:

E je največ V2 in logV2 = 2logV, kar je O(logV).

Primer

Sprogramiraj Kruskalov algoritem v Mathematici. Sprogramiraj in uporabi podatkovno strukturo Union Find.

Glej rešitev:

Zgled z grafom

Slika: Kruskalov.jpg

Glej tudi

Zunanje povezave

- v angleščini:

Osebna orodja