Organizacija podatkov
Podatke o grafu bomo dobili v obliki matrike povezav, velikosti n * n.
Vozlišča so indeksi od 0 do n-1. Ker je graf neusmerjen, je dana matrika simetrična,
vrednost diagonalnih elementov naj bo neskončno - nobenega vozlišča ne bomo povezovali
samega s seboj. Dovolj bo torej poznati zgornjo trikotno matriko brez diagonale.
V rešitvi sem predvidela dva načina branja podatkov:
-
Lahko jih preberemo iz vnosnega okna. Posebej preberemo velikost matrike (n). Nato pa
beremo SAMO ZGORJI TRIKOTNIK matrike, brez diagonale.
Torej je v prvi vrstici n-1 elementov, v drugi n-2 ... v zadnji en sam element.
Cene povezav naj bodo pozitivna cela števila, ločimo jih z vejico.
Ta način je zamuden in če se zmotimo, je treba začeti od začetka.
-
Lahko pa izbiro prepustimo računalniku: določimo samo število povezav, potem pa
program naključno generira cene v mejah od 1 do 10.
-
Najbolje bi bilo brati iz datoteke, a tega še ne znam ...
Na vsakem koraku postopka bomo morali poiskati najcenejšo povezavo in preveriti, ali
sta njeni krajišči že povezani. Torej imamo dva problema: