L'algorithme de Prim

Très différente de l'algorithme de Kruskal, la méthode de Prim construit une coupe $[S, \, \overline{S}]$ et rajoute l'arète de poids minimal $(i,\,j),\quad i\:\in\: S$ sortant de la coupe rajoutant ainsi dans $S$ le sommet $j$.