Kruskalov algoritem/NeznanAvtor

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Ta članek je treba združiti s člankom Kruskalov algoritem.


Pri Kurskalovem algoritmu povežemo tisti vpeti drevesi, ki ju je najceneje povezati.
Kruskalov algoritem gradi minimalno vpeto drevo. (Že samo vozlišče je eno drevo.) Drevo gradi po korakih. Začne graditi iz najcenejše povezave. V enem koraku algoritem združi dve minimalni vpeti drevesi v eno minimalno vpeto drevo, tako da uporabi minimalno povezavo med dvema vpetima drevesoma. Pri tem moramo paziti, da se ne zaciklamo. V povezanem grafu Kruskalov algoritem zaporedoma združi vsa vpeta drevesa v eno minimalno vpeto drevo.

Vsebina

Postopek

Podan je povezan graf G = (V,E) in cene povezav w (funkcija, ki slika iz množice E v množico pozitivnih realnih števil). Poiščemo minimalno vpeto drevo T:

  1. Naj bo graf T prazna množica in naj bo sako v iz V vozlišče drevesa D(v). Vozlišča razvrstimo po naraščujočem vrstnem redu, glede na ceno povezave w (od najcenejše od najdražje povezava).
  2. Za vsako povezavo w(u, v) (u je vozlišče) po vrsti pogledamo ali sta si množici D(u) in D(v) že tuji. Če sta si množici tuji, dodamo obe vozlišči v množico T, ter napravimo unijo množic D(u) D(v).
  3. Ko so vsa vozlišča v T, smo končali.

Časovna in prostorska zahtevnost algoritma

Časovna zahtevnost

Prebrati moramo zgornji trikotnik matrike n*n brez diagonale - to je n*(n-1)/2 operacij in jih preložiti v tabelo - še n*(n-1)/2 prelaganj. Če izločimo neskončne povezave, je prelaganj manj. Preurejanje tabele v kopico nas stane m*log m, kjer je m število povezav, to je nekje med n in n*(n-1)/2. Sledi sam postopek: Najcenejšo povezavo - vrhKopice - najdemo v konstantnem času, nato je treba popraviti kopico - log m in preveriti dopustnost izbrane povezave - pregled tabele prinese n operacij. V n korakih je to skupaj O(n*n). Pri zelo polnih tabelah je torej najdražje zlaganje kopice: če je m blizu n2, je to O(n2log n), če je graf bolj "prazen" - povezav je le malo več kot vozlišč - pa nas kopica stane samo O(n log n). Vsekakor se izplača takoj na začetku izločiti "neskončne" povezave, pri velikih matrikah to lahko opazno poceni postopek. Skupna časovna zahtevnost je torej najmanj O(n2) in največ O(n2 log n).

Za primerjavo: Primov algoritem, ki shaja brez kopice, ima vedno T(n) = O(n2). Za grafe z malo povezavami je boljši od Kruskalovega, pri polnih grafih pa ga ta prehiti (vir: J. Kozak).

Prostorska zahtevnost

Poleg matrike povezav potrebujemo še tabelo za kopico, ki je dolga m = n*(n-1)/2 ne glede na dejansko število povezav in tabelo poddreves dolžine n ter matriko velikosti m * 3 za rešitev. Vse skupaj je torej O(n2).

V analizi ni upoštevano risanje grafa, ki seveda najbolj podraži postopek - časovno in prostorsko.

Če bi se odločili za drugačno predstavitev poddreves, bi potrebovali n matrik dolžine n, torej smo prostorsko še vedno na O(n2). Časovno zahtevnost bi malo skrajšali. Verjetno se pri zelo polnih matrikah to ne izplača, ker je T(n) več kot kvadratna. Če pa je povezav malo in je T(n) samo O(n log n), bi morda veljalo poskusiti.


Primer

Slikovni prikaz iskanja minimalno vpetega drevsa

Slikovni primer iskanja minimalno vpetega drevesa z najcenejšimi povezavami po Kruskalovem algoritmu.

Slika: Kruskalov.jpg


Implementacija

Osebna orodja