Algorithme de Prim: l'arbre couvrant de poids minimum
1. On selecte un sommet quelconque comme racine, par ex A.
2. Parmi les arêtes pendantes (un seul sommet dans l'arbre), selectionner la plus petite
3. Ajouter son sommet pendant à l'arbre
4. Revenir en (2)
5. On s'arrête quand il n'y a plus d'arêtes à selectionner .

Cliquer à l'intérieur du graphe pour avoir l'arbre couvrant de poids minimum.
Résultat ?




Accueil