Algorithme de Borůvka

Le principe est de réduire G en contractant des arêtes : on choisit peu à peu les arêtes qui seront dans l'arbre, et à chaque fois que l'on en choisit une, on fusionne les nœuds que cette arête relie. Ainsi, il ne reste plus qu'un sommet à la fin.

On peut aussi décrire l'algorithme sans parler de contraction : on construit une forêt dont les arbres fusionnent peu à peu pour former un arbre couvrant de poids minimum.

On prend G le graphe et F l'ensemble des arêtes choisies (on le remplit peu à peu).

 1 F ← vide
 2 Tant que G n'est pas réduit à un sommet faire
 3    Détruire les boucles de G (*) 
 4    Remplacer les arêtes multiples entre deux sommets par une seule dont le poids est le minimum
 5    Pour tout x, sommet de G, faire
 6       Trouver l'arête e_x de poids minimum adjacente à x
 7       F ← F union e_x
 8       Contracter e_x (**)
 9    fin pour
10 fin tant que
11 renvoyer F

(*) i.e. les arêtes qui partent et arrivent au même sommet ; ce genre d'arête peut apparaitre après une itération.

(**) i.e. fusionner les sommets aux extrémités de ${\displaystyle e_{x}}$

L'algorithme de Borůvka a une complexité en ${\displaystyle O(A\ln(S))}$, où ${\displaystyle A}$ est le nombre d'arêtes et ${\displaystyle S}$ le nombre de sommets du graphe considéré[2].