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 = (V, E).
- Uspořádej hrany z E podle váhy.
- Vytvoř prázdnou množinu hran E0 = ∅.
- Pokud přidáním ei vznikne kružnice, ponechej Ei = Ei − 1,
- jinak Ei = Ei − 1 ∪ ei.
- 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).

