Arbres couvrants minimaux et union-find

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• définir un arbre couvrant et un arbre couvrant minimal, dire combien d'arêtes ils comptent et reconnaître les problèmes concrets qui s'y ramènent;
• énoncer et démontrer la propriété de coupe, énoncer sa jumelle, la propriété de cycle, et vous en servir pour justifier qu'une arête donnée appartient — ou n'appartient pas — à un arbre couvrant minimal;
• dérouler Kruskal et Prim à la main sur un graphe pondéré, en montrant les arêtes refusées autant que les arêtes retenues, et démontrer la correction de Kruskal à partir de la propriété de coupe;
• implémenter la structure union-find avec union par rang et compression de chemin, et démontrer la borne $O(\log n)$ que le rang seul garantit;
• énoncer le coût de Kruskal, $O(m\log m)$, et celui de Prim avec un tas, $O(m\log n)$, dire ce que chacun facture, et choisir entre les deux selon que le graphe est creux ou dense;
• dire ce que l'unicité d'un arbre couvrant minimal implique, ce qu'elle n'implique pas, et pourquoi deux algorithmes différents tombent ici sur le même arbre.

Le problème de l'arbre couvrant minimal

Relier tout le monde, au moindre coût

Sept sites doivent être reliés par un réseau. Une entreprise de télécommunications tire de la fibre entre des centraux, un distributeur d'électricité pose des lignes entre des villages, un ingénieur en hydraulique raccorde des réservoirs: le problème a la même forme à chaque fois. On connaît les liaisons possibles — toutes ne le sont pas, une montagne, une frontière ou un lac en interdisent certaines — et le coût de chacune. On cherche un ensemble de liaisons qui rende l'ensemble des sites communicants, et dont le coût total soit le plus petit possible.

Deux remarques suffisent à transformer cette question en un problème de graphes bien posé. La première: la solution n'a aucune raison de contenir un cycle. Si un ensemble de liaisons contient un cycle, on peut en retirer n'importe quelle arête du cycle — tous les sites restent reliés, puisque le tour du cycle offrait déjà un chemin de rechange — et le coût diminue strictement dès que les poids sont strictement positifs. La seconde: une solution doit toucher tous les sites, sans quoi certains resteraient hors du réseau. Un sous-graphe connexe, sans cycle, contenant tous les sommets: c'est exactement ce qu'on appelle un arbre couvrant.

Le chapitre 6, Graphes: représentations et parcours, a posé le vocabulaire dont nous nous servirons sans le redéfinir: graphe non orienté $G=(V,E)$, avec $n=|V|$ sommets et $m=|E|$ arêtes, degré d'un sommet, chemin, cycle, connexité, composante connexe, liste et matrice d'adjacence. Il a aussi introduit le graphe témoin du cours, celui que les chapitres 6, 7 et 8 se partagent pour que vous n'ayez à apprendre qu'une seule image; nous le reprenons tel quel, avec ses onze poids, et c'est sur lui que tout ce chapitre calcule.

Trois précisions, chacune source d'une erreur classique.

D'abord, l'ACM n'est défini que pour un graphe connexe. Sur un graphe à plusieurs composantes, il n'existe aucun arbre couvrant, et ce qu'on cherche alors est une forêt couvrante minimale: un arbre minimal par composante. Les deux algorithmes de ce chapitre la produisent sans aucune modification; ils s'arrêtent simplement avec moins de $n-1$ arêtes, et c'est d'ailleurs le moyen le plus économique de tester la connexité tout en calculant le réseau.

Ensuite, rien n'exige que les poids soient positifs. Un poids négatif ne casse rien ici, contrairement à ce qui se passe pour les plus courts chemins au chapitre 7: l'ACM minimise une somme sur un ensemble fixé de $n-1$ arêtes, et non un chemin dont la longueur pourrait diverger en tournant dans un cycle négatif. C'est une différence de fond entre les deux problèmes, et elle mérite d'être notée dès maintenant.

Enfin, «minimal» ne veut pas dire «unique». Un graphe peut posséder plusieurs ACM, tous de même poids; nous y reviendrons longuement quand Kruskal et Prim auront produit le même arbre et qu'il faudra dire pourquoi.

Le chapitre 6 a énoncé, dans sa définition d'un arbre, qu'un arbre à $n$ sommets possède exactement $n-1$ arêtes. Ce chapitre-ci en dépend de bout en bout — c'est ce fait qui transforme «trouver le réseau le moins cher» en «choisir six arêtes sur onze» —, alors démontrons-le.

Démonstration. Par récurrence sur $n$. Pour $n=1$, l'arbre est réduit à un sommet et n'a aucune arête: $0=1-1$.

Supposons la propriété vraie pour tous les arbres à $n-1$ sommets, avec $n\ge 2$, et soit $T$ un arbre à $n$ sommets. $T$ possède au moins une feuille, c'est-à-dire un sommet de degré 1. En effet, partons d'un sommet quelconque et marchons sans jamais revenir immédiatement sur l'arête qu'on vient d'emprunter: comme $T$ est fini et sans cycle, on ne peut pas marcher indéfiniment — repasser deux fois par un même sommet fermerait un cycle —, donc la marche s'arrête, et elle ne peut s'arrêter que sur un sommet dont la seule arête est celle par laquelle on est arrivé. Notons $v$ cette feuille. Le graphe $T-v$, obtenu en retirant et son unique arête, est encore sans cycle, et il est encore connexe: tout chemin entre deux sommets de ne pouvait pas passer par , qui est de degré 1 et n'aurait pas eu d'issue. C'est donc un arbre à sommets, qui par hypothèse de récurrence a arêtes. En remettant et son arête, en a .

La conséquence est plus forte qu'elle n'en a l'air: tous les arbres couvrants d'un graphe donné ont le même nombre d'arêtes. Chercher le moins cher n'est donc pas chercher le plus petit — le nombre d'arêtes est imposé —, c'est choisir lesquelles des $m$ arêtes forment ce paquet de $n-1$. Sur le graphe témoin, $n=7$: tout arbre couvrant compte exactement six arêtes, et le problème est de choisir six arêtes parmi onze, en évitant celles qui créeraient un cycle.

Le graphe témoin, et pourquoi on n'énumère pas

Voici les données que tout ce chapitre utilise. Ce sont exactement celles du chapitre 6: le graphe est non orienté, il a sept sommets $A$ à $G$ et onze arêtes.

La somme des onze poids vaut 52. Les degrés sont $A$ 2, $B$ 3, $C$ 4, $D$ 4, $E$ 4, $F$ 3, $G$ 2, et leur somme vaut bien $2m=22$. Ces sept sites sont fictifs, comme le tableau témoin du chapitre 1: leur seule vertu est d'être toujours les mêmes.

La méthode la plus naïve consiste à énumérer tous les arbres couvrants et à garder le plus léger. Elle fonctionne, et elle est sans espoir. Un programme d'énumération exhaustive sur le graphe témoin — on essaie chacun des $\left(\genfrac{}{}{0ex}{}{11}{6}\right)=462$ choix de six arêtes et on garde ceux qui sont acycliques — trouve 144 arbres couvrants, dont exactement un de poids 17. Cent quarante-quatre pour sept sommets: c'est encore praticable. Mais la formule de Cayley donne le nombre d'arbres couvrants du graphe complet à $n$ sommets,

soit $7^5=16807$ pour sept sommets déjà, et $10^{98}$ pour cent sommets. L'énumération n'est pas une méthode: c'est la description du problème. Il nous faut un algorithme qui construise directement le bon arbre, et pour le construire sans jamais revenir sur ses pas, il nous faut un théorème qui dise, à chaque étape, qu'une arête est sûre.

Notez, sur la figure 8.1, une chose qui surprend souvent: l'arbre retenu contient l'arête $BD$ de poids 5, alors que le graphe possède des arêtes plus légères qui ont été écartées — $AB$ de poids 4, $FG$... non, $FG$ y est. Mais $AB$, de poids 4, est bel et bien refusée alors que $BD$, de poids 5, est prise. Un algorithme qui se contenterait de prendre les arêtes les plus légères sans autre précaution se tromperait. Ce qui rend $AB$ inutile, c'est que $A$ et $B$ sont reliés, par le chemin de poids , moins cher que l'arête directe. Reconnaître ce «déjà reliés» est tout le travail, et il occupera la seconde moitié du chapitre.

La propriété de coupe

Couper le graphe en deux

Toute la théorie tient dans une idée, et cette idée est une coupe: on sépare les sommets en deux camps et on regarde les arêtes qui passent d'un camp à l'autre.

Un graphe à $n$ sommets possède $2^n-2$ coupes si l'on distingue $S$ de son complémentaire, et la moitié sinon: pour le graphe témoin, $2^7-2=126$ parties non triviales, soit 63 coupes au sens géométrique. C'est peu, et nous vérifierons plus loin la propriété de coupe sur les 126, par programme.

Prenons-en une, et prenons-la nommée, parce qu'une propriété illustrée sur «une coupe quelconque» n'est illustrée sur rien. Posons

Trois arêtes traversent cette coupe, et trois seulement: $BD$ de poids 5, $CD$ de poids 8 et $CE$ de poids 10. Les arêtes $AB$, $AC$ et $BC$ ont leurs deux extrémités dans $S$; les arêtes $DE$, $DF$, , et ont leurs deux extrémités hors de . Aucune de ces huit-là ne traverse. La plus légère des traversantes est , de poids 5, et la figure 8.2 la met en évidence.

Démonstration. Démontrons la seconde forme, qui contient la première — il suffit d'y prendre $A=\varnothing$, ensemble contenu dans tout arbre couvrant minimal, et n'importe quelle coupe le respecte.

Soit donc $T$ un arbre couvrant minimal contenant $A$. Si $e\in T$, il n'y a rien à faire: $A\cup \{e\}\subseteq T$ et $T$ convient. Supposons donc $e=\{u,v\}\notin T$, avec et , et construisons à partir de un autre arbre couvrant minimal qui, lui, contient . C'est un : on ajoute l'arête voulue, on constate qu'un cycle apparaît, et on retire de ce cycle une arête bien choisie.

Un cycle apparaît. Puisque $T$ est un arbre couvrant, il contient un unique chemin $P$ reliant $u$ à $v$ — l'existence vient de la connexité, l'unicité de l'absence de cycle: deux chemins distincts entre les mêmes extrémités se recolleraient en un cycle. Le graphe $T\cup \{e\}$ contient donc exactement un cycle, à savoir $P$ suivi de l'arête $e$.

Ce cycle traverse la coupe au moins deux fois. Le chemin $P$ part de $u\in S$ et arrive à $v\notin S$: il quitte donc $S$ au moins une fois. Il existe par conséquent sur $P$ au moins une arête $f=\{x,y\}$ avec et , c'est-à-dire une arête de traversant la coupe. Fixons-en une.

Cette arête n'est pas dans $A$. C'est ici que sert l'hypothèse «la coupe respecte $A$»: aucune arête de $A$ ne traverse la coupe, et $f$ la traverse, donc $f\notin A$.

L'échange ne coûte rien. Posons $T^{\prime }=(T\setminus \{f\})\cup \{e\}$. C'est encore un arbre couvrant: retirer une arête d'un cycle de $T\cup \{e\}$ laisse un graphe connexe — les deux morceaux séparés par la disparition de $f$ restent reliés par le reste du cycle —, et ce graphe a de nouveau $n-1$ arêtes, donc il est sans cycle. Son poids vaut

Or $f$ et $e$ traversent toutes deux la coupe, et $e$ est de poids minimal parmi les arêtes traversantes: donc $w(e)\le w(f)$, d'où $w(T^{\prime })\le w(T)$. Comme $T$ est un arbre couvrant , on a aussi , donc et est lui aussi un arbre couvrant minimal.

Conclusion. $T^{\prime }$ contient $e$ par construction, et il contient $A$: toutes les arêtes de $A$ étaient dans $T$, et la seule que nous ayons retirée, $f$, n'appartenait pas à $A$. Donc $A\cup \{e\}\subseteq T^{\prime }$ avec arbre couvrant minimal.

Relisez la démonstration en repérant où chaque hypothèse a servi, c'est le meilleur usage qu'on puisse en faire. L'hypothèse «$e$ de poids minimal traversant» sert une seule fois, dans l'inégalité $w(e)\le w(f)$. L'hypothèse «la coupe respecte $A$» sert une seule fois aussi, pour garantir que l'arête sacrifiée n'était pas une de celles qu'on avait promis de garder. Retirez l'une ou l'autre et l'argument tombe — l'exercice 8.4 vous fait construire le contre-exemple correspondant.

La propriété de cycle, son miroir

La propriété de coupe dit quelles arêtes on peut prendre. Sa jumelle dit lesquelles on peut jeter, et elle s'obtient par le même échange, lu à l'envers.

Démonstration. Supposons par l'absurde qu'un arbre couvrant minimal $T$ contienne cette arête $e=\{u,v\}$, strictement la plus lourde du cycle $C$. Retirons $e$ de $T$: le graphe $T\setminus \{e\}$ se scinde en exactement deux composantes connexes, celle qui contient $u$, appelons-la $S$, et celle qui contient . La paire est une coupe, et la traverse.

Le cycle $C$ part de $u$, passe par $v$ et revient en $u$. Le morceau de $C$ qui relie $u$ à $v$ sans emprunter $e$ commence dans $S$ et se termine hors de $S$: il contient donc au moins une arête $f$ traversant la coupe, et puisque ce morceau évite . Comme appartient à et que est strictement la plus lourde de , on a .

Posons $T^{\prime }=(T\setminus \{e\})\cup \{f\}$. L'arête $f$ relie les deux composantes que la disparition de $e$ avait séparées, donc $T^{\prime }$ est connexe; il a $n-1$ arêtes, donc c'est un arbre couvrant. Et

ce qui contredit la minimalité de $T$. Donc aucun arbre couvrant minimal ne contient $e$. $\square$

Sur le graphe témoin, le triangle $A\text{–}B\text{–}C$ a pour poids 4, 1 et 2: l'arête $AB$, de poids 4, est strictement la plus lourde de ce cycle, donc elle n'appartient à aucun ACM. Voilà démontré, sans exécuter le moindre algorithme, ce que la figure 8.1 montre. De même, le triangle $C\text{–}D\text{–}E$ a pour poids 8, 2 et 10: l'arête $CE$ (10) est éliminée. Et le triangle $D\text{–}E\text{–}F$ avec $DF$ (6), $DE$ (2), (3) élimine .

La propriété de cycle exige la stricte supériorité, et l'exercice 8.4 vous montrera pourquoi: avec une égalité, l'arête peut appartenir à un ACM sans que l'autre cesse d'y appartenir aussi, tout simplement parce qu'il y a alors plusieurs ACM.

Kruskal: trier les arêtes, refuser les cycles

L'idée et le code

L'algorithme de Joseph Kruskal, publié en 1956, est d'une simplicité qui frise l'insolence: triez les arêtes par poids croissant, puis prenez-les une par une dans cet ordre, en refusant celles dont les deux extrémités sont déjà reliées.

Il construit donc une forêt qui grossit. Au départ, chaque sommet est seul dans sa composante — $n$ composantes, aucune arête. Chaque arête acceptée fusionne deux composantes et fait donc baisser leur nombre d'une unité; chaque arête refusée le laisse inchangé. On s'arrête quand il n'en reste qu'une, ce qui, d'après le théorème 8.1, arrive après exactement $n-1$ acceptations.

Tout repose donc sur la question: «ces deux sommets sont-ils déjà dans la même composante?» Nous allons d'abord l'implémenter naïvement, pour voir l'algorithme tourner, puis lui consacrer toute une section.

def kruskal(n, aretes):
    """ACM d'un graphe a n sommets 0..n-1. aretes : liste de (u, v, poids)."""
    composante = list(range(n))          # composante[v] : etiquette de la composante de v
    arbre = []
    for u, v, poids in sorted(aretes, key=lambda e: e[2]):
        if composante[u] != composante[v]:
            ancienne, nouvelle = composante[v], composante[u]
            for s in range(n):           # on reetiquette toute une composante
                if composante[s] 

Comptons, comme le chapitre 1 l'exige, avant de parler de classe. Le tri coûte $\Theta (m\log m)$ comparaisons. La boucle examine au plus $m$ arêtes; pour chacune, le test coûte deux lectures, et une acceptation coûte un réétiquetage en $\Theta (n)$. Comme il y a $n-1$ acceptations, le réétiquetage total coûte $\Theta (n^2)$. Le coût est donc $\Theta (m\log m+n^2)$ — acceptable ici, catastrophique sur un grand graphe creux, où écrase largement . La section sur union-find remplacera ce par un terme quasi linéaire, et c'est le seul endroit où l'algorithme a besoin d'être amélioré.

La trace, sur le graphe témoin

Pourquoi c'est correct

Démonstration. Notons $A_k$ l'ensemble des arêtes retenues après l'examen des $k$ premières arêtes de la liste triée, avec $A_0=\varnothing$. Nous démontrons par récurrence sur $k$ l'invariant:

$A_k$ est un ensemble d'arêtes sans cycle, contenu dans au moins un arbre couvrant minimal de $G$.

Initialisation. $A_0=\varnothing$ est sans cycle et contenu dans n'importe quel arbre couvrant minimal, et il en existe au moins un puisque $G$ est connexe et fini.

Hérédité. Supposons l'invariant vrai pour $A_k$ et examinons la $(k+1)$-ième arête, $e=\{u,v\}$.

Premier cas: $u$ et $v$ sont dans la même composante de la forêt $A_k$. L'algorithme refuse $e$, donc $A_{k+1}=A_k$ et l'invariant est trivialement conservé. (Il est utile de noter que ce refus est justifié: contiendrait un cycle, et ne pourrait donc être inclus dans aucun arbre.)

Second cas: $u$ et $v$ sont dans deux composantes différentes de $A_k$. L'algorithme accepte, et $A_{k+1}=A_k\cup \{e\}$. Cet ensemble est encore sans cycle, puisque l'arête ajoutée relie deux composantes jusqu'ici disjointes. Reste à montrer qu'il est contenu dans un arbre couvrant minimal, et c'est la propriété de coupe qu'il faut invoquer — encore faut-il exhiber la bonne coupe.

Prenons pour $S$ l'ensemble des sommets de la composante de $u$ dans la forêt $A_k$. C'est une partie non vide de $V$ ($u$ y est), et stricte ($v$ n'y est pas). La coupe $(S,V\setminus S)$ : une arête de qui la traverserait aurait une extrémité dans la composante de et l'autre ailleurs, ce qui est impossible puisque les arêtes de relient des sommets d'une même composante.

Il reste à voir que $e$ est de poids minimal parmi les arêtes traversant cette coupe. Soit $f$ une arête quelconque traversant $(S,V\setminus S)$. Ses deux extrémités sont dans des composantes différentes de $A_k$, donc $f$ n'appartient pas à $A_k$, donc n'a pas été retenue; et comme est la -ième de la liste triée, deux cas se présentent: ou bien vient dans la liste, et alors par construction du tri; ou bien vient , mais alors elle a déjà été examinée et refusée, ce qui signifie que ses deux extrémités étaient déjà dans la même composante au moment de son examen — donc, les composantes ne faisant que fusionner, elles y sont encore, et ne traverse pas la coupe. Contradiction. Donc toute arête traversante a un poids au moins égal à : est bien minimale sur cette coupe.

Le théorème 8.2 s'applique: $A_k\cup \{e\}=A_{k+1}$ est contenu dans un arbre couvrant minimal. L'invariant est conservé.

Terminaison et conclusion. La boucle examine les $m$ arêtes, donc elle termine. À la fin, $A_m$ est sans cycle et contenu dans un arbre couvrant minimal $T$. Il reste à voir que $A_m=T$, c'est-à-dire que l'algorithme n'a rien oublié. Supposons $A_m\ne T$ et soit : cette arête a été examinée et refusée, donc ses deux extrémités étaient déjà reliées dans ; mais , donc elles étaient déjà reliées dans , et ajouter à y créerait un cycle — or . Contradiction. Donc , et l'algorithme renvoie un arbre couvrant minimal.

Ce que cette démonstration illustre dépasse Kruskal. C'est le patron de toutes les preuves de correction d'algorithmes gloutons, que le chapitre 9 systématisera: on ne montre pas que le choix glouton est «le bon» — notion sans contenu —, on montre qu'il conserve la possibilité d'atteindre un optimum. L'invariant «ce que j'ai construit jusqu'ici est contenu dans au moins une solution optimale» est la formulation exacte de cette idée, et l'argument d'échange est l'outil qui l'établit à chaque pas.

Prim: faire grossir un seul arbre

L'idée et le code

L'algorithme de Prim — publié par Robert Prim en 1957, redécouvert par Edsger Dijkstra en 1959, mais déjà donné par Vojtěch Jarník en 1930 — procède tout autrement. Au lieu de faire grossir une forêt un peu partout, il fait grossir un seul arbre à partir d'un sommet de départ.

On part d'un sommet quelconque, disons $A$, et on maintient un ensemble $S$ des sommets déjà reliés. À chaque tour, on regarde toutes les arêtes qui traversent la coupe $(S,V\setminus S)$ et on prend la plus légère; le sommet qu'elle atteint rejoint $S$. On répète $n-1$ fois.

Dit ainsi, le lien avec la propriété de coupe est immédiat, et c'est ce qui rend Prim si facile à démontrer: à chaque tour, l'ensemble $A$ des arêtes déjà retenues est exactement l'arbre construit sur $S$, la coupe $(S,V\setminus S)$ le respecte par construction — aucune arête de l'arbre ne sort de $S$ —, et l'arête choisie est de poids minimal parmi les traversantes. Le théorème 8.2 s'applique tel quel à chaque tour, et l'invariant «$A$ est contenu dans un arbre couvrant minimal» est conservé du début à la fin. La correction de Prim tient donc en trois lignes une fois la propriété de coupe démontrée, et c'est une bonne illustration de ce qu'un bon théorème fait gagner.

Reste le problème pratique: trouver la plus légère arête traversante sans les réexaminer toutes à chaque tour. La réponse est la file de priorité du chapitre 5. On y dépose les arêtes candidates au fur et à mesure qu'un sommet rejoint $S$, et on en extrait le minimum.

import heapq


def prim(n, adjacence, depart=0):
    """ACM par croissance d'un seul arbre. adjacence[v] : liste de (voisin, poids)."""
    dans_arbre = [False] * n
    dans_arbre[depart] = True
    tas = [(poids, depart, voisin) for voisin, poids in adjacence[depart]]
    heapq.heapify(tas)
    arbre, total = [], 0
    while tas and len(arbre) < n - 1

Comptons. Chaque arête est insérée dans le tas au plus une fois par extrémité, donc au plus $2m$ insertions — en pratique moins, puisqu'on n'insère pas les arêtes menant à un sommet déjà pris. Chaque insertion et chaque extraction coûtent $O(\log (\text{taille du tas}))=O(\log m)$ comparaisons, et $\log m\le \log n^2=2\log n$, donc . Le coût total est . C'est ce qu'on appelle la variante : on laisse dans le tas des arêtes devenues inutiles et on les jette au moment de les extraire, ce que fait le . La variante garde une seule entrée par sommet et demande une file de priorité avec diminution de clé; elle est plus économe en mémoire, pas en classe de complexité.

Le même arbre — et ce que cela prouve, ou non

Deux algorithmes, deux logiques opposées, un seul résultat. Il est tentant d'en conclure que l'ACM est toujours unique, et c'est faux. Voici ce qu'on peut affirmer.

La démonstration est l'objet de l'exercice 8.5, et elle est courte: on suppose deux ACM distincts, on considère l'arête de poids minimal qui appartient à l'un et pas à l'autre, et l'argument d'échange du théorème 8.2 produit une contradiction stricte.

Sur le graphe témoin, les poids ne sont pas deux à deux distincts: $AC$ et $DE$ valent toutes deux 2, $AB$ et $FG$ valent toutes deux 4. Le théorème 8.5 ne s'applique donc pas, et pourtant l'énumération exhaustive des 144 arbres couvrants montre qu'il y en a exactement un de poids 17. Retenez la leçon logique, qui vaut bien au-delà de ce chapitre: poids distincts $\Rightarrow$ unicité, mais la réciproque est fausse. Un graphe peut avoir des poids répétés et un ACM unique, comme celui-ci; il peut aussi avoir des poids répétés et plusieurs ACM.

Que se passe-t-il exactement, alors, quand l'unicité tombe? Deux choses distinctes, qu'il faut séparer.

• Le poids de l'ACM est toujours unique. C'est la définition d'un minimum: si $T_1$ et $T_2$ sont tous deux minimaux, alors $w(T_1)=w(T_2)$. Aucun algorithme correct ne peut donc rendre un poids différent d'un autre algorithme correct, et c'est cette valeur-là, 17, qui est la vraie réponse au problème.

Un exemple concret, à faire vous-même avec l'explorateur ci-dessous: donnez à l'arête $AB$ le poids 2 au lieu de 4. Il y a alors trois arêtes de poids 2 ($AB$, $AC$, $DE$), le tri les départage par ordre alphabétique et prend $AB$ avant $AC$; $AC$ est alors refusée, et l'arbre obtenu est $\{AB,BC,BD,DE,EF,FG\}$ — , de poids , . Descendez à 1 et tout change: est prise avant sans la moindre égalité, l'ACM devient de poids , et il est de nouveau unique. Remontez à 5, 6, 7 ou 8: rien ne bouge, l'ACM reste celui de 17. C'est cohérent avec la propriété de cycle, qui élimine dès qu'elle est strictement plus lourde que , donc dès .

Union-find: la structure qui dit «déjà reliés»

Le problème, isolé

Revenons au réétiquetage en $\Theta (n)$ de notre première version de Kruskal. Ce n'est pas une maladresse d'implémentation, c'est un vrai problème algorithmique, et il mérite d'être posé pour lui-même.

Kruskal s'écrit en six lignes avec cette structure, et c'est la version qu'on écrit vraiment:

def kruskal(n, aretes):
    uf = UnionFind(n)
    arbre = []
    for u, v, poids in sorted(aretes, key=lambda e: e[2]):
        if uf.unir(u, v):                 # unir renvoie False si deja unis
            arbre.append((u, v, poids))
            if len(arbre) == n - 1:
                break
    return arbre

Le décompte qui compte, ici, n'est plus celui des comparaisons mais celui des opérations de la structure: Kruskal effectue $m$ appels à unir au plus — un par arête examinée — et donc au plus $2m$ appels à trouver, pour $n-1$ fusions effectives. Sur le graphe témoin, en s'arrêtant dès la sixième arête retenue: sept arêtes examinées, quatorze trouver, six fusions.

La forêt

La représentation naturelle est une forêt: chaque élément pointe vers un parent, chaque classe est un arbre, et le représentant de la classe est la racine de cet arbre, c'est-à-dire l'unique élément qui est son propre parent. Tout tient dans un tableau parent de taille $n$.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))       # chacun est sa propre racine

    def trouver(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def unir(self, x, y):
        a, b = self.trouver(x), self.trouver(y)
        if a ==

unir coûte deux trouver et une affectation; tout le coût est donc dans trouver, et le coût de trouver est la profondeur de l'élément dans son arbre. Dans le pire des cas, cette version est catastrophique: la suite unir(0,1), unir(1,2), …, unir(n-2, n-1) construit un peigne, une chaîne de longueur $n-1$, et un trouver sur la dernière feuille remonte $n-1$ arêtes. On a remplacé un réétiquetage en $\Theta (n)$ par une remontée en $\Theta (n)$: aucun progrès.

Deux idées, indépendantes et cumulables, corrigent cela.

Union par rang

La première idée est de ne pas accrocher n'importe quelle racine sous n'importe quelle autre. Quand on fusionne, l'arbre le plus «plat» doit passer sous le plus «profond», puisque cela ne change pas la hauteur du résultat; l'inverse l'augmenterait d'une unité. On mémorise donc pour chaque racine un entier, le rang, qui majore la hauteur de son arbre.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rang = [0] * n

    def trouver(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def unir(self, x, y):
        a, b = self

Le rang n'est pas le nombre d'éléments de la classe, et ce n'est pas non plus exactement la hauteur dès qu'on ajoutera la compression de chemin: c'est un majorant de la hauteur, qu'on maintient à peu de frais. Sa vertu tient dans un seul lemme.

Démonstration. Par récurrence sur le nombre d'opérations unir effectuées depuis la création.

Initialisation. Après creer(n), chaque élément est une racine de rang 0, à la tête d'un arbre d'un élément, et $1=2^0$.

Hérédité. Supposons la propriété vraie avant une opération unir(x, y), et examinons ce qu'elle change. Soient $a$ et $b$ les deux racines concernées, de rangs $r_a$ et $r_b$, l'algorithme ayant échangé les noms de sorte que $r_a\ge r_b$. Les arbres autres que ceux de et de ne sont pas touchés, et leurs racines gardent leur rang: la propriété y reste vraie. L'élément cesse d'être une racine, il n'y a donc rien à vérifier pour lui. Seule la racine demande un examen, et il y a deux cas.

Si $r_a>r_b$, le rang de $a$ ne change pas et reste $r_a$, tandis que son arbre ne fait que grossir: il contenait au moins $2^{r_a}$ éléments par hypothèse de récurrence, il en contient encore au moins autant. La propriété est conservée.

Si $r_a=r_b$, le rang de $a$ passe à $r_a+1$. Mais son nouvel arbre est la réunion des deux anciens, qui comptaient chacun au moins $2^{r_a}$ éléments par hypothèse de récurrence, et qui étaient disjoints. Le nouvel arbre compte donc au moins

éléments, ce qui est exactement ce qu'exige son nouveau rang. La propriété est conservée.

Conséquences. Un arbre de la structure ne peut pas contenir plus de $n$ éléments. Si une racine avait un rang $r$ tel que $2^r>n$, elle contredirait le lemme; donc $2^r\le n$, c'est-à-dire $r\le {\log }_{2}n$, et comme est entier, . Enfin, sans compression de chemin, une récurrence immédiate sur les mêmes cas montre que le rang d'une racine est à la hauteur de son arbre: la hauteur est donc elle aussi au plus , et , qui remonte de la profondeur de jusqu'à 0, effectue au plus remontées.

La borne est atteinte, et c'est important: elle n'est pas pessimiste par précaution. Avec huit éléments, la suite d'unions

produit le tableau de parents [0, 0, 0, 2, 0, 4, 4, 6], de rangs [3, 0, 1, 0, 2, 0, 1, 0], et d'une hauteur de $3={\log }_{2}8$. C'est cette forêt-là que dessine la figure 8.3.

Compression de chemin

La seconde idée est plus jolie encore, et elle ne coûte rien: puisqu'on vient de remonter tout un chemin jusqu'à la racine, autant en profiter pour le raccourcir. trouver(x) remonte de $x$ à la racine; en redescendant, on accroche directement à la racine tous les nœuds rencontrés. Le prochain trouver sur l'un d'eux coûtera une seule remontée.

    def trouver(self, x):
        racine = x
        while self.parent[racine] != racine:
            racine = self.parent[racine]
        while self.parent[x] != racine:               # seconde passe : on recable
            self.parent[x], x = racine, self.parent[x]
        return racine

La ligne self.parent[x], x = racine, self.parent[x] mérite un regard: le membre de droite est évalué entièrement avant la moindre affectation, donc x reçoit bien l'ancien parent et non la racine. C'est le même mécanisme que l'échange a, b = b, a du chapitre 6 d'Introduction à la programmation, et c'est ici qu'il évite une variable temporaire.

L'effet cumulé des deux idées est spectaculaire, et il est difficile à démontrer. Le résultat s'énonce avec la fonction $\alpha$, l'inverse de la fonction d'Ackermann.

Ce théorème est admis, et il faut dire pourquoi plutôt que de faire comme si l'omission allait de soi. La démonstration, due à Robert Tarjan en 1975, repose sur une analyse par fonction de potentiel dont les classes de rang sont définies par des tours d'exponentielles; elle occupe une dizaine de pages denses dans Cormen et al. et n'apprend, sur les arbres couvrants, strictement rien. Tarjan a de plus montré que la borne est optimale: aucune implémentation d'union-find fondée sur des pointeurs ne peut faire mieux que $\Omega (q\alpha (n))$ dans le pire des cas amorti. Ce qu'il faut retenir de l'énoncé, c'est ce que $\alpha$ est et n'est pas.

Ce que chaque algorithme coûte

Les trois termes de Kruskal, les deux de Prim

Reprenons Kruskal avec union-find, et comptons chaque phase séparément — c'est la seule manière de savoir ce qu'on peut espérer améliorer.

1. Le tri des $m$ arêtes: $\Theta (m\log m)$ comparaisons, et le chapitre 3 a démontré qu'aucun tri par comparaisons ne peut faire mieux.
2. Les $2m$ appels à trouver et les $n-1$ fusions: $O(m\alpha (n))$ au total, d'après le théorème 8.7.
3. La construction de la structure: $\Theta (n)$.

Total: $O(m\log m+m\alpha (n)+n)$. Comme $\alpha (n)$ est majoré par 4 en pratique et, de toute façon, par $\log m$, le premier terme domine et l'on écrit

Le tri domine, et c'est tout ce qu'il y a à retenir. Une conséquence pratique immédiate: si les arêtes arrivent déjà triées — elles sortent d'une base de données indexée par le coût, ou d'un calcul précédent —, ou si les poids sont de petits entiers permettant un tri par dénombrement en $\Theta (m)$ (chapitre 3), alors Kruskal devient $O(m\alpha (n))$, c'est-à-dire quasi linéaire. C'est un cas fréquent et c'est un vrai gain.

Une simplification s'impose au passage. Comme $m\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)<n^2$, on a $\log m<2\log n$, donc

et les deux écritures sont interchangeables. Ce n'est pas une coquetterie: cela montre que Kruskal et Prim avec un tas binaire sont dans la même classe de complexité, $O(m\log n)$, et que le choix entre les deux ne se décide donc pas sur la classe.

Pour Prim, le décompte a été fait plus haut: au plus $2m$ insertions et $2m$ extractions dans un tas, chacune en $O(\log n)$, plus $\Theta (n)$ d'initialisation, soit

Deux autres variantes de Prim méritent d'être connues, parce qu'elles gagnent là où la version au tas perd.

• Prim avec un simple tableau. On stocke pour chaque sommet hors de $S$ le poids de la plus légère arête qui l'y relie, et on cherche le minimum par un balayage linéaire. Chaque tour coûte $\Theta (n)$ pour le balayage et l'on fait $n$ tours, plus $\Theta (m)$ pour les mises à jour: total $\Theta (n^2+m)=\Theta (n^2)$, puisque . Aucun logarithme.

Creux ou dense: qui gagne

Prenons $n=1000$ sommets, et deux régimes. Un graphe creux, avec $m=3n=3000$ arêtes — c'est l'ordre de grandeur d'un réseau routier, d'un réseau électrique, d'un graphe de voisinage. Un graphe dense, avec $m=\left(\genfrac{}{}{0ex}{}{1000}{2}\right)=499500$ arêtes, c'est-à-dire complet — c'est le cas d'un problème de partitionnement où tout couple de points a une distance.

La lecture est nette, et elle tient en deux phrases.

Sur un graphe creux, Kruskal et Prim au tas se valent — 34 652 contre 29 897, un rapport de 1,16, entièrement dans l'épaisseur des constantes — et tous deux écrasent la version à tableau d'un facteur 30, parce que celle-ci paie $n^2$ même quand il n'y a que $3n$ arêtes. C'est le régime où les deux algorithmes sont interchangeables, et où le choix se fait sur d'autres critères: Kruskal si les arêtes sont déjà triées ou triables linéairement, si le graphe risque d'être non connexe (il rend alors la forêt couvrante minimale sans une ligne de plus), ou si l'on veut le trier une fois pour plusieurs requêtes; Prim si le graphe est donné par listes d'adjacence et qu'on ne veut pas matérialiser la liste des arêtes.

Sur un graphe dense, c'est Prim avec un tableau qui gagne, et de loin: 1 000 000 contre 4 977 909 pour Prim au tas et 9 455 598 pour Kruskal, soit un facteur 5 et un facteur 9. La raison est structurelle et vaut d'être comprise: quand $m$ est de l'ordre de $n^2$, tout algorithme qui paie un logarithme par arête paie $n^2\log n$, alors que le balayage linéaire paie $n^2$ tout court. Le tas, qui était une bonne idée pour éviter de relire les $m$ arêtes à chaque tour, devient une dépense inutile quand on doit de toute façon toutes les lire. Une structure de données sophistiquée n'est un progrès que si la structure du problème le permet, et c'est l'un des rares endroits de ce cours où le tableau plat bat le tas.

Ajoutons deux remarques honnêtes sur ce tableau. La ligne Fibonacci donne les meilleurs nombres des deux colonnes et reste, en pratique, le plus mauvais choix des quatre pour des graphes de cette taille: ses constantes cachées sont grandes et sa structure maltraite les caches, ce que le modèle RAM du chapitre 1 ne voit pas. Et la frontière entre «creux» et «dense» n'est pas à $m=n$: en égalant $m\log n$ et $n^2$, on trouve que le tableau devient préférable au tas autour de $m\approx n^2/{\log }_{2}n$, soit environ 100 000 arêtes pour — donc bien au-delà du régime creux, et un peu en deçà du graphe complet.

Synthèse

• Un arbre couvrant d'un graphe connexe à $n$ sommets est un sous-graphe connexe et sans cycle qui touche tous les sommets; le théorème 8.1 lui impose exactement $n-1$ arêtes. Chercher l'arbre couvrant minimal n'est donc pas chercher le plus petit — la taille est imposée — mais choisir lesquelles des $m$ arêtes forment ce paquet. Sur le graphe témoin, $n=7$ et $m=11$: six arêtes à choisir parmi onze, parmi 144 arbres couvrants possibles, et l'énumération n'est une méthode pour aucune taille sérieuse, puisque le graphe complet en compte $n^{n-2}$.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 21 pour les arbres couvrants minimaux, la propriété de coupe et les deux algorithmes; chapitre 19 pour union-find, dont l'analyse complète en $O(\alpha (n))$ amorti.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, utile pour fixer le vocabulaire: «coupe», «arête sûre», «ensembles disjoints».
• Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 4, qui présente la propriété de coupe sous le nom de cut property et la propriété de cycle sous celui de cycle property, avec une discussion particulièrement claire de l'unicité sous poids distincts.
• Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — section 4.3, pour les variantes paresseuse et gloutonne de Prim et pour une comparaison expérimentale des implémentations.
• Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitre 5, qui déduit les deux algorithmes d'un unique énoncé de coupe, dans l'esprit de ce chapitre.
• Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM, 1975 — l'article original de l'analyse en $\alpha (n)$ et de la borne inférieure correspondante; à consulter pour un point précis, pas comme lecture.