Kalamita

Algoritmy pro hledání minimální kostry

Kruskalův algoritmus

J. P. Kruskal vypracoval tři postupy pro hledání minimální kostry. Své výsledky publikoval v roce 1956. Uvedeme jeden z jeho algoritmů známý jako Kruskalův algoritmus.

Primův algoritmus

R. C. Prim vypracoval podobný algoritmus pro hledání minimální kostry. Svou práci publikoval v roce 1957. Uvedeme jeho algoritmus známý jako Primův algoritmus.

Poznámka

Je známo, že brněnský matematik Otakar Borůvka řešil otázku optimální výstavby elektrické sítě. Jeho algoritmus pochází z roku 1926. O. Borůvka jej však neformuloval jako úlohu teorie grafů, ale v jazyku matic. Kruskal na jeho práci navazoval.

Jeho postup vylepšil roku 1929 Vojtěch Jarník. Nezávisle na něm ke stejným výsledkům dospěl později Prim a také Dijkstra.

Jeden z algoritmů si vybereme.