Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Prim
Résumé
thumb|right|Arbre couvrant de poids minimum
L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.
L'algorithme a été développé en 1930 par le mathématicien tchèque Vojtech Jarnik, puis a été redécouvert et republié par Robert C. Prim et Edsger W. Dijkstra en 1959. Ainsi, il est parfois appelé DJP algorithm, Jarník's algorithm, Prim–Jarník algorithm, ou Prim–Dijkstra algorithm.
L'algorithme consiste à faire croître un arbre depuis un sommet. On part d'un sous-ensemble contenant un sommet unique. À chaque itération, on agrandit ce sous-ensemble en prenant l'arête incidente à ce sous-ensemble de coût minimum. En effet, si l'on prend une arête dont les deux extrémités appartiennent déjà à l'arbre, l'ajout de cette arête créerait un deuxième chemin entre les deux sommets dans l'arbre en cours de construction et le résultat contiendrait un cycle.
À droite, on donne un exemple d'exécution de l'algorithme de Prim.
Le pseudo-code de l'algorithme de Prim est similaire à celui de l'algorithme de Dijkstra et utilise le type abstrait .
fonction prim(G, s)
pour tout sommet t
cout[t] := +∞
pred[t] := null
cout[s] := 0
F := file de priorité contenant les sommets de G avec cout[.] comme priorité
tant que F ≠ vide
t := F.defiler
pour toute arête t--u avec u appartenant à F
si cout[u] >= poids de l'arête entre les sommets t et u
pred[u] := t
cout[u] := poids de l'arête entre les sommets t et u
F.notifierDiminution(u)
retourner pred
Au début tous les sommets sont dans la file de priorité. La priorité est donnée par cout[.]. Autrement dit, le sommet possédant la plus faible valeur dans le tableau cout[.] sortira en premier de la file.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.