Algorithme de Prim - Définition

Arbre couvrant de poids minimum

L'algorithme de Prim est un algorithme déterminant un arbre couvrant minimal d'un graphe connexe valué. C'est-à-dire qu'il trouve un sous-ensemble d'arêtes formant un arbre incluant tous les sommets, tel que la somme des poids de chaque arête soit minimal. Si le graphe n'est pas connexe l'algorithme ne déterminera l'arbre couvrant minimal que d'une composante connexe du graphe. Il a été conçu en 1957 par Robert Prim.

Principe

L'algorithme consiste à choisir arbitrairement un sommet et à faire croître un arbre à partir de ce sommet. Chaque augmentation se fait de la manière la plus économique possible.

Algorithme

 
 Procedure PRIM 
 Parametres locaux: entier s , graphe G 
 Parametres globaux: graphe T 
 Variables: 
 entier i, m, y 
 reel: v 
 ensemble: M 
 TvectNent: pp 
 TvectNReel: d 
 Debut 
 1  T <- graphe_vide 
 2  M <- ensemble_vide 
 3  Pour i <- 0 jusqu'à N Faire 
 4    d[i] <- cout(s, i, G) 
 5    pp[i] <- s 
 6    M <- Ajouter (i,M) 
 7  Fin pour 
 8  M <- Supprimer (s,M) 
 9  Tant que M <> Ensemble_vide Faire 
 10   m <- Choisir (M,d) 
 11   M <- Supprimer (m,M) 
 12   z <- pp[m] 
 13   v <- cout (m,z,G) 
 14   T <- Ajout arrete  de cout v à T 
 15   Pour i <-1 jusqu'à d° m dans G Faire 
 16     y <- i ieme_succ_de m dans G 
 17     Si y  M et (cout(m,y,G) < d[y]) alors 
 18       d[y] <- cout(m,y,G) 
 19       pp[y] <- m 
 20     Fin Si 
 21   Fin Pour 
 22 Fin Tant que 
 Fin algo 
 

(Attention le principe suivant differe de l'implémentation proposée).

L'étape d'initialisation consiste à choisir au hasard un sommet. Au bout de la première étape, on se retrouve ainsi avec un arbre contenant 1 sommet et 0 arête. Ensuite, on construit récursivement l'arbre minimal de la façon suivante : à l'étape n, ayant déjà construit un arbre contenant n sommets et n-1 arêtes, on établit la liste de toutes les arêtes liant un sommet de l'arbre à un sommet qui n'est pas sur l'arbre. On choisit alors une arête de poids minimal, que l'on rajoute à l'arbre ; l'arbre contient à présent n+1 sommets et n arêtes. L'algorithme se termine lorsque tous les sommets du graphe sont contenus dans l'arbre.

La complexité de l'algorithme est O(A * S) avec A le nombre d'arêtes et S le nombre de sommets.