Un arbre couvrant minimum (ACM) connecte tous les sommets d'un graphe pondéré et connexe avec le poids total minimum des arêtes et sans cycles. Kruskal et Prim sont les deux algorithmes gloutons classiques.
Trier toutes les arêtes par poids ; ajouter l'arête la moins chère qui ne forme pas de cycle.
def kruskal(n, edges): # edges: (weight, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # cheapest first
ru, rv = find(u), find(v)
if ru != rv: # no cycle -> take it
parent[ru] = rv
mst.append((u, v, w)); total += w
return mst, total
Commencer à partir d'un sommet quelconque ; ajouter répétitivement l'arête la moins chère sortant de l'arbre courant.
| Kruskal | Prim | |
|---|---|---|
| Approche | tri des arêtes + union-find | croissance à partir d'un nœud + tas |
| Temps | O(E log E) | O(E log V) |
| Optimal pour | graphes clairsemés | graphes denses |
Utiliser ACM pour la conception de réseaux — poser du câble, des tuyauteries d'eau, regroupement. Les deux sont gloutons et prouvablement optimaux ici. Kruskal a besoin d'union-find pour éviter les cycles efficacement.
ACM minimise le coût de connexion de tout — directement applicable à l'infrastructure et à la disposition des réseaux.
C'est un cas net où le glouton est prouvablement optimal, renforçant le raisonnement du choix glouton.
Kruskal montre aussi union-find, une structure avec une portée algorithmique large.