Algoritmos de Prim y de Kruskal.

Esquema del algoritmo de Kruskal usando particiones:


Simulador del algoritmo de Prim

Simulador del algoritmo de Kruskal

EJERCICIO: Implementa en C++ los algoritmos de Prim y Kruskal partiendo del mismo grafo de ejemplo del post anterior ("Un tal Prim asfaltando caminos") para verificar que la salida es correcta. Muestra el grafo de partida, el árbol de recubrimiento mínimo obtenido y el coste total de las aristas de dicha solución. Apóyate en los tipos abstractos de datos "Grafo" y, para el algoritmo de Kruskal también "Particion", basados en el paradigma orientado a objetos.

SOLUCIÓN (Prim y Kruskal)