Prim et Kruskal servent à résoudre le même problème : trouver un arbre couvrant minimum dans un graphe pondéré. En clair, ils cherchent à relier tous les sommets avec le coût total le plus faible possible, sans créer de cycle.
La différence tient à leur stratégie. Prim part d’un sommet et agrandit progressivement un arbre. Kruskal trie toutes les arêtes par poids et ajoute les moins chères tant qu’elles ne créent pas de cycle.
Prim : on construit un arbre depuis un point de départ.
Kruskal : on sélectionne les meilleures arêtes dans tout le graphe.
Les deux algorithmes sont corrects. Le bon choix dépend surtout de la forme de vos données : liste d’adjacence, liste d’arêtes, graphe dense, graphe clairsemé, besoin d’une forêt couvrante ou non.
La réponse courte
Utilisez Prim si votre graphe est déjà représenté sous forme de liste d’adjacence et que vous voulez faire grandir l’arbre depuis un sommet de départ. Avec heapq, c’est une solution efficace et assez naturelle en Python.
Utilisez Kruskal si vos données sont déjà une liste d’arêtes, ou si vous voulez une approche simple à raisonner : trier les arêtes, puis éviter les cycles avec une structure Union-Find.
| Critère | Prim | Kruskal |
|---|---|---|
| Idée principale | Agrandir un arbre existant | Ajouter les arêtes les moins chères |
| Structure utile | File de priorité avec heapq |
Union-Find |
| Données pratiques | Liste d’adjacence | Liste d’arêtes |
| Graphe non connexe | Couvre une composante depuis le départ | Peut produire une forêt couvrante |
| Point fort | Très naturel depuis un sommet | Très clair si les arêtes sont disponibles |
Dans les tutoriels et les entretiens techniques, Kruskal est souvent apprécié parce qu’il expose bien la logique “pas de cycle”. Prim est souvent plus direct quand le graphe est déjà stocké sous forme de voisins.
Ce qu’est un arbre couvrant minimum
Un arbre couvrant minimum, souvent appelé MST pour Minimum Spanning Tree, concerne un graphe :
- non orienté ;
- pondéré ;
- connexe si l’on veut relier tous les sommets ;
- sans nécessité de conserver toutes les arêtes.
L’objectif est de garder seulement assez d’arêtes pour connecter tous les sommets, avec le poids total le plus faible.
Si un graphe contient n sommets, un arbre couvrant contient toujours n - 1 arêtes. S’il contient plus d’arêtes, il y a forcément un cycle. S’il en contient moins, tous les sommets ne sont pas reliés.
Imaginez un réseau de villes à connecter par des câbles. Chaque arête a un coût de construction. L’arbre couvrant minimum donne une manière de relier toutes les villes au coût total minimal, sans construire de liaison inutile.
Exemple de graphe utilisé
Pour comparer Prim et Kruskal, utilisons le même graphe.
aretes = [
("A", "B", 4),
("A", "C", 2),
("B", "C", 1),
("B", "D", 5),
("C", "D", 8),
("C", "E", 10),
("D", "E", 2),
("D", "F", 6),
("E", "F", 3),
]
Chaque tuple représente :
(sommet_1, sommet_2, poids)
Le graphe est non orienté : une arête entre A et B peut être parcourue dans les deux sens.
Implémenter Kruskal en Python
Kruskal commence par trier les arêtes du poids le plus faible au poids le plus élevé. Ensuite, il parcourt cette liste et ajoute une arête seulement si elle ne crée pas de cycle.
Pour détecter les cycles efficacement, on utilise Union-Find, aussi appelé structure d’ensembles disjoints.
class UnionFind:
def __init__(self, elements):
self.parent = {element: element for element in elements}
self.rank = {element: 0 for element in elements}
def find(self, element):
if self.parent[element] != element:
self.parent[element] = self.find(self.parent[element])
return self.parent[element]
def union(self, a, b):
racine_a = self.find(a)
racine_b = self.find(b)
if racine_a == racine_b:
return False
if self.rank[racine_a] < self.rank[racine_b]:
self.parent[racine_a] = racine_b
elif self.rank[racine_a] > self.rank[racine_b]:
self.parent[racine_b] = racine_a
else:
self.parent[racine_b] = racine_a
self.rank[racine_a] += 1
return True
La méthode find() retrouve le représentant d’un ensemble. La méthode union() fusionne deux ensembles si les sommets ne sont pas déjà connectés. Si deux sommets ont déjà la même racine, ajouter leur arête créerait un cycle.
Voici l’algorithme de Kruskal complet.
def kruskal(aretes):
sommets = set()
for u, v, poids in aretes:
sommets.add(u)
sommets.add(v)
uf = UnionFind(sommets)
arbre = []
cout_total = 0
for u, v, poids in sorted(aretes, key=lambda item: item[2]):
if uf.union(u, v):
arbre.append((u, v, poids))
cout_total += poids
return arbre, cout_total
mst, cout = kruskal(aretes)
print(mst)
print(cout)
Résultat possible :
[("B", "C", 1), ("A", "C", 2), ("D", "E", 2), ("E", "F", 3), ("B", "D", 5)]
13
L’ordre exact des arêtes peut varier si plusieurs arêtes ont le même poids, mais le coût minimal reste cohérent.
Implémenter Prim en Python avec heapq
Prim fonctionne autrement. On choisit un sommet de départ, puis on ajoute à chaque étape l’arête la moins chère qui relie l’arbre actuel à un nouveau sommet.
Pour cela, une file de priorité est idéale. En Python, on utilise le module heapq.
Commençons par transformer la liste d’arêtes en liste d’adjacence.
from collections import defaultdict
def construire_graphe(aretes):
graphe = defaultdict(list)
for u, v, poids in aretes:
graphe[u].append((poids, v))
graphe[v].append((poids, u))
return graphe
Puis écrivons Prim.
import heapq
def prim(aretes, depart):
graphe = construire_graphe(aretes)
visites = set()
tas = [(0, depart, None)]
arbre = []
cout_total = 0
while tas:
poids, sommet, precedent = heapq.heappop(tas)
if sommet in visites:
continue
visites.add(sommet)
if precedent is not None:
arbre.append((precedent, sommet, poids))
cout_total += poids
for poids_voisin, voisin in graphe[sommet]:
if voisin not in visites:
heapq.heappush(tas, (poids_voisin, voisin, sommet))
return arbre, cout_total
mst, cout = prim(aretes, "A")
print(mst)
print(cout)
Résultat possible :
[("A", "C", 2), ("C", "B", 1), ("B", "D", 5), ("D", "E", 2), ("E", "F", 3)]
13
Le coût total est le même que pour Kruskal : 13. L’ordre des arêtes est différent, car Prim construit l’arbre à partir de A, tandis que Kruskal raisonne globalement sur toutes les arêtes.
Pourquoi les deux donnent le même coût
Prim et Kruskal suivent deux stratégies différentes, mais elles reposent sur la même propriété des graphes pondérés : à chaque étape, il existe une arête sûre que l’on peut ajouter sans empêcher d’obtenir un arbre couvrant minimum.
Kruskal prend les arêtes les moins chères tant qu’elles ne forment pas de cycle.
Prim prend l’arête la moins chère qui sort de l’arbre déjà construit.
Dans les deux cas, l’algorithme évite les choix qui rendraient la solution inutilement coûteuse. C’est pour cela qu’ils aboutissent au même coût minimal, même si l’arbre final peut avoir une forme différente quand plusieurs arêtes ont des poids équivalents.
Comparer les complexités
Soit :
Vle nombre de sommets ;Ele nombre d’arêtes.
Avec une file de priorité, Prim a généralement une complexité :
O(E log V)
Kruskal trie les arêtes, puis applique Union-Find :
O(E log E)
Comme E est lié au nombre de sommets dans un graphe simple, on résume souvent Kruskal par un coût très proche de :
O(E log V)
En pratique, la différence ne se joue pas seulement sur la formule. Elle dépend surtout de la représentation de vos données.
Quand choisir Prim
Prim est souvent un bon choix si :
- votre graphe est déjà sous forme de liste d’adjacence ;
- vous partez naturellement d’un sommet ;
- le graphe est connexe ;
- vous voulez une construction progressive ;
- vous utilisez une file de priorité.
Exemple typique :
graphe = {
"A": [(2, "C"), (4, "B")],
"B": [(1, "C"), (4, "A")],
"C": [(2, "A"), (1, "B")],
}
Si vos données ressemblent déjà à cela, Prim s’intègre très bien.
Autre point : dans un graphe dense, où beaucoup de sommets sont reliés entre eux, Prim peut être très naturel, notamment si vous contrôlez bien la structure de priorité.
Quand choisir Kruskal
Kruskal est souvent un bon choix si :
- vos données sont déjà une liste d’arêtes ;
- vous voulez une implémentation facile à vérifier ;
- le graphe peut être non connexe ;
- vous voulez construire une forêt couvrante minimum ;
- vous avez besoin de raisonner explicitement sur les cycles.
Exemple typique :
aretes = [
("A", "B", 4),
("A", "C", 2),
("B", "C", 1),
]
Dans ce format, Kruskal est direct : on trie, puis on ajoute les arêtes une par une.
Kruskal a aussi un intérêt pédagogique fort. Il rend très visible la question centrale : “cette arête connecte-t-elle deux composantes différentes ?”
Que se passe-t-il si le graphe n’est pas connexe ?
Un arbre couvrant minimum suppose que tous les sommets peuvent être reliés. Si le graphe n’est pas connexe, il n’existe pas d’arbre couvrant unique pour tout le graphe.
Kruskal peut alors produire une forêt couvrante minimum : un arbre minimum par composante connexe.
Prim, dans la version ci-dessus, part d’un sommet et couvre seulement la composante accessible depuis ce sommet. Si vous voulez appliquer Prim à toutes les composantes, il faut le relancer depuis chaque sommet non visité.
Ce détail est important dans du code réel. Avant d’annoncer que vous avez trouvé un arbre couvrant pour tout le graphe, vérifiez que tous les sommets ont bien été visités.
def prim_couvre_tout(aretes, depart):
sommets = {u for u, _, _ in aretes} | {v for _, v, _ in aretes}
arbre, cout = prim(aretes, depart)
sommets_couverts = {depart}
for u, v, _ in arbre:
sommets_couverts.add(u)
sommets_couverts.add(v)
return sommets_couverts == sommets
Si cette fonction renvoie False, le graphe n’est pas entièrement couvert depuis le sommet de départ.
Erreurs fréquentes
Utiliser Dijkstra à la place de Prim
Prim et Dijkstra utilisent tous les deux une file de priorité, mais ils ne résolvent pas le même problème.
Dijkstra cherche les plus courts chemins depuis une source. Prim cherche un arbre couvrant minimum.
Dans Dijkstra, le poids stocké correspond à une distance cumulée depuis le départ. Dans Prim, le poids correspond seulement au coût de l’arête qui ajoute un nouveau sommet.
Cette différence est essentielle.
Oublier que le graphe est non orienté
Pour un arbre couvrant minimum classique, le graphe est non orienté. Si vous construisez une liste d’adjacence, ajoutez l’arête dans les deux sens.
graphe[u].append((poids, v))
graphe[v].append((poids, u))
Si vous oubliez la deuxième ligne, Prim risque d’ignorer des connexions.
Ne pas vérifier les cycles dans Kruskal
Kruskal ne consiste pas seulement à prendre les arêtes les moins chères. Il faut refuser celles qui créent un cycle.
if uf.union(u, v):
arbre.append((u, v, poids))
Le if est indispensable. Sans lui, vous obtenez une liste d’arêtes bon marché, mais pas forcément un arbre.
Comparer seulement le nombre d’arêtes
Un arbre couvrant doit contenir V - 1 arêtes si le graphe est connexe. Mais ce critère ne suffit pas à prouver qu’il est minimum. Il faut aussi que le coût total soit minimal et que les sommets soient bien connectés.
Mini-exercice
Prenez ce graphe :
aretes_test = [
("A", "B", 7),
("A", "D", 5),
("B", "C", 8),
("B", "D", 9),
("B", "E", 7),
("C", "E", 5),
("D", "E", 15),
("D", "F", 6),
("E", "F", 8),
("E", "G", 9),
("F", "G", 11),
]
Essayez d’abord d’appliquer Kruskal à la main :
- triez les arêtes par poids ;
- ajoutez l’arête la moins chère ;
- refusez les arêtes qui créent un cycle ;
- arrêtez-vous quand tous les sommets sont connectés.
Puis comparez avec le code :
print(kruskal(aretes_test))
print(prim(aretes_test, "A"))
Si vos deux coûts sont identiques, votre raisonnement est cohérent.
Le bon réflexe en Python
Si vous devez choisir rapidement :
- données en liste d’arêtes : commencez par Kruskal ;
- données en liste d’adjacence : commencez par Prim ;
- besoin d’expliquer les cycles : Kruskal est plus parlant ;
- besoin de partir d’un sommet précis : Prim est plus naturel ;
- graphe potentiellement non connexe : Kruskal donne plus facilement une forêt.
Dans un projet réel, testez les deux si le graphe est grand et que les performances comptent. Dans un apprentissage algorithmique, maîtriser les deux est très utile : ils montrent deux façons complémentaires de penser un même problème.
Pour aller plus loin
Ce comparatif complète plusieurs guides déjà disponibles :
- implémenter l’algorithme de Prim en Python ;
- implémenter l’algorithme de Kruskal en Python ;
- Dijkstra en Python pour trouver le plus court chemin ;
- trouver les composantes connexes en Python.
La suite logique consiste à créer un guide pilier sur les graphes en Python : parcours BFS/DFS, plus courts chemins, arbres couvrants, composantes connexes et structures comme Union-Find.
Références
- Documentation Python –
heapq - Documentation Python –
collections.defaultdict - Wikipedia – Minimum spanning tree
