Algorithme de Prim

Carte Commune · n° 221096

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.

Lire sur Wikipédia · Image L’auteur n’a pas pu être identifié automatiquement. Il est supposé qu'il s'agit de : Dcoetzee (étant donné la revendication de droit d’auteur)., Public domain