Borůvkův algoritmus funguje správně pouze na ohodnocených grafech, ve kterých je minimální kostra určena jednoznačně. (Jak si v každém grafu zajistit jednoznačnost minimální kostry je popsáno v předchozí sekci). Výhodou Borůvkova algoritmu je, že lze dobře paralelizovat.

Borůvkův algoritmus si v průběhu udržuje les $T$ (množinu hran rozšířitelnou do minimální kostry). Na začátku je les tvořen izolovanými vrcholy (neobsahuje žádnou hranu). V každé iteraci vybereme pro každý strom $T_i$ (komponentu souvislosti) lesa $T$ nejlevnější hranu řezu $\delta(T_i)$ a na závěr iterace ji přidáme do $T$. Proč ji nepřidáme rovnou? Musíme si dát pozor, abychom nějakou hranu nepřidali dvakrát. Mohlo by se stát, že jedna hrana bude spojovat dvě komponenty souvislosti a pro obě komponenty bude vybrána jako nejlevnější.

Proč algoritmus vyžaduje jednoznačnost minimální kostry? Jinak by se mohlo stát, že pro komponetu $T_u$ vybereme nejlevnější hranu řezu $e_u$ a pro komponentu $T_v$ jinou nejlevnější hranu $e_v$ téhož řezu. Po přidání obou hran do kostry by vznikla kružnice.

Borůvka:
	 $T:= (V,\emptyset)$
	 while $T$ není souvislý do
	 	 Pro každou komponentu souvislosti $T_i$ grafu $T$ 
	 	 \quad vyber nejlevnější hranu $e_i$ řezu $\delta(T_i)$.
	 	 Všechny hrany $e_i$ přidej do $T$.
Lemma: V každé iteraci Borůvkova algoritmu klesne počet komponent souvislosti aspoň na polovinu.

Lemma platí, protože se každá komponenta souvislosti $T_i$ spojí s jinou komponentou souvislosti přes hranu $e_i$. Jako důsledek dostáváme, že Borůvkův algoritmus provede nejvýše $\log n$ iterací.

Lemma: Borůvkův algoritmus najde minimální kostru.

Důkaz: Borůvkův algoritmus opět funguje podle meta-algoritmu. Tentokrát ale s tou změnou, že používáme variantu lemmatu “o nejlevnější hraně řezu” pro grafy, jejich hrany mají vzájemně různé ohodnocení. Podle lemmatu „o nejlevnější hraně řezu“ patří každá vybraná hrana $e_i$ do jednoznačně určené minimální kostry.

Zkuste si rozmyslet, proč během přidávání hran nevznikne kružnice.

Příklad: Najděte pomocí Borůvkova algoritmu minimální kostru grafu na následujícím obrázku. Jednotlivé iterace jsou na obrázcích vpravo. V první iteraci pro každý vrchol vybíráme nejlevnější hranu, která z něj vede. Pro vrchol A vybereme hranu AD, podobně pro vrchol D vybereme hranu AD. Dále pro vrcholy B a C vybereme hranu BC a pro vrcholy E a F hranu EF. V druhé iteraci podobně vybíráme nejlevnější hranu, která vede z každé “tlusté” komponenty souvislosti někam ven. Pro komponentu $\{A,D\}$ vybereme hranu DB, pro komponentu $\{B,C\}$ také hranu DB a pro komponentu $\{E,F\}$ hranu CF.

Implementace

Nechť $T_v$ označuje komponentu souvislosti, ve které leží vrchol $v$. V každé iteraci chceme pro každou komponentu $T_v$ nalézt nejlevnější hranu, která z ní vede ven. V každé komponentě souvislosti $T_v$ zvolíme jednoho reprezentanta $\ARRAY{r}{v}\in T_v$. Nejlevnější hranu vedoucí z komponenty $T_v$ si zapamatujeme v položce $\ARRAY{emin}{\cdot}$ u reprezentanta komponenty $\ARRAY{r}{v}$. Iteraci provedeme následovně:

  • Vytvoříme pomocný graf $G_{pom}$ jehož vrcholy jsou reprezentanti komponent souvislosti. Postupně projdeme všechny hrany $e=xy\in E$ a zkusíme je přidat do pomocného grafu jako hrany $\ARRAY{r}{x}\ARRAY{r}{y}$. Při přidávání hran mohou vzniknout smyčky a násobné hrany. Smyčky rovnou vyhodíme a z násobných hran přidáme do pomocného grafu pouze tu nejlevnější.V Borůvkově algoritmu můžeme být velmi líní a nemusíme si z pomocného grafu skoro nic pamatovat. Zapamatujeme si pro každého reprezentanta komponenty pouze nejlevnější hranu $\ARRAY{emin}{\ARRAY{r}{v}}$, která z reprezentanta vede. Nejlevnější hrana vedoucí z reprezentanta $\ARRAY{r}{v}$ odpovídá nejlevnější hraně řezu $\delta(C_v)$.
  • Za každého reprezentanta $\ARRAY{r}{v}$ přidáme do minimální kostry hranu $\ARRAY{emin}{\ARRAY{r}{v}}$. (Projdeme všechny vrcholy a najdeme reprezentanty.)
  • Před další iterací musíme aktualizovat pole $\ARRAY{r}{\cdot}$. Protože se nám mohlo sjednotit několik komponent souvislosti do jedné, je potřeba provést sjednocení komponent opatrněji než postupným sjednocováním dvojic komponent a přeznačováním $\ARRAY{r}{u}$. Jinak by to mohlo trvat příliš dlouho. Pole $\ARRAY{r}{\cdot}$ vyplníme úplně znova tak, že nalezneme komponenty souvislosti v grafu s hranami $M$ (průchod do hloubky).1

Mohlo by vás napadnout, proč si neušetříme práci s aktualizací pole $\ARRAY{r}{\cdot}$ a proč nepoužijeme řešení Union-Find problému pomocí přepojování stromečků s kompresí cestiček. Je pravda, že by se výrazně zjednodušila aktualizace pole $\ARRAY{r}{\cdot}$, ale na druhou stranu by hledání nejlevnějších hran vycházejících z každé komponenty trvalo $\OO(m\alpha(n))$. To je víc než $\OO(m)$.

Výše popsaným postupem můžeme každou iteraci provést v čase $\OO(m)$. Celkem bude Borůvkův algoritmus trvat čas $\OO(m \log n)$. Výhodou Borůvkova algoritmu je, že v každé iteraci můžeme počítat nejlevnější hrany $e_i$ paralelně.