Skip to content

11.5 Implementace Kruskalova algoritmu

Definice 11.3 (Struktura Union-Find)

Struktura Union-Find

Struktura Union-Find reprezentuje rozklad množiny objektů \(X\) a podporuje operace:

  • Init(\(X\)) vytvoří strukturu, ve které je každý element z \(X\) ve vlastní množině.
  • Find(\(u\)) vrátí identifikátor množiny obsahující element \(u\).
  • Union(\(u,v\)) sjednotí množiny obsahující prvky \(u\) a \(v\) (pokud jsou ze stejné množiny, struktura zůstane nezměněná).

Algoritmus 11.3 Implementace Kruskalova algoritmu s Union-Find

Algoritmus Kruskal s Union-Find

Vstup

Souvislý graf G s vahami na hranách

Výstup

Kostra T s minimální váhou

Idea

  • Kruskalův algoritmus musí nejprve seřadit hrany. Na to použijeme pochopitelně optimální řadící algoritmus.
  • Začne s lesem izolovaných vrcholů a testuje postupně hrany, zda jejich vrcholy leží ve dvou různých stromových komponentách lesa a pokud ano, spojí tyto komponenty pomocí této hrany do větší.
  • To vede na využití struktury Union-Find
  • Struktura Union-Find reprezentuje komponenty souvislosti akuálního grafu a operace pak speciálně jsou:
    • Init(\(V\)) založíme strukturu – každý vrchol je v samostatné komponentě.
    • Find(\(u\)) vrátí identifikátor komponenty, ve které leží vrchol \(u\).
    • Pokud pro testovanou hranu \(\{u,v\}\) platí, že \(u\) a \(v\) patří do různých komponent (tj. Find\((u)\ne\)Find\((v)\)), pak Union(\(u,v\)) tyto komponenty spojí do jedné (přidáme \(\{u,v\}\) do konstruované kostry).

Algoritmus

Algoritmus MinKostraKruskal(G = (V, E), w: E → R):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Uspořádej hrany podle vah: w(e1) ≤ · · · ≤ w(em)
T := (V, ∅) //pocatecni les izolovaných vrcholů
U := Init(V )
Pro i := 1, . . . , m opakuj:
    označ u, v krajní vrcholy hrany ei
    a := U → Find(u); b := U → Find(v);
    Pokud a ̸= b:
        E(T) := E(T) ∪ {ei}
        U → Union(a, b)
Vrať T

Časová složitost Kruskalova algoritmu

  • Připomeňme, že \(n = |V|\) a \(m = |E|\).
  • Řazení hran trvá \(O(m \log m) = O(m \log {n^2}) = O(m \log n)\).
  • Zbytek algoritmu testuje hrany pomocí operace Find a spojuje menší stromy do větších stromů pomocí operace Union.

Věta 11.7 (o časové složitosti Kruskalova algoritmu)

Kruskalův algoritmus vytvoří minimální kostru v čase \(O(m \log n + T_i(n) + m \cdot T_f(n) + n \cdot T_u(n))\), kde \(T_i(n), T_f(n)\) a \(T_u(n)\) jsou časové složitosti operací Init, Find a Union v Union-Find struktuře nad množinou velikosti \(n\).

Důkaz věty 11.7

Založí strukturu Union-Find. Při testování hran se nejvýše 2m-krát zavolá Find a (n − 1)-krát se zavolá Union.