Kruskal's MST

O(E log E)

Kruskalův algoritmus staví minimální kostru tím, že seřadí všechny hrany podle váhy a přidává je jednu po druhé, přičemž přeskočí hranu, jejíž oba konce jsou už spojené (to by vytvořilo cyklus). Struktura union-find sleduje, které uzly jsou spojené. Běží v O(E log E), dominuje řazení. Tady jsou váhy hran vzdálenosti mezi uzly.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Seřaď každou hranu podle váhy, nejlevnější první.
  2. Vezmi další hranu; když jsou její konce v různých komponentách, přidej ji.
  3. Slouč ty dvě komponenty (union-find).
  4. Když už jsou spojené, hranu přeskoč — vytvořila by cyklus.

Pseudokód

1kruskal(graph):                     # O(E log E)2  sort all edges by weight3  for each edge (u, v) in order:4    if find(u) ≠ find(v):            # different components5      union(u, v); add the edge to the MST6    else: skip it (it would make a cycle)