Calculateur Algorithme de Boruvka

Pseudocode

Chaque composante choisit sa propre arête sortante la moins chère, et toutes ces sélections sont appliquées d'un coup. Des tours plutôt que des étapes, et c'est précisément ce qui rend l'algorithme parallélisable.

Boruvka(graphe):
    creerEnsemble(v) pour chaque sommet
    acm = []

    tant qu il reste plus d une composante:
        moinsChere = {} // par composante
        pour chaque arete (u, v, w):
            a = trouver(u); b = trouver(v)
            si a == b: continuer        // arete interne
            si w < moinsChere[a]: moinsChere[a] = (u,v,w)
            si w < moinsChere[b]: moinsChere[b] = (u,v,w)

        pour chaque arete e dans moinsChere.valeurs():
            si trouver(e.u) != trouver(e.v):  // peut-etre deja unies
                unir(e.u, e.v); acm.ajouter(e)

La garde de la seconde boucle est indispensable, et non une précaution superflue. Deux composantes choisissent fréquemment la même arête, une depuis chaque extrémité, et l'appliquer deux fois ajouterait un doublon. La correction exige des poids d'arêtes distincts, ou une règle de départage cohérente comme la comparaison des identifiants d'arêtes: sans une telle règle, plusieurs composantes peuvent chacune retenir une arête différente de même poids et former ensemble un cycle.

Exemple détaillé, étape par étape

Construis l'arbre couvrant de poids minimum sur le graphe déjà utilisé pour Prim et Kruskal, afin de comparer directement les trois méthodes.

Graphe d'exemple: Arêtes non orientées A-B (2), A-C (3), B-C (1), C-D (4) et B-D (7).

1. Départ. Chaque sommet forme sa propre composante: {A}, {B}, {C}, {D}. Toute arête est donc sortante pour ses deux extrémités.
2. Chaque composante choisit. La composante A compare A-B à 2 contre A-C à 3 et retient A-B. La composante B compare A-B à 2, B-C à 1 et B-D à 7, et retient B-C. La composante C compare A-C à 3, B-C à 1 et C-D à 4, et retient B-C. La composante D compare C-D à 4 contre B-D à 7 et retient C-D.
3. Remarque le doublon. B et C ont toutes deux proposé la même arête B-C, une depuis chaque extrémité. La garde de la seconde boucle ne l'applique qu'une seule fois, et c'est exactement la raison d'être de cette vérification.
4. Appliquer toutes les sélections d un coup. Ajouter A-B, B-C et C-D fusionne l'ensemble en une seule composante en un unique tour. Cela fait trois arêtes pour quatre sommets, l'arbre est donc déjà complet.
5. La boucle se termine. Il ne reste qu'une composante, aucun second tour n'a donc lieu.

L'arbre couvrant de poids minimum est A-B, B-C et C-D pour un poids total de 2 + 1 + 4 = 7, soit le même arbre que celui produit par Prim et Kruskal. Boruvka y est parvenu en un tour au lieu de trois étapes séquentielles, et c'est tout l'intérêt: chaque tour divise au moins par deux le nombre de composantes, puisque chacune fusionne avec au moins une autre, si bien que O(log V) tours suffisent toujours. Avec quatre sommets, un seul tour a ici suffi.

Complexité et son origine

Temps: O(E log V) · Espace: O(V + E)

Chaque tour parcourt toutes les arêtes une fois en O(E) pour déterminer l'arête sortante la moins chère de chaque composante. Pendant un tour, chaque composante fusionne avec au moins une autre, le nombre de composantes est donc au moins divisé par deux, ce qui borne le nombre de tours par le logarithme en base 2 de V. La multiplication donne O(E log V), identique à Prim et Kruskal. La propriété distinctive est qu'au sein d'un tour chaque composante travaille indépendamment, si bien que le parcours se parallélise directement; c'est pourquoi Boruvka sous-tend les implémentations d'ACM sur GPU et en environnement distribué, alors que Prim et Kruskal, intrinsèquement séquentiels, ne s'y prêtent pas. Les algorithmes hybrides exécutent quelques tours de Boruvka pour réduire le graphe, puis basculent sur Prim.

Quand utiliser Algorithme de Borůvka, et quand l'éviter

Les trois algorithmes classiques d'ACM coûtent O(E log V). La différence est structurelle.

Pièges fréquents

• Ne pas traiter les poids égaux. Avec des poids identiques, des composantes différentes peuvent retenir des arêtes différentes qui forment ensemble un cycle, et le résultat n'est pas un arbre. Départage de manière cohérente, par exemple selon l'indice de l'arête, afin que toutes les composantes s'accordent sur un même ordre. Avec des poids tous distincts, le problème disparaît de lui-même.
• Ajouter deux fois la même arête. Deux composantes proposent couramment la même arête depuis des extrémités opposées. Sans vérifier que les extrémités appartiennent encore à des composantes distinctes au moment de l'application, l'arête est ajoutée deux fois et le nombre d'arêtes dépasse V - 1.
• Recalculer les composantes dans le parcours des arêtes. Appeler trouver à répétition sans compression de chemin rend chaque tour bien plus coûteux que O(E). Utilise Union-Find avec compression de chemin et union par rang, exactement comme dans Kruskal.
• Croire qu il exige un graphe connexe. Comme Kruskal, Boruvka traite nativement les entrées non connexes et renvoie une forêt couvrante de poids minimum. La condition de boucle doit alors devenir « aucune composante n'a d'arête sortante » plutôt que « il reste une composante », faute de quoi il ne terminera pas.
• Oublier qu il précède les deux autres. Publié en 1926 pour planifier un réseau électrique en Moravie, Boruvka est le plus ancien algorithme d'ACM connu, antérieur à Prim comme à Kruskal. On l'enseigne souvent en dernier, ce qui masque le fait que la formulation parallèle est venue en premier.

Questions fréquentes

Comment fonctionne l'algorithme de Boruvka?

Chaque composante sélectionne simultanément l'arête la moins chère qui en sort, et toutes les arêtes retenues sont ajoutées d'un coup, fusionnant les composantes. Cela se répète jusqu'à ce qu'il n'en reste qu'une. Comme chaque composante fusionne avec au moins une autre par tour, leur nombre est au moins divisé par deux à chaque fois et O(log V) tours suffisent.

Quelle est la complexité temporelle de l'algorithme de Boruvka?

O(E log V). Chaque tour parcourt les E arêtes pour trouver l'arête sortante la moins chère de chaque composante, et il se produit au plus log V tours puisque le nombre de composantes est divisé par deux à chaque tour. Cela égale asymptotiquement Prim et Kruskal.

Pourquoi l'algorithme de Boruvka convient-il au calcul parallèle?

Parce qu'au sein d'un tour chaque composante détermine sa propre arête sortante la moins chère de façon indépendante, sans état partagé ni contrainte d'ordre. Cela se transpose directement sur GPU et sur grappes distribuées. Prim et Kruskal sont intrinsèquement séquentiels: chacun dépend de l'unique décision globale prise juste avant.

Pourquoi les poids des arêtes doivent-ils être distincts?

Avec des poids égaux, des composantes différentes peuvent sélectionner des arêtes différentes de même coût qui forment ensemble un cycle, si bien que le résultat n'est pas un arbre. Toute règle de départage cohérente, comme comparer les indices d'arêtes à poids égal, rétablit la correction. Des poids distincts rendent en outre l'arbre couvrant de poids minimum unique.

Quelle est la différence entre Boruvka, Prim et Kruskal?

Les trois produisent un arbre couvrant de poids minimum en O(E log V). Prim fait croître un arbre depuis un sommet de départ à l'aide d'une file de priorité. Kruskal trie toutes les arêtes et ajoute celles qui ne ferment pas de cycle. Boruvka fait choisir à chaque composante son arête sortante la moins chère par tours parallèles, et c'est le seul des trois à se paralléliser naturellement.