Algorithme de Prim
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Arbre couvrant de poids minimum
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 (Dans l'intonation, les changements de fréquence fondamentale sont perçus comme des variations de hauteur : plus la fréquence est élevée, plus la hauteur perçue est haute et inversement. Chaque voyelle se caractérise par son...) un arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide composée d'un tronc qui peut...) incluant tous les sommets, tel que la somme des poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du voisinage de la Terre....) de chaque arête soit minimal. Si le graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...): 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 \in 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 (Le mot implantation peut avoir plusieurs significations :) proposée).

L'étape d'initialisation consiste à choisir au hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet...) 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 liant est un produit liquide qui agglomère des particules solides sous forme de poudre. Dans le domaine de la peinture, il permet au pigment d'une peinture de coller sur le support, il est alors...) 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é (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en...) de l'algorithme est O(A * S) avec A le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'arêtes et S le nombre de sommets.

Page générée en 0.038 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique