Arêtes de l'arbre
Longueur totale
Arêtes examinées

  • Actuel
  • Dans l'arbre
  • Fermerait un cycle

En savoir plus sur l'algorithme de Kruskal

Algorithme de Kruskal

L'algorithme de Kruskal construit un arbre couvrant minimal, l'ensemble d'arêtes le moins cher qui relie tous les nœuds, de la façon la plus simple qui soit : prendre les arêtes de la plus courte à la plus longue, et garder chacune sauf si elle fermerait un cycle. Avancez pas à pas pour voir des morceaux séparés grandir et fusionner en un seul arbre, et les arêtes passées. Appuyez sur Lecture pour voir l'arbre grandir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Le nombre sur chaque arête est sa longueur. Sous le graphe se trouvent les arêtes encore à essayer, de la plus courte à la plus longue ; une arête dont les extrémités sont déjà reliées fermerait un cycle et est tracée en pointillés rouges. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas.
  2. Faites glisser le curseur d'étapes pour aller n'importe où. Les arêtes encore à essayer sont listées sous le graphe, la plus courte d'abord.
  3. Repérez les arêtes en pointillés rouges : elles fermeraient un cycle. Nouveau graphe crée un autre graphe à essayer.

Fonctionnement de l'algorithme de Kruskal

Triez toutes les arêtes de la plus courte à la plus longue. Au départ, chaque nœud est un morceau à lui seul. Essayez les arêtes dans l'ordre : si une arête relie deux morceaux différents, elle entre dans l'arbre et les deux morceaux n'en font plus qu'un ; si ses deux extrémités sont déjà dans le même morceau, elle fermerait un cycle, donc on la passe. On s'arrête quand tout forme un seul morceau, ce qui arrive après une arête de moins qu'il n'y a de nœuds, souvent bien avant d'essayer la dernière arête.

Union-find

Pour chaque arête, l'algorithme de Kruskal doit savoir si ses deux extrémités sont déjà reliées. Une structure union-find répond vite : chaque morceau a un nœud représentant, find suit les liens jusqu'à lui, et union rattache un représentant à l'autre. Avec deux astuces simples, la compression de chemin et l'union par taille, chaque question prend un temps presque constant : trier les arêtes est donc la partie la plus lente, avec un travail qui croît en E log E.

Questions fréquemment posées

Qu'est-ce que l'algorithme de Kruskal ?

Un algorithme glouton qui construit un arbre couvrant minimal en triant toutes les arêtes de la plus courte à la plus longue et en ajoutant chaque arête qui ne ferme pas de cycle avec les arêtes déjà choisies.

Comment l'algorithme de Kruskal détecte-t-il un cycle ?

Une arête ferme un cycle exactement quand ses deux extrémités sont déjà reliées par des arêtes choisies. Une structure union-find retient quels nœuds sont reliés et répond à cette question presque instantanément.

Pourquoi l'algorithme de Kruskal marche-t-il ?

Grâce à la propriété du cycle : la plus longue arête d'un cycle n'est jamais nécessaire pour un arbre couvrant minimal. Chaque arête que Kruskal passe est la plus longue du cycle qu'elle fermerait, puisque toutes les arêtes avant elle étaient plus courtes ou égales.

Quand utiliser Kruskal plutôt que Prim ?

L'algorithme de Kruskal est simple et rapide sur les graphes creux, et travaille directement sur une simple liste d'arêtes. L'algorithme de Prim convient aux graphes denses et aux graphes stockés sous forme de listes d'adjacence. Tous deux trouvent un arbre de même longueur totale.

Mon graphe est-il envoyé quelque part ?

Non. Le graphe est créé et l'arbre construit dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

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

Aller à l'éditeur