Algorithme de Prim
Dernière mise à jour
L'algorithme de Prim construit un arbre couvrant minimal (MST) - l'ensemble d'arêtes le moins cher reliant tous les nœuds sans cycle - en faisant croître un seul arbre vers l'extérieur à partir d'un nœud de départ. À chaque étape, il examine toutes les arêtes qui traversent de l'arbre vers un nœud extérieur et ajoute la moins chère. Appuyez sur lecture ci-dessus pour voir l'arbre s'étendre, en prenant toujours l'arête de plus faible poids qui atteint un nouveau nœud.
Comme il choisit toujours l'arête de coupe minimale, chaque ajout est sûr (garanti de faire partie d'un MST). Avec une file de priorité basée sur un tas binaire indexée par l'arête la moins chère vers chaque nœud extérieur, Prim s'exécute en O(E log V). Il contraste avec Kruskal, qui trie toutes les arêtes globalement au lieu de faire croître un seul arbre connexe.
Complexité en temps et en espace
| Implémentation | Complexité | Notes |
|---|---|---|
| Tas binaire | O(E log V) | File de priorité des arêtes de coupe |
| Matrice d'adjacence | O(V²) | Plus simple ; adaptée aux graphes denses |
| Espace | O(V + E) | Appartenance à l'arbre + file de priorité |
| Idéal pour | Graphes denses | Croît à partir d'un seul nœud de départ |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Démarrez l'arbre avec un seul nœud quelconque. |
| 2 | Examinez toutes les arêtes qui traversent de l'arbre vers un nœud extérieur. |
| 3 | Choisissez l'arête de coupe de plus faible poids. |
| 4 | Ajoutez cette arête et son nouveau nœud à l'arbre. |
| 5 | Répétez jusqu'à ce que tous les nœuds soient dans l'arbre. |
Exemple résolu
Construction du MST d'un graphe à 4 nœuds avec les arêtes A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, en partant de A :
| Étape | Arbre | Arêtes de coupe | Arête choisie |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (poids 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (poids 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (poids 4) |
| 4 | {A, B, C, D} | aucune - tous les nœuds dans l'arbre | terminé : poids du MST 1+2+4 = 7 |
Quand utiliser l'algorithme de Prim
| À utiliser quand | À éviter quand |
|---|---|
| Vous avez besoin d'un arbre couvrant minimal d'un graphe connexe, non orienté et pondéré. | Le graphe est orienté ou vous avez besoin des plus courts chemins - utilisez Dijkstra ou Bellman-Ford. |
Le graphe est dense (E proche de V²) ; la forme matricielle O(V²) est simple et rapide. | Le graphe est creux et les arêtes sont déjà triées ou faciles à trier - Kruskal est souvent plus simple. |
| Vous voulez que l'arbre croisse d'une région vers l'extérieur (par ex. disposition incrémentale d'un réseau). | Le graphe est déconnecté - Prim ne couvre qu'un composant ; vous avez besoin d'une forêt couvrante minimale. |
| Vous disposez déjà d'une structure d'adjacence et d'une file de priorité. | Vous devez détecter des cycles sur un ensemble global d'arêtes - union-find (Kruskal) convient mieux à ce cas. |
Code de Prim's Algorithm
Une implémentation propre et exécutable de Prim'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 Prim's Algorithm en Python
1import heapq2
3
4def prim(graph, start):5 visited = {start}6 heap = [(w, start, v) for v, w in graph[start]]7 heapq.heapify(heap)8 mst, total = [], 09 while heap and len(visited) < len(graph):10 w, u, v = heapq.heappop(heap)11 if v in visited:12 continue13 visited.add(v)14 mst.append((u, v, w))15 total += w16 # Offer the new node's edges to the frontier17 for neighbor, weight in graph[v]:18 if neighbor not in visited:19 heapq.heappush(heap, (weight, v, neighbor))20 return mst, total21
22
23graph = {24 "A": [("B", 4), ("C", 1)],25 "B": [("A", 4), ("C", 3), ("D", 2)],26 "C": [("A", 1), ("B", 3), ("D", 5)],27 "D": [("B", 2), ("C", 5), ("E", 7)],28 "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33 print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)Code de Prim's Algorithm en JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { A: 4, C: 1, D: 5 },4 C: { A: 2, B: 1, D: 8, E: 10 },5 D: { B: 5, C: 8, E: 2 },6 E: { C: 10, D: 2 },7};8
9function prim(start) {10 const inTree = new Set([start]);11 const mst = [];12 let total = 0;13 while (inTree.size < Object.keys(graph).length) {14 // JS has no built-in heap: scan all crossing edges for the cheapest15 let best = null;16 for (const u of inTree) {17 for (const [v, w] of Object.entries(graph[u])) {18 if (!inTree.has(v) && (best === null || w < best[2])) {19 best = [u, v, w];20 }21 }22 }23 const [u, v, w] = best;24 inTree.add(v);25 mst.push(`${u}-${v} (${w})`);26 total += w;27 }28 return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);Code de Prim's Algorithm en Java
1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 List<List<int[]>> adj = new ArrayList<>();9 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10 int[][] edges = {11 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13 };14 for (int[] e : edges) {15 adj.get(e[0]).add(new int[]{e[1], e[2]});16 adj.get(e[1]).add(new int[]{e[0], e[2]});17 }18
19 boolean[] inMst = new boolean[n];20 // Always grow the tree along the cheapest crossing edge21 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22 pq.add(new int[]{0, 0}); // {node, edge weight}23 int total = 0, taken = 0;24 while (!pq.isEmpty() && taken < n) {25 int[] cur = pq.poll();26 if (inMst[cur[0]]) continue;27 inMst[cur[0]] = true;28 total += cur[1];29 taken++;30 for (int[] edge : adj.get(cur[0])) {31 if (!inMst[edge[0]]) pq.add(edge);32 }33 }34 System.out.println("MST nodes reached: " + taken);35 System.out.println("MST total weight: " + total);36 }37}Code de Prim's Algorithm en C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7 std::vector<std::vector<std::pair<int, int>>> adj = {8 {{1, 2}, {3, 6}}, // 09 {{0, 2}, {2, 3}, {3, 8}, {4, 5}}, // 110 {{1, 3}, {4, 7}}, // 211 {{0, 6}, {1, 8}}, // 312 {{1, 5}, {2, 7}}, // 413 };14 int n = static_cast<int>(adj.size());15 std::vector<bool> inMST(n, false);16 using State = std::pair<int, int>; // (edge weight, node)17 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18 pq.push({0, 0});19 int total = 0, picked = 0;20 // Always grow the tree along the cheapest crossing edge21 while (!pq.empty() && picked < n) {22 auto [w, u] = pq.top();23 pq.pop();24 if (inMST[u]) continue;25 inMST[u] = true;26 total += w;27 ++picked;28 std::cout << "Add node " << u << " (edge weight " << w << ")\n";29 for (auto [v, weight] : adj[u]) {30 if (!inMST[v]) pq.push({weight, v});31 }32 }33 std::cout << "MST total weight: " << total << "\n";34 return 0;35}Code de Prim's Algorithm en C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Undirected weighted graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 2, 0, 6, 0},11 {2, 0, 3, 8, 5},12 {0, 3, 0, 0, 7},13 {6, 8, 0, 0, 0},14 {0, 5, 7, 0, 0},15 };16 int key[N], parent[N];17 bool inMST[N] = {false};18 for (int v = 0; v < N; v++) {19 key[v] = INF;20 parent[v] = -1;21 }22 key[0] = 0;23 int total = 0;24 // O(V^2) scan for the cheapest crossing edge (no heap needed here)25 for (int iter = 0; iter < N; iter++) {26 int u = -1;27 for (int v = 0; v < N; v++) {28 if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29 }30 inMST[u] = true;31 total += key[u];32 if (parent[u] != -1) {33 printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34 }35 for (int v = 0; v < N; v++) {36 if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37 key[v] = w[u][v];38 parent[v] = u;39 }40 }41 }42 printf("MST total weight: %d\n", total);43 return 0;44}FAQ sur l'algorithme de Prim
Quelle est la complexité temporelle de l'algorithme de Prim ?
O(E log V). Une version plus simple avec matrice d'adjacence qui balaie l'arête de coupe minimale à chaque étape est en O(V²), ce qui peut être plus rapide sur les graphes denses. Les deux utilisent un espace O(V + E).Quelle est la différence entre les algorithmes de Prim et de Kruskal ?
Tous deux trouvent un arbre couvrant minimal de manière gloutonne. Prim fait croître un seul arbre connexe à partir d'un nœud de départ, en ajoutant à répétition l'arête la moins chère qui quitte l'arbre (à l'aide d'une file de priorité). Kruskal considère toutes les arêtes triées par poids et ajoute la moins chère qui ne forme pas de cycle (à l'aide de union-find). Prim est souvent préféré sur les graphes denses, Kruskal sur les graphes creux.
L'algorithme de Prim trouve-t-il toujours le MST optimal ?
Oui. À chaque étape, l'arête la moins chère qui traverse l'arbre actuel est sûre à ajouter - elle appartient à un arbre couvrant minimal (la propriété de coupe). Ajouter à répétition des arêtes sûres donne un véritable arbre couvrant minimal, à condition que le graphe soit connexe.
Quand devrais-je utiliser l'algorithme de Prim plutôt que celui de Kruskal ?
O(V²) évite de trier les E arêtes et fait croître un seul arbre à partir d'un nœud de départ. Kruskal brille sur les graphes creux où trier la liste d'arêtes est peu coûteux et où union-find garde les vérifications de cycles rapides. Les deux produisent un MST correct, donc le choix dépend surtout de la densité des arêtes et des structures de données dont vous disposez déjà.Le nœud de départ affecte-t-il le MST obtenu ?
Non - le poids total du MST est le même quel que soit le nœud de départ, car le poids de l'arbre couvrant minimal d'un graphe connexe est unique. Les arêtes précises ne peuvent différer que lorsque plusieurs arêtes partagent le même poids et que plusieurs MST existent. Sinon, Prim atteint exactement le même arbre quel que soit le nœud de départ.
L'algorithme de Prim peut-il gérer les graphes déconnectés ?
Pas directement. Prim fait croître un seul arbre, il ne couvre donc que le composant connexe contenant le nœud de départ et laisse le reste intact. Pour couvrir chaque composant, vous exécuteriez Prim à répétition à partir d'un nœud non visité, produisant une forêt couvrante minimale plutôt qu'un seul arbre.
Ressources associées
Plus de visualisations
