Kruskalův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Kruskalův algoritmus (v České republice se někdy mylně zaměňuje s Borůvkovým algoritmem, ten ale funguje odlišně) je jeden z algoritmů využívaných v teorii grafů k nalezení minimální kostry grafu, jehož hrany mají nezáporné ohodnocení (délku). U souvislého grafu hledá podmnožinu hran, která tvoří strom obsahující všechny uzly, s tím, že celková váha (součet délek) hran grafu je minimální. V případě grafu o více komponentách, algoritmus hledá les minimálních koster, tedy minimální kostru každé komponenty. Kruskalův algoritmus je příkladem hladového algoritmu.

Historie[editovat | editovat zdroj]

Algoritmus byl poprvé publikován Josephem B. Kruskalem, zaměstnancem Bellových Laboratoří, v roce 1956. Kruskal v úvodu své práce[1] odkazuje na článek[2] Otakara Borůvky, který pojednává o existenci jediné minimální kostry pro graf s hranami ohodnocenými různými nezápornými čísly.

Kruskal svůj algoritmus popsal následujícím způsobem[1]:

Postup A:

  • Opakuj následující kroky, dokud je to možné:
  • Z hran grafu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): G , které dosud nebyly vybrány, vyber nejkratší hranu, která nevytváří žádnou kružnici s hranami již vybranými.
  • Množina vybraných hran je kostrou grafu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): G , která je navíc minimální

V roce 1957 tento algoritmus popsali Loberman a Weinberger, těsně před zveřejněním se autoři o Kruskalově práci dověděli, kvůli detailnějšímu popisu problému a obecnější formulaci však svou práci publikovali.[3]

Ve své práci Kruskal zmiňuje variaci postupu A, ve kterém se opakovaně odebírá nejdelší hrana z grafu, která ještě nezpůsobí rozpad grafu na více podgrafů. Tímto ekvivalentním postupem můžeme také vytvořit minimální kostru grafu.

Postup A':

  • Opakuj následující kroky, dokud je to možné:
  • Z hran Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): G , které dosud nebyly vybrány, vyber nejdelší, která je nerozpojí.
  • Množina nevybraných hran je minimální kostrou grafu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): G .

Tento alternativní postup byl v roce 1961 nezávisle popsán A. Kotzigem.[4]

Postup B:

Jako obecnější postup pro podmnožinu uzlů grafu formuloval Kruskal postup B:

  • Nechť V je libovolná pevná (neprázdná) podmnožina uzlů grafu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): G , potom opakuj následující kroky, dokud je to možné:
  • Z hran grafu , které dosud nebyly vybrány, ale jsou spojeny s uzlem z Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): V nebo s hranou grafu, která již byla vybrána, vyber nejkratší hranu, která nevytváří kružnice s hranami již vybranými.
  • Množina vybraných hran je kostrou grafu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): G , která je navíc minimální. V případě, že Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): V je množina všech vrcholů grafu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): G , stává se z obecnějšího postupu B postup A.

Kruskal se ve své práci také zamýšlí nad existencí „duálního“ postupu k B, stejně jako je tomu v případě postupů A a A'. Požadovanou formulaci přináší Rosenstiehl v roce 1967.[5]

První, kdo formuloval postup B byl Vojtěch Jarník v roku 1930[6], obvykle je přisuzován Robertu Primovi, který formuloval obecně kategorii těchto algoritmů[7], z výpočtového hlediska, ale preferoval (stejně jako později Edsger Dijkstra[8]) použití postupu B.

Kruskalův původní důkaz předpokládá různé ohodnocení hran grafu.

Algoritmus[editovat | editovat zdroj]

Ekvivalentně můžeme algoritmus popsat tak, že se vždy vybírá taková hrana, která má ze všech možných hran spojujících dva různé podstromy ve vytvářené kostře tu nejmenší váhu.

  • vytvoř les Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): F (množinu stromů), ve kterém je každý uzel grafu samostatným podstromem
  • vytvoř množinu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): S obsahující všechny hrany grafu
  • dokud je množina Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): S neprázdná
    • z množiny Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): S odeber hranu s minimální váhou
    • pokud tato hrana spojuje dva různé podstromy, přidej ji do lesa Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): F , tak že tyto podstromy sluč do jednoho
    • v jiném případě hranu zahoď

Po skončení běhu algoritmu obsahuje les jedinou komponentu, tvořící minimální kostru grafu.

Složitost[editovat | editovat zdroj]

Časová složitost závisí na způsobu implementace řazení a operací s množinovým rozkladem. Pro graf Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): G s počtem uzlů Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): U a hran Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): H je složitost algoritmu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle O(U \log U)} , což je asymptoticky ekvivalentní s Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle O(H \log U)} . Hrany seřadíme některým z řadících algoritmů podle vah v čase Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle O(H \log H)} , to umožní algoritmu odstranit hranu s minimální vahou v konstantním čase. Pro zaznamenání informací příslušnosti uzlů k jednotlivým komponentám využijeme datovou strukturu disjoint-set (viz Disjoint-set data structure). V této datové struktuře můžeme pro vyhledávání a spojování (sjednocení) využít union-find, které mají složitost Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle O(U)} . Algoritmus udělá pro každou hranu dvě operace vyhledávání a jednu operaci sjednocení. I jednodušší datové struktury umožňují dosáhnout celkovou složitost Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle O(H \log H) = O (H \log U)} . Pokud jsou hrany již seřazeny, nebo je dokážeme seřadit v lineárním čase, může pomocí sofistikovanějších datových struktur dosáhnout složitost Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle O(H \alpha (U))} , kde Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): \alpha je inverzní Ackermannova funkce.

Příklad[editovat | editovat zdroj]

Prim Algorithm 0.svg Původní ohodnocený graf. Čísla poblíž hran označují jejich cenu. Žádná hrana zatím není označena.
Kruskal Algorithm 1.svg AD a CE jsou hrany s nejmenší délkou. Můžeme zvolit libovolnou z dvou hran. Označíme hranu AD.
Kruskal Algorithm 2.svg Nejkratší neoznačenou hranou je CE s délkou 5. Označíme hranu CE.
Kruskal Algorithm 3.svg Nejkratší neoznačenou hranou je DF s délkou 6. Označíme hranu DF.
Kruskal Algorithm 4.svg Následující nejkratší hranou jsou AB a BE s délkou 7. Vybereme hranu AB. Hranu BD označíme červeně, protože mezi B a D již existuje cesta označená zelenou barvou, přidání hrany BD do výběru by způsobilo vznik nežádoucí kružnice ABD.
Kruskal Algorithm 5.svg Proces pokračuje označením následující nejkratší hrany BE. Tři hrany jsou následně označené červeně, protože BC by mohla vytvořit kružnici BCE, DE kružnici DEBA a FE kružnici FEBAD.
Kruskal Algorithm 6.svg Hledání minimální kostry končí přidáním hrany EG. Následující výběr jakékoliv jiné hrany by způsobil vznik kružnice a výsledek by již nebyl kostrou grafu.

Důkaz správnosti[editovat | editovat zdroj]

Bez újmy na obecnosti můžeme graf považovat za úplný. Pokud by byl graf neúplný, jednoduše nahradíme hrany, které jsou jeho doplňkem do úplného grafu, za hrany s neporovnatelně větším ohodnocením.

Důkaz se skládá ze dvou částí. První dokazuje, že algoritmus na výstupu skutečně vytvoří kostru. Druhá část důkazu je potvrzením, že kostra je skutečně minimální.

Důkaz vytvoření kostry[editovat | editovat zdroj]

Nechť je souvislý graf s ohodnocenými hranami a Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): Y je podgrafem Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): P vytvořeným Kruskalovým algoritmem. Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): Y nemůže obsahovat kružnici, protože poslední hrana přidána do kružnice by spojovala ten samý podstrom a ne dva rozdílné, co je podmínkou pro přidání nové hrany. nemůže být nesouvislý, protože hrany přidané do Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y slučující podstromy byly do Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y přidány, z toho plyne, že Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y je kostrou grafu Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): P .

Důkaz minimální kostry[editovat | editovat zdroj]

Provedeme důkaz sporem. Nechť Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y je kostrou, ale ne minimální, zkoumaného grafu a Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_1 minimální kostrou grafu, která má nejmenší počet takových hran, které se nenacházejí v Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y . Nechť Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): e je hrana, která by byla jako první přidána algoritmem do Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y , z těch které nejsou v Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_1 . Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle Y_1 \cup {e}} tvoří kružnici. Jelikož Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y je strom, nemůže obsahovat kružnici. Proto musí zmíněné sjednocení obsahovat hranu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): f , která v Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y není obsažena. Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle Y_{2}=Y_{1}\cup {e}\setminus {f}} je také kostrou grafu a jeho celkové ohodnocení nemůže být menší než ohodnocení Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_1 , proto Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): e nemůže mít menší ohodnocení než Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): f . Dalším využitím důkazu sporem dokážeme, že ohodnocení hrany Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): f nemůže být menší než ohodnocení hrany Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): e . Předpokládejme opak (Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): f má menší ohodnocení jako Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): e ) a pamatujme, že hrany mají být přidány do Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y v pořadí jejich neklesajících ohodnocení. Proto by bylo Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): f testováno pro přidání do podlesu Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): {\displaystyle Y_3 \subset Y\cap Y_1} před Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): e (Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): e je první hrana Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y , která není v Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_1 ). Hrana ale nevytvoří kružnici v Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_1 , proto nemůže vytvořit ani kružnici v Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): Y_3 a byla by přidána do vytvářeného stromu. Z předchozích úvah plyne, že ohodnocení Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): e a Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): f jsou stejné a Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_2 je minimální kostrou, ale Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_2 má o jednu společnou hranu s Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y víc jako má Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „/mathoid/local/v1/“:): Y_1 , co je ve sporu s výběrem Nelze pochopit (Chyba konverze. Server („https://cs.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): Y_1 za minimální kostru grafu.

Pseudokód[editovat | editovat zdroj]

1 Kruskal(G,w)[9]
2 A := ∅ Vybraná kostra zatím prázdná,
3     for každý uzel u ∈ U //pro každý uzel se vytvoří samostatný podstrom
4         do MAKE-SET(u) 
5   uspořádej H do neklesající posloupnosti podle váhy w
6   for každou hranu [u, v] ∈ H v pořadí neklesajících vah
7     do if FIND-SET(u) != FIND-SET(v) //Hrana [u, v] je vhodná, přidej ji do kostry a spoj odpovídající podstromy
8         then A := A ∪ {[u, v]} 
9             UNION(u, v)
10  return A

Odkazy[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. a b KRUSKAL, Joseph Bernard. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society. únor 1956, roč. 7, čís. 1, s. 48-50. Dostupné online. DOI:10.2307/2033241. (anglicky) 
  2. BORŮVKA, Otakar. O jistém problému minimálním. In Práce Mor. Přírodověd. Spol. v Brně. Brno : [s. n.], 1926. Svazek 3, s. 37–58.
  3. LOBERMAN, H; WEINBERGER, A. Formal Procedures for Connecting Terminals with a Minimum Total Wire Length. Journal of the ACM. únor 1957, roč. 4, čís. 4, s. 428-437. Dostupné online. ISSN 0004-5411. DOI:10.1145/320893.320896. (anglicky) 
  4. KOTZIG, Anton. Súvislé podgrafy s minimálnou hodnotou v konečnom súvislom grafe. Časopis pro pěstování matematiky. 1961, čís. 86. ISSN 0528-2195.  
  5. ROSENSTIEHL, Pierre. L'arbre minimum d'un graphe. In Theory of Graphs (Int. Symposium, Rome, 1966). New York : Gordon and Breach, 1967. S. 357-368.
  6. JARNÍK, Vojtěch. O jistém problému minimálním. In Práce Mor. Přírodověd. Spol. v Brně. Brno : [s. n.], 1930. Svazek 6, s. 57–63.
  7. PRIM, Robert Clay. Formal Procedures for Connecting Terminals with a Minimum Total Wire Length. Bell System Technical Journal. 1957, čís. 36, s. 1389-1401. ISSN 1089-7089. (anglicky) 
  8. DIJKSTRA, Edsger Wybe. A note on two problems in connexion with graphs. Numerische Mathematik. prosinec 1959, roč. 1, čís. 1, s. 269-271. ISSN 0029-599X. DOI:10.1007/BF01386390.  
  9. KOLÁŘ, Josef. Teoretická informatika. Praha : Česká informatická společnost, 2004. ISBN 80-900853-8-5. Kapitola 5, s. 102.