Minimalno vpeto drevo v grafu
Kruskalov algoritem

Avtor: Tatjana Hernaus (Tatjana.Hernaus@guest.arnes.si)

DIRI
Študijsko leto 2004/05
 

Viri:
Jernej Kozak, Podatkovne strukture in algoritmi, DMFA Slovenije, Ljubljana 1986
Zapiski in prosojnice s predavanj, Matija Lokar

Naj bo G povezan neusmerjen graf z uteženimi povezavami. Radi bi našli tako vpeto drevo, da bo vsota cen povezav v tem vpetem drevesu minimalna. Eden izmed algoritmov za reševanje tega problema je Kruskalov algoritem (J. B. Kruskal, njegova domača stran). Rešitev gradimo po korakih, na vsakem koraku dodamo novo povezavo. Problema se lotimo "na požrešen način": vedno izberemo najcenejšo povezavo, ki je še na voljo. Pri tem pazimo le, da ne dobimo cikla.

Najprej sem sestavila razred Kopica.
Kopico sem predstavila s tabelo. Ker pa potrebujemo za vsak element tabele tri podatke (ceno povezave in njeni krajišči), je tabela pravzaprav matrika m*3, kjer je m število elementov.

Konstruktorji:
Poleg osnovnega Kopica(int m), ki naredi prazno tabelo dolžine m, je v razredu še konstruktor Kopica(int[][] matrika), ki elemente dane matrike n*n preloži v kopico. Velikost kopice je m = n*(n-1)/2, ker je matrika zgornjetrikotna brez diagonale. Dodala sem še podoben konstruktor public Kopica(int[][] matrika, int neskoncno), ki sproti izloči neskončne povezave, tako je kopica malo manjša in imamo pozneje manj dela.

Metode:

• public int[] povejVrh() - vrne prvi element iz tabele (kopice);
• public int[] povejZadnjega() - vrne zadnji element kopice; potrebujemo ga pri brisanju: zadnjega prestavimo na mesto prvega;
• public void spremeniVrh(int[] podatek) - vstavi nov podatek namesto vrha; vrh pri tem izgubimo!
• public void brisi() - zbriše vrh kopice, na njegovo mesto prestavi zadnji element in ga potopi, do koder je treba, da se ohrani struktura kopice; velikost kopice se zmanjša;
• public void popraviKopico(int k) - potopi k-ti element do koder je treba, deluje rekurzivno;
• public void narediKopico() - dano tabelo preuredi v minimalno kopico;
• public void zamenjaj(int k, int j) - zamenja elementa kopice;
• public int velikost() - vrne velikost kopice;

To so le metode, ki jih potrebujem za rešitev te naloge, nekatere standardne metode, npr. vstaviVkopico(pod), prazna() in podobne manjkajo. Metode so public, čeprav bi vsaj kakšna lahko bila private, denimo popraviKopico().

Rešitev naloge je programček Kruskal.java, ki dela takole.

V programu je nekaj globalnih spremenljivk:

• final int NESKONCNO - konstanta, ki jo dolocimo sami (glede na podatke). Zdi pa se mi, da obstaja v javi celo vrednost infinity (?). Trenutno je vrednost nastavljena na 100.
• boolean nakljucenVnos - uporabnik si izbere način vnosa;
• int n - število vozlišč, izbere ga uporabnik;
• int[][] pov - seznam povezav s cenami in krajišči je tabela m * 3; ko cene povezav zložimo v tabelo, si moramo zapomniti poleg cene tudi krajišči povezave, zato za vsako potrebujemo tri celice;
• int[] poddrevesa - seznam poddreves v gozdu, ki se med postopkom povezujejo v eno samo drevo, tabela dolžine n;
• Kopica kopica - kopica povezav;
• int[][] resitev - "vektor" rešitve je pravzaprav matrika m * 3, ker za vsako povezavo potrebujemo tri podatke, ceno in krajišči;
• static int[] vozY in static int[] vozX - koordinate vozlišč za grafični prikaz rešitve;

Postopek:

• Najprej se odločimo za način branja podatkov in za število vozlišč. Grafična predstavitev deluje, če je vozlišč največ 8.
• Izbiro cen lahko prepustimo računalniku. V tem primeru se lahko zgodi, da graf ne bo povezan - če je preveč povezav "neskončnih". Naključni izbor je nastavljen tako, da je cca. vsak tretja povezava "neskončna", zato težave niso prav pogoste. Program ne preverja, ali je graf povezan, le v primeru, da je povezav manj kot n-1, opozori uporabnika, da rešitev ne bo smiselna.
  Lahko pa povezave vnesemo sami. Preko vnosnega okna vnašamo samo zgornjo trikotno matriko brez diagonale.
• Povezave se nato zložijo v tabelo, ta pa se uredi v minimalno kopico. Pri tem izpustimo neskončne povezave in s tem prihranimo nekaj časa.
• Sledi sam kruskalov postopek: izberemo najcenejšo še neizbrano povezavo, preverimo, ali ne pripelje do cikla, in - če je dopustna - jo dodamo k rešitvi.
• Na koncu se za boljšo predstavo nariše graf in minimalno vpeto drevo v njem, izpiše se tudi seznam povezav v drevesu, in sicer v istem vrstnem redu, kot smo jih dodajali.

Metode:

• int preberi(String niz) - prebere ŠTEVILO (trenutno samo iz vnosnega okna) ali pa ga določi naključno; niz je morebiten komentar za uporabnika
• void branjeMatrike(int[][] matrika) - prebere elemente zgornjetrikotne kvadratne matrike n*n krusk(kopica, n) - to je osrednji del, kruskalov algoritem, rešitev je tabela povezav, ki sestavljajo minimalno vpeto drevo; v tabeli skupaj hranimo cene in krajišča posameznih povezav.
• public static int[][] krusk(Kopica kopica, int n) - izvede kruskalov algoritem na kopici povezav, n je število vozlišč, ne povezav.
• public static boolean dopustna(int[] povezava) - preveri, ali je povezava dopustna - ali sta krajišči še nepovezani; hkrati metoda še združi na novo povezani poddrevesi
• public static void dodaj(int[][] resitev, int i, int[] povezava) - resitvi na mesto z indeksom i doda povezavo
• public static void izpisResitve(Graphics g, int[][] resitev) - na grafično površino izpiše vektor rešitve: povezave in cene, v istem vrstnem redu, kot jih je določil algoritem
• public static void narisiGraf(Graphics g, int[][] pov) - na grafično površino nariše graf, dan z matriko povezav pov
• public static void narisiDrevo(Graphics g, int[][] drevo) - na že narisanem grafu označi minimalno vpeto drevo, povezave dodaja kot v Kruskalovem algoritmu; med posameznimi koraki čaka 1500 milisekund
• public static void narisiVozlisce(Graphics g, int i) - nariše vozlišče i, pozicije vozlišč so fiksirane (tabeli koordinat vozX in vozY)
• public static void narisiPovezavo(Graphics g, int i, int j, int cena) - narise povezavo med i-tim in j-tim vozliščem, njihove pozicije so fiksne - tabeli vozX in vozY
• public static void crta(Graphics g, int x1, int y1, int x2, int y2) - nariše debelejšo črto od A(x1,y1) do B(x2,y2)
• public static void cakaj(int koliko) - kratka prekinitev med koraki (pri risanju) - nastavljena v metodi narisiDrevo

Najprej sem testirala razred Kopica - pričakovala sem težave pri sestavljanju kopice in pri brisanju iz nje (in program je v celoti izpolnil moja pričakovanja :) ). Testni program TestZaKopico.java izpisuje celoten postopek prelaganja elementov za izbran primer. Namesto razreda kopica uporablja razred KopicaTest s testnimi izpisi (v ukazno vrstico, ne na grafično površino).

Program KruskalTest.java pa preverja delovanje samega algoritma: v ukazno vrstico izpiše dano (fiksno) tabelo povezav kot zgornjetrikotno matriko ter spremlja dodajanje povezav in seznam poddreves med postopkom. Tabelo povezav lahko vnesemo prek vnosnega okna ali pa prepustimo izbor računalniku.

Časovna in prostorska zahtevnost algoritma:

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 n², je to O(n²log 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(n²) in največ O(n² log n).

Za primerjavo: Primov algoritem, ki shaja brez kopice, ima vedno T(n) = O(n²). 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(n²).

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 (opisana je tule), bi potrebovali n matrik dolžine n, torej smo prostorsko še vedno na O(n²). Č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.

Problem minimalnega vpetega drevesa ni rešljiv, če graf ni povezan. Program sam tega ne preverja. Če sami vnašamo matriko povezav, moramo poskrbeti za smiselnost podatkov. Če določanje cen prepustimo računalniku, se tu lahko zatakne. Da ne bi bilo preveč težav, je "neskončna" samo približno vsaka tretja povezava, zato redko naletimo na nerešljiv problem. Program nas v tem primeru ne opomni (!) razen izjemoma: če je povezav manj kot vozlišč, pove, da bo šlo narobe in zakaj.

Grafični prikaz se mi zdi dovolj nazoren, ni pa estetsko dovršen. Zdelo se mi je, da bi mi oblikovanje vzelo preveč časa. Zato sem se lepemu izgledu odpovedala. Saj je vendar bistvo Kruskalovega algoritma optimizacija cene, ali ne? Čas pa je denar ...

Na koncu sem se "oglasila" na strani konzorcija w3c, kjer sem izvedela, da mi manjka !doctype značka. Še nekaj, kar se moram naučiti ...