Kontraktivní algoritmus vychází z Borůvkova algoritmu, malinko ho vylepšuje a díky tomu dosáhneme o něco lepší časové složitosti (pochází od Mareše [MaresSaga]).

V každé iteraci Borůvkova algoritmu jsme konstruovali pomocný graf, ale u každého reprezentanta jsme si pamatovali jen nejlevnější hranu, která z něj vede. Tentokrát ten graf zkonstruujeme pořádně. Postupně projdeme všechny hrany $e=xy\in E$ a přidáme je 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 vyhodíme a z násobných hran si budeme pamatovat jen tu nejlevnější.1 Tímto postupem dostaneme v $k$-té iteraci graf $G_k$. Jinými slovy, graf $G_k$ vznikne z grafu $G$ kontrakcí komponent souvislosti podgrafu $T\subseteq G$.

V $k$-té iteraci se pouze některé komponenty spojili do jedné. Proto nemusíme graf $G_k$ konstruovat z $G$, ale můžeme ho konstruovat z menšího grafu $G_{k-1}$.

Nechť $n_i$ označuje počet vrcholů grafu $G_i$ a $m_i$ jeho počet hran. Při postupném vytváření grafů $G_0$, $G_1$,… bude $i$-tá iterace Borůvkova algoritmu trvat čas $\OO(m_i)$.

Lemma: Na grafu s různým ohodnocením hran je časová složitost kontraktivního Borůvkova algoritmu $\OO(\min\{n^2, m\log n \})$.
Důkaz: Odhad $\OO(m\log n)$ jsme si ukázali i pro nekontraktivní Borůvkův algoritmus. V kontraktivní variantě navíc ušetříme nějaký čas a tak odhad platí. Podívejme se na důkaz odhadu $\OO(n^2)$. Podle lemmatu [ref]lemma_pokles_boruvek[/ref] klesne v každé iteraci počet komponent souvislosti aspoň na polovinu. Proto $n_i \lt n/2^i$. V každém grafu je $m_i \lt n_i^2$ a proto $m_i \lt n^2 /4^i$. Každá iterace kontraktivního Borůvkova algoritmu trvá $\OO(m_i)$ a tedy celkem algoritmus trvá čas $\OO(\sum_i m_i)= \OO(\sum_i n^2/4^i)=\OO(n^2)$.
Lemma: Kontraktivní Borůvkův algoritmus má v rovinných grafech časovou složitost $\OO(n)$.
Důkaz: Platí následující fakt. Kontrakcí a mazáním hran rovinného grafu vznikne rovinný graf. Víme, že $n_i \leq n/2^i$. V každém rovinném grafu $G_R=(V_R,E_R)$ platí $|E_R| \leq 3|V_R|-6$. Proto $m_i \leq 3 n_i \leq 3n/2^i$. Součtem přes všechny iterace dostaneme celkový čas algoritmu $\OO(\sum_i m_i)=\OO(3n \sum_i 1/2^i)=\OO(n)$.