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.