15a

---

Primův algoritmus

Popis algoritmu

KROK 0

Položíme okamžitý les F₀ := { U,{} }, i = 0.

KROK 1

Je-li i = n-1, STOP (F_i je hledaná kostra), jinak jdeme na krok 2.

KROK 2

Zvolme strom s maximálním počtem uzlů T lesa F_i. Vybereme takovou hranu e_i, která má jeden koncový uzel patřící do stromu T a druhý do množiny U-T a je minimální s touto vlastností vzhledem k ohodnocení hran e_i.

Pokud neexistuje, STOP (G je nesouvislý a nemá kostru). Jinak položíme:

F_i+1 := F_i + e_j,
i := i+1 a jdeme na krok 1.

Zjednodušený popis algoritmu

Minimální kostru grafu vytvoříme v několik krocích. Krok 0 je startovní, opakujeme kroky 1 a 2. Předpokládáme, že graf je konečný a souvislý, tj. má minimální kostru.

KROK 0

Začneme od grafu, který neobsahuje žádnou hranu. Zvolíme si libovolný vrchol jako výchozí "část grafu". Jdeme na krok 1.

KROK 1

Obsahuje-li náš graf o jednu hranu méně něž je vrcholů, můžeme skončit. Našli jsme minimální kostru grafu. Jinak jdeme na krok 2.

KROK 2

K "největší části grafu" přidáme další hranu tak, aby

• vedla z již sestavené části grafu do nového vrcholu
• ze všech takových hran vybereme hranu s co nejmenším ohodnocením

a jdeme na krok 1.

---

15a