Kruskalův algoritmus

Z Wikipedie, otevřené encyklopedie

Kruskalův algoritmus (v České republice se někdy mylně zaměňuje s Borůvkovým algoritmem, ale ten funguje odlišně) je hladový algoritmus na nalezení minimální kostry grafu.

Algoritmus hledá minimální kostru souvislého grafu, v případě grafu o více komponentách pak les minimálních koster.

Poprvé byl publikován Josephem Kruskalem v Proceedings of the American Mathematical Society, pp. 48–50 v roce 1956.

[editovat] Algoritmus

Algoritmus postupně prochází hrany a vytváří z nich množiny E0, E1, E2, …, z nichž poslední je minimální kostra daného grafu G = (VE).

  1. Uspořádej hrany z E podle váhy.
  2. Vytvoř prázdnou množinu hran E0 = ∅.
  3. Pokud přidáním ei vznikne kružnice, ponechej Ei = Ei − 1,
    jinak Ei = Ei − 1ei.
  4. Opakuj krok 3, dokud i < m a Ei ještě nemá n − 1 hran.

[editovat] Důkaz

[editovat] Složitost

Složitost algoritmu závisí na použitých datových strukturách. Nejlepší možná varianta pomocí Union-Findu dosahuje O(nα(n) + m), kde α je inverzní Ackermannova funkce. Jednoduchá implementace, kde se při sjednocení přeznačuje vždy menší skupina, pak O(nlog(n) + m).