next up previous
suivant: Illustration par l'exemple monter: Démonstration unifiée précédent: Application à l'algorithme de

Application à l'algorithme de Kruskal

Elle est un peu plus compliquée à mettre en évidence que dans le cas de Prim. A chaque étape l'algorithme de Kruskal fusionne 2 composantes connexes de la forêt en cours de construction en rajoutant une arète de coût minimal. L'idée importante est de noter que cette arète est nécessairement de coût minimal pour une coupe particulière comme elle l'est au sein de l'ensemble des arètes encore candidates.

Bruno Garcia 2000-12-17