Minimální rozpínací strom

První pokus

Vytvořit algoritmus, který objeví minimální spřádací strom, může být velmi jednoduché:

 funkce MST(G,W):     T = {} dokud T netvoří protahovací strom: najděte minimální váženou hranu v E, která je bezpečná pro T T = T union {(u,v)} return T

V tomto případě "bezpečný" znamená, že zahrnutí hrany nevytvoří v grafu cyklus. Cyklus znamená začít v jednom vrcholu, přejít do několika dalších vrcholů a skončit opět ve výchozím bodě, aniž by byla dvakrát použita stejná hrana.

Historie

Český vědec Otakar Borůvka vyvinul v roce 1926 první známý algoritmus pro nalezení minimálního protahovacího stromu. Chtěl vyřešit problém nalezení efektivního pokrytí Moravy elektrickou energií. Dnes je tento algoritmus známý jako Borůvkův algoritmus. Dnes se běžně používají dva další algoritmy. Jeden z nich vyvinul Vojtěch Jarník v roce 1930 a do praxe jej uvedl Robert Clay Prim v roce 1957. Edsger Wybe Dijkstra jej znovu objevil v roce 1959 a nazval jej Primův algoritmus. Druhý algoritmus se nazývá Kruskalův algoritmus a v roce 1956 jej vytáhl Joseph Kruskal. Všechny tři algoritmy jsou chamtivé a pracují v polynomiálním čase.

Dosud nejrychlejší algoritmus minimálního rozpětí stromů vyvinul Bernard Chazelle. Algoritmus je založen na měkké hromadě, přibližné prioritní frontě. Jeho doba běhu je O(m α(m,n)), kde m je počet hran, n je počet vrcholů a α je klasická funkční inverze Ackermannovy funkce. Funkce α roste extrémně pomalu, takže pro všechny praktické účely ji lze považovat za konstantu ne větší než 4; Chazellův algoritmus tedy trvá velmi blízko lineárnímu času.

Jaký je nejrychlejší možný algoritmus pro tento problém? To je jedna z nejstarších otevřených otázek v informatice. Je zřejmé, že existuje lineární dolní mez, protože musíme prozkoumat alespoň všechny váhy. Pokud jsou váhy hran celá čísla s omezenou bitovou délkou, pak jsou známy deterministické algoritmy s lineárním časem běhu. Pro obecné váhy existují randomizované algoritmy, jejichž očekávaná doba běhu je lineární.

K problému lze přistupovat i distribuovaným způsobem. Pokud je každý uzel považován za počítač a žádný uzel nezná nic jiného než své vlastní připojené spoje, lze i tak vypočítat distribuovaný minimální protahovací strom.