Algorithme de Kruskal
Dernière mise à jour
L'algorithme de Kruskal construit un arbre couvrant minimal (MST) - l'ensemble d'arêtes le moins coûteux qui relie tous les nœuds sans cycle. Il trie toutes les arêtes par poids, puis ajoute gloutonnement l'arête la moins chère suivante tant qu'elle relie deux nœuds pas encore connectés. Appuyez sur lecture ci-dessus pour voir l'arbre grandir, une arête sûre et bon marché à la fois.
La vérification « déjà connectés ? » se fait avec une structure de données union-find (ensembles disjoints) : chaque arête est ignorée si ses deux extrémités sont déjà dans le même composant, car l'ajouter formerait un cycle. Le tri domine le coût, donnant O(E log E) au total. Kruskal brille sur les graphes creux.
Complexité en temps et en espace
| Mesure | Complexité | Notes |
|---|---|---|
| Temps | O(E log E) | Dominé par le tri des arêtes |
| Opérations union-find | ≈ O(E α(V)) | Presque constant par vérification avec compression de chemin |
| Espace | O(V + E) | Liste d'arêtes + structure d'ensembles disjoints |
| Idéal pour | Graphes creux | Fonctionne à partir d'une liste globale d'arêtes |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Trier chaque arête par poids, en ordre croissant. |
| 2 | Placer chaque nœud dans son propre composant (union-find). |
| 3 | Prendre l'arête la moins chère suivante. |
| 4 | Si ses extrémités sont dans des composants différents, l'ajouter à l'arbre et les unir. |
| 5 | Sinon, l'ignorer (elle créerait un cycle). |
| 6 | S'arrêter quand l'arbre a V − 1 arêtes. |
Exemple résolu
Graphe avec les nœuds A, B, C, D et les arêtes A-B(1), B-C(2), A-C(3), C-D(4), B-D(5). Arêtes triées : A-B(1), B-C(2), A-C(3), C-D(4), B-D(5) :
| Arête (poids) | Composants avant | Action |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | Composants différents - ajouter au MST, unir en {A,B}. |
B-C(2) | {A,B} {C} {D} | Composants différents - ajouter au MST, unir en {A,B,C}. |
A-C(3) | {A,B,C} {D} | A et C sont déjà ensemble - ignorer (formerait un cycle). |
C-D(4) | {A,B,C} {D} | Composants différents - ajouter au MST, unir en {A,B,C,D}. |
| Arrêt | {A,B,C,D} | L'arbre a V - 1 = 3 arêtes. MST = A-B, B-C, C-D, poids total 7. |
Quand utiliser l'algorithme de Kruskal
| À utiliser quand | À éviter quand |
|---|---|
| Le graphe est creux (peu d'arêtes par rapport aux nœuds). | Le graphe est dense - Prim avec un tas est généralement plus rapide. |
| Les arêtes sont déjà disponibles sous forme de liste globale triable. | Les arêtes n'arrivent que via des listes d'adjacence à parcourir par nœud. |
| Vous voulez une implémentation simple appuyée sur l'union-find. | Vous avez besoin que l'arbre grandisse depuis un nœud de départ précis. |
| Vous voulez construire une forêt couvrante d'un graphe non connexe. | Vous devez gérer des arêtes en flux sans tri complet. |
Code de Kruskal's Algorithm
Une implémentation propre et exécutable de Kruskal's Algorithm en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Kruskal's Algorithm en Python
Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)Code de Kruskal's Algorithm en JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);Code de Kruskal's Algorithm en Java
Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}Code de Kruskal's Algorithm en C++
C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}Code de Kruskal's Algorithm en C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}FAQ sur l'algorithme de Kruskal
Qu'est-ce qu'un arbre couvrant minimal ?
Un arbre couvrant minimal (MST) d'un graphe pondéré connexe est un sous-ensemble d'arêtes qui relie tous les nœuds sans cycle et avec le poids total le plus petit possible. Il a exactement
V - 1 arêtes pour V nœuds.Quelle est la différence entre l'algorithme de Kruskal et celui de Prim ?
Les deux construisent un arbre couvrant minimal de manière gloutonne. Kruskal trie toutes les arêtes globalement et ajoute la moins chère qui ne forme pas de cycle, en utilisant l'union-find. Prim fait grandir un seul arbre vers l'extérieur depuis un nœud de départ, ajoutant toujours l'arête la moins chère qui quitte l'arbre. Kruskal convient aux graphes creux ; Prim (avec un tas) aux graphes denses.
Pourquoi l'algorithme de Kruskal utilise-t-il l'union-find ?
Avant d'ajouter une arête, Kruskal doit vérifier si ses deux extrémités sont déjà connectées - ajouter une telle arête créerait un cycle. L'union-find (ensembles disjoints) répond à « sont-ils dans le même composant ? » et fusionne les composants en temps amorti quasi constant, ce qui garde l'algorithme efficace.
Quand devrais-je utiliser l'algorithme de Kruskal plutôt que celui de Prim ?
Préférez Kruskal quand le graphe est creux et que vous avez déjà toutes les arêtes sous forme de liste triable - le tri
O(E log E) est bon marché quand E est petit. L'algorithme de Prim avec un tas binaire ou de Fibonacci tend à gagner sur les graphes denses où E s'approche de V², car il évite de trier toutes les arêtes au préalable.L'algorithme de Kruskal fonctionne-t-il sur les graphes non connexes ?
Oui. Si le graphe est non connexe, Kruskal ne peut simplement pas atteindre
V - 1 arêtes et produit à la place une forêt couvrante minimale - un MST par composant connexe. Cela découle naturellement du fait que l'union-find ne fusionne jamais des nœuds sans chemin entre eux.Quelle est l'erreur la plus courante lors de l'implémentation de l'algorithme de Kruskal ?
Omettre la compression de chemin et l'union par rang de l'union-find, ce qui fait passer chaque vérification de connectivité de quasi constant à quasi linéaire et peut dominer le temps d'exécution. Une autre erreur fréquente est d'oublier d'unir réellement les deux composants après l'ajout d'une arête, ce qui laisse des arêtes ultérieures créer des cycles.
Ressources associées
Plus de visualisations
