Prim's MST

O(E log V)

Primův algoritmus staví minimální kostru — nejlevnější množinu hran spojující všechny uzly — tím, že nechá jeden strom růst ven. Z libovolného uzlu opakovaně přidá hranu s nejmenší vahou, která spojí strom s uzlem, jenž v něm ještě není. S prioritní frontou běží v O(E log V). Tady jsou váhy hran vzdálenosti mezi uzly, takže táhnutím přetvoříš MST.

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. Začni strom libovolným jedním uzlem.
  2. Podívej se na každou hranu vedoucí ze stromu k vnějšímu uzlu.
  3. Přidej nejlevnější takovou hranu (a její uzel) do stromu.
  4. Opakuj, dokud nejsou ve stromě všechny uzly.

Pseudokód

1prim(graph, start):                 # O(E log V)2  tree ← { start }3  while a node is still outside the tree:4    pick the cheapest edge from the tree to an outside node5    add that node and edge to the tree