next up previous
suivant: Démonstration unifiée monter: Les algorithmes de recherche précédent: L'algorithme de Kruskal

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$.

Bruno Garcia 2000-12-17