Comment lancer Prim ou Kruskal 01 Construisez un graphe pondéré. Essayez le préréglage Grille (rows 4, cols 5 — 20 nœuds, 31 arêtes unitaires), un graphe Random connecté, ou Complete K₆. 02 Choisissez Prim et réglez Source , ou passez à Kruskal, qui n’a pas besoin de source. 03 Lisez le tableau. D’abord le poids total, puis les arêtes choisies, les composantes et est-forêt ; en dessous se trouve une ligne par arête choisie avec son poids. 04 Recoupez avec l’autre algorithme — les deux doivent s’accorder sur le poids total pour le même graphe. 05 Avancez l’exécution avec Play / Prev / Next ; Prim met en évidence la frontière croissante, Kruskal les arêtes acceptées et rejetées.
Exemples travaillés Valeurs telles qu’affichées par le panneau :
Graphe · algorithme
Lecture
Grille 4 × 5, Prim depuis 1-1
poids total 19 ; arêtes choisies 19 / 31 ; composantes 1 ; est forêt No
Grille 4 × 5, Kruskal
poids total 19 ; arêtes choisies 19 / 31
Random connecté (n 6, p 0.3, seed 20260730, poids max 9), Prim depuis A
poids total 16 ; choisies A–B(3), A–C(4), C–E(2), A–D(6), D–F(1) ; arêtes choisies 5 / 7
Le même graphe, Kruskal
poids total 16 ; les mêmes cinq arêtes par ordre de poids : D–F(1), C–E(2), A–B(3), A–C(4), A–D(6)
Complete K₆, Prim
poids total 5 ; arêtes choisies 5 / 15 ; arêtes A–B(1), A–F(1), A–E(1), A–D(1), A–C(1)
L’arbre couvrant minimal de la grille compte 19 arêtes unitaires pour 20 nœuds — le minimum théorique — et les deux algorithmes l’atteignent. Sur le graphe aléatoire, une seule arête suffit à vérifier la réponse à la main : D–F pèse 1 , la plus légère du graphe, donc tout arbre couvrant minimal doit la contenir, et les deux exécutions le font.
Pourquoi les deux listes diffèrent Prim et Kruskal choisissent les arêtes dans des ordres différents et, en cas d’égalité, peuvent choisir des arbres valides différents. Kruskal trie toutes les arêtes globalement, donc son tableau commence par l’arête la plus légère où qu’elle soit ; Prim ne regarde que la frontière d’un arbre en croissance, donc son tableau commence par ce qui quitte la racine en premier. Sur le graphe aléatoire, les deux produisent le même ensemble — l’arbre couvrant minimal y est unique — mais la liste de K₆ (tous les poids 1) n’est qu’un parmi de nombreux arbres parfaits : comparez le poids total et le nombre d’arêtes, pas les listes d’arêtes, quand les poids se répètent.
Limites
Un graphe déconnecté donne une forêt. La ligne est-forêt passe à Oui et le nombre de composantes reste supérieur à 1 ; la réponse est alors une forêt couvrante minimale, un arbre par composante, pas un seul arbre.
Arêtes non orientées uniquement. Prim traite un graphe orienté comme non orienté et le signale dans un avertissement ; la fusion de composantes de Kruskal est aussi une idée non orientée. Aucun des deux ne résout l’arborescence minimale orientée.
Le piège du départage Sur Complete K₆, chaque arête pèse 1 , donc chaque arbre couvrant pèse 5 ; Prim répond justement par une étoile autour de A : A–B, A–F, A–E, A–D, A–C . Lisez cette liste comme un arbre minimal, pas comme *l’*arbre minimal. La même prudence vaut pour les grilles à poids égaux : la réponse de la grille 19 est stable, mais quelles 19 arêtes unitaires apparaissent peut différer entre Prim et Kruskal alors que les deux restent corrects.
Où il est utile Vérifier une affirmation de câblage le moins cher Sur le graphe aléatoire, les deux arêtes les plus lourdes, E–F(8) et B–D(7) , sont toutes deux exclues tandis que A–D(6) est acceptée. Vérifiez un réseau proposé de la même façon : s’il paie E–F(8) en laissant la moins chère D–F(1) de côté, il n’est pas minimal.
Enseigner la propriété de coupe La grille rend le raisonnement par coupes visible : chaque arête unitaire traverse une coupe de poids 1, et les deux algorithmes en acceptent 19 sur 31 sans un seul cycle. Passez au graphe Random connecté et lancez les deux ; la lecture pas à pas montre Kruskal sautant E–F(8) parce que ses extrémités sont déjà reliées.
Confidentialité L’édition du graphe et les deux exécutions MST s’exécutent localement dans votre navigateur ; rien n’est téléversé.
Références
Wikipédia, Prim's algorithm , en.wikipedia.org (访问日期:2026-10-07)— croissance de la frontière depuis une racine.
Wikipédia, Kruskal's algorithm , en.wikipedia.org (访问日期:2026-10-07)— ordre par poids avec union-find.
Wikipédia, Minimum spanning tree , en.wikipedia.org (访问日期:2026-10-07)— propriétés de coupe et de cycle, unicité à poids distincts.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4e éd., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— algorithmes d’arbre couvrant minimal et propriété de coupe.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07