Kruskalův algoritmus - Kruskal's algorithm

Kruskalův algoritmus najde minimální rozsah lesa neorientovaného okrajově váženého grafu . Pokud je graf připojen , najde minimální kostru . (Minimální rozpětí připojeného grafu je podmnožinou hran, která tvoří strom zahrnující každý vrchol , kde je minimalizován součet hmotností všech hran ve stromu. U odpojeného grafu je minimální rozpínací les složený z minimálního spanningového stromu pro každou připojenou komponentu .) Je to chamtivý algoritmus v teorii grafů, protože v každém kroku přidává další hranu s nejnižší hmotností, která nebude tvořit cyklus do minimálního spanningového lesa.

Tento algoritmus se poprvé objevil v časopise Proceedings of the American Mathematical Society , s. 48–50 v roce 1956, a byl napsán Josephem Kruskalem .

Mezi další algoritmy tohoto problému patří Primův algoritmus , algoritmus reverzního mazání a Borůvkův algoritmus .

Algoritmus

• vytvořte les F (sadu stromů), kde každý vrchol v grafu je samostatný strom
• vytvořte sadu S obsahující všechny hrany v grafu
• zatímco S je neprázdné a F ještě není překlenující
  • odstraňte hranu s minimální hmotností ze S
  • pokud odstraněná hrana spojuje dva různé stromy, přidejte ji do lesa F a zkombinujte dva stromy do jednoho stromu

Na konci algoritmu tvoří doménová struktura minimální kostru grafu. Pokud je graf připojen, má doménová struktura jednu komponentu a tvoří minimální kostru.

Pseudo kód

Demo pro Kruskalův algoritmus na úplném grafu s váhami založenými na euklidovské vzdálenosti.

Následující kód je implementován s disjunktně nastavenou datovou strukturou . Zde reprezentujeme naši lesní F jako sadu hran a pomocí datové struktury disjunktní sady efektivně určujeme, zda jsou dva vrcholy součástí stejného stromu.

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
    return F

Složitost

U grafu s hranami E a vrcholy V lze Kruskalův algoritmus zobrazit tak, aby běžel v čase O ( E log E ), nebo ekvivalentně v čase O ( E log V ), vše s jednoduchými datovými strukturami. Tyto provozní časy jsou ekvivalentní, protože:

• E je nanejvýš a . ${\ displaystyle V ^ {2}}$${\ displaystyle \ log V ^ {2} = 2 \ log V \ in O (\ log V)}$
• Každý izolovaný vrchol je samostatnou součástí minimálního lesu. Pokud ignorujeme izolované vrcholy, získáme V ≤ 2 E , takže log V je . ${\ displaystyle O (\ log E)}$

Toho můžeme dosáhnout takto: nejprve seřaďte hrany podle váhy pomocí srovnávacího řazení v čase O ( E log E ); to umožňuje, aby krok „odstranit hranu s minimální hmotností z S “ pracoval v konstantním čase. Dále použijeme disjunktně nastavenou datovou strukturu, abychom sledovali, které vrcholy jsou ve kterých komponentách. Každý vrchol umístíme do vlastní disjunktní množiny, která přebírá operace O ( V ). Nakonec v nejhorším případě musíme iterovat všemi hranami a pro každou hranu musíme provést dvě operace „hledání“ a případně jedno spojení. Dokonce i jednoduchý nesouvislý-set datová struktura, jako nespojených-set lesy s unií podle hodnosti může vykonávat O ( E ) operace O ( E log V ) času. Celkový čas je tedy O ( E log E ) = O ( E log V ).

Za předpokladu, že hrany jsou buď již tříděny, nebo je lze třídit v lineárním čase (například s řadením počítáním nebo radixem ), může algoritmus ke spuštění v čase O ( E α ( V )) použít sofistikovanější disjunktní datovou strukturu , kde α je extrémně pomalu rostoucí inverzní funkce Ackermannovy funkce s jednou hodnotou .

Příklad

obraz	Popis
	AD a CE jsou nejkratší hrany s délkou 5 a AD byl zvolen libovolně , takže je zvýrazněn.
	CE je nyní nejkratší hrana, která netvoří cyklus, s délkou 5, takže je zvýrazněna jako druhá hrana.
	Další hrana, DF s délkou 6, je zvýrazněna pomocí stejné metody.
	Další nejkratší hrany jsou AB a BE , obě s délkou 7. AB je vybrán libovolně a je zvýrazněn. Okraj BD byl zvýrazněn červeně, protože mezi B a D již existuje cesta (zeleně) , takže pokud by byla zvolena, vytvořila by cyklus ( ABD ).
	Proces pokračuje v zvýraznění další nejmenší hrany, BE s délkou 7. Mnoho dalších hran je v této fázi zvýrazněno červeně: BC, protože by tvořilo smyčku BCE , DE, protože by tvořilo smyčku DEBA , a FE, protože by formulář FEBAD .
	Nakonec proces končí hranou EG délky 9 a je nalezen minimální kostra.

Důkaz správnosti

Důkaz se skládá ze dvou částí. Nejprve je dokázáno, že algoritmus vytváří kostru . Za druhé, je prokázáno, že vytvořený kostra má minimální váhu.

Překlenující strom

Dovolit být připojený, vážený graf a nechat být podgrafem vytvořeným algoritmem. nemůže mít cyklus, protože podle definice není hrana přidána, pokud má za následek cyklus. nelze odpojit, protože první narazená hrana, která spojuje dvě komponenty, by byla přidána algoritmem. Tak, je kostra . ${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle G}$

Minimalita

Ukážeme, že následující tvrzení P je pravdivé indukcí : Pokud F je množina hran zvolená v kterékoli fázi algoritmu, pak existuje nějaký minimální kostra, která obsahuje F a žádná z hran odmítnutá algoritmem.

• Je zřejmé, že P je na začátku pravdivé, když F je prázdný: jakýkoli minimální spanningový strom bude stačit a existuje jeden, protože vážený připojený graf má vždy minimální spanningový strom.
• Nyní předpokládejme, že P je pravdivý pro nějaký non-final set hrana F a nechť T být strom minimální kostry, který obsahuje F .
  • Pokud je další zvolená hrana e také v T , pak P platí pro F + e .
  • V opačném případě, je-li E není v T pak T + e má cyklus C . Tento cyklus obsahuje okraje, které nepatří k F , protože e netvoří cyklus při přidání do F , ale nemá v T . Nechť f je hrana, která je v C, ale ne v F + e . Všimněte si, že f také patří k T a P nebyl algoritmem považován. f proto musí mít váhu alespoň tak velkou jako e . Pak T - f + e je strom, a má stejný nebo menší váhu jako T . Tak T - f + e je minimální kostra obsahující F + e a znovu P drží.
• Proto podle principu indukce platí P, když se z F stal spanningový strom, což je možné pouze v případě, že F je minimální spanningový strom.

Paralelní algoritmus

Kruskalův algoritmus je ve své podstatě sekvenční a je obtížné jej paralelizovat. Je však možné provést počáteční třídění hran paralelně nebo alternativně použít paralelní implementaci binární haldy k extrakci hrany minimální váhy v každé iteraci. Vzhledem k tomu , že na procesorech je možné paralelní třídění v čase, lze dobu běhu Kruskalova algoritmu snížit na O ( E α ( V )), kde α je zase inverzní funkcí Ackermannovy funkce s jednou hodnotou . ${\ displaystyle O (n)}$${\ displaystyle O (\ log n)}$

Variantu Kruskalova algoritmu nazvanou Filter-Kruskal popsal Osipov et al. a je vhodnější pro paralelizaci. Základní myšlenkou funkce Filter-Kruskal je rozdělit hrany podobným způsobem jako rychlé třídění a odfiltrování hran, které spojují vrcholy stejného stromu, aby se snížily náklady na třídění. Následující pseudokód to dokazuje.

function filter_kruskal(G) is
    if |G.E| < kruskal_threshold:
        return kruskal(G)
    pivot = choose_random(G.E)
    ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$ = partition(G.E, pivot)
    A = filter_kruskal(${\displaystyle E_{\leq }}$)
    ${\displaystyle E_{>}}$ = filter(${\displaystyle E_{>}}$)
    A = A ∪ filter_kruskal(${\displaystyle E_{>}}$)
    return A

function partition(E, pivot) is
    ${\displaystyle E_{\leq }}$ = ∅, ${\displaystyle E_{>}}$ = ∅
    foreach (u, v) in E do
        if weight(u, v) <= pivot then
            ${\displaystyle E_{\leq }}$ = ${\displaystyle E_{\leq }}$ ∪ {(u, v)}
        else
            ${\displaystyle E_{>}}$ = ${\displaystyle E_{>}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$

function filter(E) is
    ${\displaystyle E_{\text{filtered}}}$ = ∅
    foreach (u, v) in E do
        if find_set(u) ≠ find_set(v) then
            ${\displaystyle E_{\text{filtered}}}$ = ${\displaystyle E_{\text{filtered}}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\text{filtered}}}$

Filtr-Kruskal se lépe hodí pro paralelizaci, protože třídění, filtrování a dělení lze snadno provádět paralelně distribucí hran mezi procesory.

Nakonec byly prozkoumány další varianty paralelní implementace Kruskalova algoritmu. Mezi příklady patří schéma, které používá pomocná vlákna k odstranění okrajů, které rozhodně nejsou součástí MST na pozadí, a varianta, která spouští sekvenční algoritmus na p podgrafech, poté tyto podgrafy sloučí, dokud nezůstane pouze jeden, konečný MST.

Viz také

• Primův algoritmus
• Dijkstrův algoritmus
• Borůvkův algoritmus
• Algoritmus obráceného mazání
• Seskupování pomocí jednoho propojení
• Chamtivý geometrický klíč

Reference

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein . Úvod do algoritmů , druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN   0-262-03293-7 . Oddíl 23.2: Algoritmy Kruskala a Prima, s. 567–574.
• Michael T. Goodrich a Roberto Tamassia . Datové struktury a algoritmy v Javě , čtvrté vydání. John Wiley & Sons, Inc., 2006. ISBN   0-471-73884-0 . Oddíl 13.7.1: Kruskalův algoritmus, s. 632.

externí odkazy

• Data pro příklad článku .
• Plugin Gephi pro výpočet zdrojového kódu minimálního rozpětí stromu .
• Kruskalův algoritmus s příkladem a programem v c ++
• Kruskalův algoritmický kód v C ++ aplikovaný na náhodná čísla
• Kruskalův algoritmický kód v Pythonu s vysvětlením