TAD de los grafos: Algoritmo de Prim

El algoritmo de Prim calcula un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.

El algoritmo de Prim funciona de la siguiente manera:

  • Inicializar un árbol con un único vértice, elegido arbitrariamente, del grafo.
  • Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
  • Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

Usando el tipo abstracto de datos de los grafos, definir la función,

tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por

entonces

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Escribe tu solución