Algoritmo de Prim

El algoritmo de Prim

Es un algoritmo de la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.


Pseudo-código

PRIM (Grafo G, nodo_fuente s)
     // inicializamos todos los nodos del grafo. La distancia la ponemos a infinito
     // y el padre de cada nodo a NULL
      for each u ∈ V[G] do
          distancia[u] = INFINITO
          padre[u] = NULL
      distancia[s]=0
      //encolamos todos los nodos del grafo
      Encolar(cola, V[G])
      while cola != 0 do
          // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición 
          // de Cola de prioridad
          u = extraer_minimo(cola)
          for v ∈ adyacencia[u] do
              if ((v ∈ cola) && (distancia[v] > peso(u, v)) do
                  padre[v] = u
                  distancia[v] = peso(u, v)

En español:

• Como debemos tener un vértice de partida, tomamos este vértice y armamos una lista con las aristas de sus adyacentes.
  Esa lista la confeccionamos en orden descendiente según su costo.
• Tomamos la arista de menor costo (siempre y cuando, al agregar esta arista, no generemos un ciclo) y la agregamos a nuestro árbol.
• Para el siguiente paso, vamos a tener que utilizar el vértice que acabamos de colocar, agregamos las aristas adyacentes de éste de la misma manera que lo hicimos anteriormente.
• Y así sucesivamente hasta tener todos los vértices del grafo, dentro del A.C.C.M.

fuente: wikipedia (pseudo-código) y apuntes mios