Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Algorithme de Prim

L'algorithme de Prim est un algorithme de théorie des graphes 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.

Algorithme

• Initialiser l'arbre avec un sommet choisi au hasard
• Créer un ensemble contenant toutes les arêtes du graphe
• Répéter jusqu'à ce que chaque arête de l'ensemble relie deux sommets de l'arbre
  • supprimer de l'ensemble une arête de poids minimal reliant un sommet faisant partie de l'arbre à un sommet ne faisant pas partie de l'arbre
  • ajouter cette arête à l'arbre

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