Izpitno vprašanje RAČ2PRA 16200

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka MonikaDraškovič.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Na praktičnem primeru razloži, kako delujeta Primovov in Kruskalov postopek.

Odgovor

Primov in Kruskalov postopek sta algoritma za iskanje minimalnega vpetega drevesa v grafu.


Primov postopek

Začnemo s poljubnim vozliščem, ki je začetno vpeto drevo. Izberemo najcenejšo povezavo med vozlišči v doslej zgrajenem vpetem drevesu in vozlišči, ki še niso del drevesa in pri tem ne naredimo cikla. To ponavljamo, dokler niso vsa vozlišča v drevesu.

slika:primer_Prim.jpg


Kruskalov postopek

Kruskalov algoritem gradi minimalni vpeti gozd, ki na koncu preraste v minimalno vpeto drevo. Na tekočem koraku izberemo najcenejšo povezavo v grafu in jo dodamo. Pri tem pazimo, da ne naredimo cikla. Končamo, ko ni na voljo več nobene povezave, katere vozlišči nista v istem vpetem drevesu.

slika:primer_Kruskal.jpg

Osebna orodja