Borůvkův algoritmus

Borůvkův algoritmus slouží k nalezení minimální kostry grafu (kostry takové, že je součet vah jejích hran minimální). Byl vymyšlen českým matematikem Otakarem Borůvkou za účelem nalezení efektivního trasování elektrické sítě na Moravě. Algoritmus byl později několikrát znovuobjeven, proto se o něm lze dočíst také jako o Sollinově algoritmu.

Borůvkův algorimus funguje na principu skládání komponent. Na začátku jsou všechny uzly grafu nepropojené samostatné komponenty. Algoritmus v každém svém kroku propojí každou komponentu s jinou komponentou pomocí nejkratší možné hrany. Po maximálně $\log_{2} \vert U \vert$ krocích je kostra postavena (asymptotická složitost je tedy $O(|H| \cdot \log_{2} \vert U \vert)$ ).

Významnou výhodou Borůvkova algoritmu je snadná paralelizace spojování jednotlivých komponent řešení. Nevýhodou základní implementace je, že všechny hrany musí mít různé ohodnocení (aby při spojování dvou komponent nedošlo k jejich propojení různými hranami stejné váhy).

Kód

Pseudocode

/**
 * Boruvkuv algoritmus
 * V teto podobe nesnese graf s dvema stejne ohodnocenymi hranami 
 * @param graph graf
 * @param weight vahy jednotlivych hran
 * @return minimalni kostra   
 */
boruvkaAlgorithm(graph, weight)
    SpanningTree tree //kostra
    components = graph.vertices //na pocatku jsou vrcholy nepospojovany
    while components.size > 1 do
        for each component in components //pro vsechny komponenty
            edge e = connectWithMinimalEdge(component, weight) //propojime s jinou komponentou pomoci minimalni hrany
            tree.add(e) //hranu pridame do kostry
    return tree

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (1): 4

Přečtěte si také

Diskuse

bubersson18.6.2010

chybka v textu: "kostry součet jejíž součet" (je tam navíc "součet")
překlep v kódu: "grapg" má být "graph"