Algorithme de Prim
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.
