15b

---

Kruskalův algoritmus

Popis algoritmu

KROK 0

Uspořádáme hrany do neklesající posloupnosti podle jejich ohodnocení:

c(e₁) <= c(e₂) <= ... <= c(e_m),

kde m = |E_G|.
Položíme okamžitý les F₀ := { U, {} },i = 0, j = 0.

KROK 1

Opakujme tento krok tolikrát, kolikrát je to jen možné:
Bereme postupně hrany e₁, e₂, ... a snažíme se přidat je k okamžitému lesu F_i. Pokud je F_i + e_j lesem, položíme

F_i+1 := F_i + e_j, i := i+1

jinak hranu e_j vynecháme. Položíme j := j+1.

Zjednodušený popis algoritmu

Minimální kostru grafu vytvoříme ve dvou krocích. Krok 0 je startovní, poté opakujeme krok 1. 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. seřadíme hrany do neklesající posloupnosti podle jejich ohodnocení. Jdeme na krok 1.

KROK 1

Tento krok opakujeme dokud nebudeme mít o jednu hranu méně, než je počet vrcholů grafu.
Bereme postupně hrany e₁, e₂, ... a snažíme se je přidat k našemu grafu.

• pokud cyklus nevznikne - hranu přidáme
• pokud by cyklus vznikl - hranu vynecháme

---

15b