Algorithme de Kruskal

Trier les arêtes, prendre la plus courte, ne jamais fermer de boucle. L'algorithme de Kruskal est peut-être le plus simple des algorithmes gloutons, et pourtant il trouve toujours la façon la moins chère de relier tous les nœuds d'un graphe.

Un graphe où plusieurs morceaux d'arbre grandissent en même temps, une arête passée qui fermerait un cycle en pointillés rouges, et la liste des arêtes encore à essayer en dessous
Un graphe où plusieurs morceaux d'arbre grandissent en même temps, une arête passée qui fermerait un cycle en pointillés rouges, et la liste des arêtes encore à essayer en dessous

L'idée

Un arbre couvrant minimal relie tous les nœuds d'un graphe pondéré avec la plus petite longueur totale d'arêtes possible. L'algorithme de Kruskal ne fait pas grandir un seul arbre depuis un départ. Il regarde tout le graphe à la fois, commence avec chaque nœud comme un morceau à lui seul, et réunit les morceaux par la plus courte arête disponible jusqu'à ce qu'il n'en reste qu'un.

Pas à pas

Triez les arêtes de la plus courte à la plus longue. Essayez-les dans cet ordre. Si les deux extrémités d'une arête sont dans des morceaux différents, ajoutez-la à l'arbre : les deux morceaux n'en font plus qu'un. Si les deux extrémités sont déjà dans le même morceau, l'arête fermerait un cycle, donc on la passe. Avec n nœuds, l'arbre est complet après n − 1 arêtes, et les arêtes restantes n'ont jamais besoin d'être examinées.

Un exemple

Prenez les arêtes A–B de longueur 1, B–C 2, A–C 3, C–D 4 et B–D 5. Kruskal ajoute A–B, puis B–C, qui rattache C au morceau A–B. A–C vient ensuite, mais A et C sont déjà dans un même morceau : elle fermerait le cycle A–B–C, donc on la passe. C–D rattache D, et les quatre nœuds forment maintenant un arbre de trois arêtes, de longueur totale 7. B–D, la plus longue arête, n'est même jamais essayée.

Union-find

La seule question difficile que pose l'algorithme de Kruskal est : ces deux nœuds sont-ils déjà dans le même morceau ? Une structure union-find y répond. Chaque morceau est un petit arbre de liens qui pointent vers un représentant. Find suit les liens jusqu'au représentant ; union place un représentant sous l'autre. La compression de chemin, qui fait pointer chaque nœud visité directement vers le représentant, et l'union par taille gardent les liens si courts que chaque question prend un temps presque constant.

Histoire et vitesse

Joseph Kruskal a publié l'algorithme en 1956, dans un court article des Proceedings of the American Mathematical Society. Trier les arêtes est la partie la plus lente, donc le travail croît en E log E pour E arêtes. Si les arêtes sont déjà triées, ou si leurs longueurs sont de petits nombres entiers, il est presque linéaire.

À vous d'essayer

Ouvrez l'application et appuyez sur Étape. Les arêtes encore à essayer sont listées sous le graphe, la plus courte d'abord. Chaque arête qui relie deux morceaux devient verte ; chaque arête qui fermerait un cycle est tracée en pointillés rouges. Regardez plusieurs petits morceaux grandir dans différentes parties du graphe puis fusionner, et remarquez que les dernières arêtes ne sont souvent jamais essayées.

Questions fréquemment posées

Pourquoi l'algorithme de Kruskal trie-t-il les arêtes ?

Pour que chaque arête qu'il ajoute soit la plus courte qui relie encore deux morceaux. Ce choix glouton est toujours sûr grâce à la propriété de la coupe, et chaque arête passée est la plus longue du cycle qu'elle fermerait, donc elle n'est jamais nécessaire.

Qu'est-ce qu'une structure d'ensembles disjoints ?

Un autre nom de l'union-find : une structure qui gère une collection d'ensembles séparés, ici les morceaux de la forêt qui grandit, et qui sait dire vite à quel ensemble appartient un élément et fusionner deux ensembles.

L'algorithme de Kruskal marche-t-il sur un graphe non connexe ?

Oui. Il finit simplement avec un arbre pour chaque morceau connexe du graphe, une forêt couvrante minimale, car aucune arête ne peut relier des morceaux qui ne sont pas connectés.

L'algorithme de Kruskal sert-il à autre chose ?

L'arrêter tôt, avant que les derniers morceaux fusionnent, regroupe les nœuds en clusters : c'est le clustering à liaison simple. Le lancer sur une grille aux longueurs d'arêtes aléatoires génère un labyrinthe.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer l'algorithme de Kruskal