Algoritmo de Prim

El algoritmo de Prim es un algoritmo perteneciente a 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.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

Descripción

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol. Siempre se seleciona una arista luego el numero mas pequeño para pasar de una arista a otra.

El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

El algoritmo podría ser informalmente descrito siguiendo los siguientes pasos:

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)

Para hacerlo más en detalle, debe ser implementado el pseudocódigo siguiente.

Asociar con cada vértice v del grafo un número C[v] (el mínimo coste de conexión a v) y a un lado E[v] (el lado que provee esa conexión de mínimo coste). Para inicializar esos valores, se establecen todos los valores de C[v] iguales a +∞ (o a cualquier número más grande que el máximo tamaño de un lado) y establecemos cada E[v] igual a un valor "flag"(bandera) que indica que no hay ningún lado que conecte v a vértices anteriores.
Inicializar un bosque vacío F y establecer Q vértices que aún no han sido incluidos en F (inicialmente, todos los vértices).
Repetir los siguientes pasos hasta que Q esté vacío:
1. Encontrar y eliminar un vértice v de Q teniendo el mínimo valor de C[v]
2. Añadir v a F y, si E[v] no tiene el valor especial de "flag", añadir también E[v] a F
3. Hacer un bucle sobre los lados vw conectando v a otros vértices w. Para cada lado, si w todavía pertenece a Q y vw tiene tamaño más pequeño que C[w], realizar los siguientes pasos:
  1. Establecer C[w] al coste del lado vw
  2. Establecer E[w] apuntando al lado vw
Devolver F

Como se ha descrito arriba, el vértice inicial para el algoritmo será elegido arbitrariamente, porque la primera iteración del bucle principal del algoritmo tendrá un número de vértices en Q que tendrán todos el mismo tamaño, y el algoritmo empezará automáticamente un nuevo árbol en F cuando complete un árbol de expansión a partir de cada vértice conectado del grafo. El algoritmo debe ser modificado para empezar con cualquier vértice particular s para configurar C[s] para que sea un número más pequeño que los otros valores de C (por norma, cero), y debe ser modificado para solo encontrar un único árbol de expansión y no un bosque entero de expansión, parando cuando encuentre otro vértice con "flag" que no tiene ningún lado asociado.

Hay diferentes variaciones del algoritmo que difieren unas de otras en cómo implementar Q: Como una única Lista enlazada o un vector de vértices, o como una estructura de datos organizada con una cola de prioridades, más compleja. Esta elección lidera las diferencias en complejidad de tiempo del algoritmo. En general, una cola de prioridades será más rápida encontrando el vértice v con el mínimo coste, pero ello conllevará actualizaciones más costosas cuando el valor de C[w] cambie.

Pseudocódigo del algoritmo

Estructura de datos auxiliar: Cola de prioridad (se puede implementar con un heap)

   Prim (Grafo G)
       /* Inicializamos todos los nodos del grafo. 
       La distancia la ponemos a infinito y el padre de cada nodo a NULL
        Encolamos, en una cola de prioridad 
                  donde la prioridad es la distancia, 
               todas las parejas <nodo, distancia> del grafo*/
       por cada u en V[G] hacer
           distancia[u] = INFINITO
           padre[u] = NULL
           Añadir(cola,<u, distancia[u]>)
       distancia[u]=0
       Actualizar(cola,<u, distancia[u]>)
       mientras !esta_vacia(cola) hacer
           // OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
           u = extraer_minimo(cola) //devuelve el mínimo y lo elimina de la cola.
           por cada v adyacente a 'u' hacer
               si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces
                   padre[v] = u
                   distancia[v] = peso(u, v)
                   Actualizar(cola,<v, distancia[v]>)

Código en Haskell (Lenguaje funcional)

--Se implementa la estructura de datos Graph (WeightedGraph). 
--No existe como tal en el lenguaje.
import DataStructures.Graph.WeightedGraph
import Data.List(delete, minimumBy)
prim :: (Ord a) => WeightedGraph a Int -> a ->  WeightedGraph a Int
prim graph v | elem v vs == False = error"el vertice no pertenece al grafo"
             | otherwise = mkWeightedGraphEdges vs (aux graph [v] (delete v vs) [])
              where
                vs = vertices graph
aux :: (Ord a) => WeightedGraph a Int -> [a] -> [a] -> [WeightedEdge a Int] -> [WeightedEdge a Int]
aux g visited [] aristas = aristas
aux g visited nvisited aristas = aux g (v:visited) (delete v nvisited) aristas'
  where
    aristaPosibles = [WE visitado peso avisitar | (WE visitado peso avisitar) <- weigthedEdges g, elem visitado visited, elem avisitar nvisited]
    (WE c p v) = minimumBy (\(WE _ p' _) (WE _ p'' _) -> if p'<p'' then LT else GT) aristaPosibles
    aristas' = (WE c p v):aristas

Código en JAVA (Lista de Adyacencia)

// Se implementa la clase Grafo en JAVA. No existe como tal en el lenguaje.
// Implementación del Algoritmo de Prim utilizando lista de adyacencia.

public class Algoritmos {
    public Grafo<T> arbolExpMinPrim(Grafo<T> g, T inicio) {
        // Obtengo la cantidad total de vértices
        int verticesTotales = g.getVertices().size();
        Vertice<T> vOrigen = g.buscarVertice(inicio);
        if (vOrigen != null) {
            Grafo<T> gNuevo = new Grafo<>(g.isDirigido());
            g.getVertices().stream().forEach((v) -> {
                gNuevo.agregarVertice(v.getContenido());
            });
            
            // Para esta implementación, los pesos son números enteros.
            PriorityQueue<Arco<T>> cola = new PriorityQueue<>((Arco a1, Arco a2) -> Integer.compare(a1.getPeso(), a2.getPeso()));

            int cont = 0;
            
            while (cont < verticesTotales) {
                for (Iterator<Arco> it = vOrigen.getArcos().iterator(); it.hasNext();) {
                    Arco<T> arc = it.next();
                    if (!arc.getDestino().isVisitado()) {
                        cola.offer(arc);
                    }
                }
                
                Arco<T> arco = cola.poll();
                if (!arco.getDestino().isVisitado()) {
                    arco.getDestino().setVisitado(true);
                    gNuevo.agregarArco(arco.getPrevio().getContenido(), arco.getDestino().getContenido(), arco.getPeso());
                    cont ++;
                    vOrigen = arco.getDestino();
                }
            }
            return gNuevo;
            
        }
        return null;
    }
}

Código en C++

//**** Comienza Archivo grafo.h *****//
#include <vector>

using namespace std;
class Grafo
{
public:
    Grafo();
    Grafo(int nodos);
    vector< vector<int> > prim();
private:
    const int INF = numeric_limits<int>::max();
    int cantidadNodos; //cantidad de nodos
    vector< vector<int> > adyacencia; //matriz de adyacencia
};
//**** Finaliza Archivo grafo.h *****//

//**** Comienza Archivo grafo.cpp *****//
Grafo::Grafo()
{
}

Grafo::Grafo(int nodos)
{
    this->cantidadNodos = nodos;
        this->adyacencia = vector< vector<int> > (cantidadNodos);

        for(int i = 0; i < cantidadNodos; i++)
            adyacencia[i] = vector<int> (cantidadNodos, INF);
}

vector< vector<int> > Grafo :: prim(){
    // uso una copia de adyacencia porque necesito eliminar columnas
    vector< vector<int> > adyacencia = this->adyacencia;
    vector< vector<int> > arbol(cantidadNodos);
    vector<int> markedLines;
    vector<int> :: iterator vectorIterator;

    // Inicializo las distancias del arbol en INF.
    for(int i = 0; i < cantidadNodos; i++)
        arbol[i] = vector<int> (cantidadNodos, INF);

    int padre = 0;
    int hijo = 0;
    while(markedLines.size() + 1 < cantidadNodos){
        padre = hijo;
        // Marco la fila y elimino la columna del nodo padre.
        markedLines.push_back(padre);
        for(int i = 0; i < cantidadNodos; i++)
            adyacencia[i][padre] = INF;

        // Encuentro la menor distancia entre las filas marcadas.
        // El nodo padre es la linea marcada y el nodo hijo es la columna del minimo.
        int min = INF;
        for(vectorIterator = markedLines.begin(); vectorIterator != markedLines.end(); vectorIterator++)
            for(int i = 0; i < cantidadNodos; i++)
                if(min > adyacencia[*vectorIterator][i]){
                    min = adyacencia[*vectorIterator][i];
                    padre = *vectorIterator;
                    hijo = i;
                }

        arbol[padre][hijo] = min;
        arbol[hijo][padre] = min;
    }
    return arbol;
}
//**** Finaliza Archivo grafo.cpp *****//

Código en JAVA

//Se utiliza una clase Graph previamente implementada (no existe en Java)

public class Algorithms
{
    public static Graph PrimsAlgorithm (Graph g, int s)
    {
        int n = g.getNumberOfVertices();
        
        Entry[] table = new Entry [n];
        for (int v = 0; v < n; ++v)
            table [v] = new Entry ();
        table [s].distance = 0;
        
        PriorityQueue queue =
            new BinaryHeap (g.getNumberOfEdges());
            
        queue.enqueue (
            new Association (new Int (0), g.getVertex (s)));
            
        while (!queue.isEmpty ())
        {
            Association assoc = (Association) queue.dequeueMin();
            Vertex v0 = (Vertex) assoc.getValue ();
            
            int n0 = v0.getNumber ();
            if (!table [n0].known)
            {
                table [n0].known = true;
                Enumeration p = v0.getEmanatingEdges ();
                while (p.hasMoreElements ())
                {
                    Edge edge = (Edge) p.nextElement ();
                    Vertex v1 = edge.getMate (v0);
                    int n1 = v1.getNumber ();
                    Int wt = (Int) edge.getWeight ();
                    int d = wt.intValue ();
                    if (!table[n1].known && table[n1].distance>d)
                    { 
                        table [n1].distance = d;
                        table [n1].predecessor = n0;
                        queue.enqueue (
                            new Association (new Int (d), v1));
                    }
                }
            }
        }
        Graph result = new GraphAsLists (n);
        for (int v = 0; v < n; ++v)
            result.addVertex (v);
        for (int v = 0; v < n; ++v)
        {
            if (v != s)
                result.addEdge (v, table [v].predecessor);
        }
        return result;
    }
}

Código en Python

# Implementar un clase Grafo donde los vértices es un conjunto y las aristas es un conjunto de 2-subconjuntos de vértices.
# Los 2-subconjuntos se implementan con frozenset({v, w}) si v, w vértices (pues Python no admite conjuntos de conjuntos)
# Las funciones y métodos son los obvios. Si G es grafo:
#     G.vertices(): es el conjunto de vértices
#     G.aristas(): es el conjunto de aristas
#     G.adyacentes(v): es el conjunto de vértices adyacentes a un vértice v
#     G.agregar_arista(e): agrega la arista e

def prim(G: Grafo , pesos):
    # pre: pesos un diccionario donde las claves son las aristas y los valores son reales no negativos. 
    # post: devuelve mst un MST de G. 
    r = next(iter(G.vertices())) # toma un vértice de G sin quitarlo
    clave, padre = {}, {} # dos diccionarios vacíos. El primero es una "cola de prioridad". El segundo indicará quien será el padre en el MST.
    INFINITO = 2 * max(pesos.values()) # INFINITO es un valor más alto que todos los pesos
    for u in G.vertices():
        clave[u] = INFINITO 
        padre[u] = None # Cuando el algoritmo termina padre[v] será el padre de v en el MST, para los v que no son raíz (el vértice r). 
    clave[r] = 0
    cola = G.vertices()
    while cola != set({}):
        u = min([[clave[v],v] for v in cola])[1] # un vértice de cola con clave[u] mínima
        cola.remove(u)
        for v in G.adyacentes(u):
            e = frozenset({u, v})
            if v in cola and pesos[e] < clave[v]:
                padre[v] = u
                clave[v] = pesos[e]
    mst = Grafo(G.vertices(), set({})) # este va a ser el MST. Se inicializa como un grafo con todos los vértices de G y si aristas. 
    for v in mst.vertices() - {r}:
        mst.agregar_arista(frozenset({v,padre[v]}))
    return mst

Otra versión sin usar Colas

    public int[][] AlgPrim(int[][] Matriz) {  //Llega la matriz a la que le vamos a aplicar el algoritmo
        boolean[] marcados = new boolean[ListaVertices.size()]; //Creamos un vector booleano, para saber cuales están marcados
        String vertice = ListaVertices.get(0); //Le introducimos un nodo aleatorio, o el primero
        return AlgPrim(Matriz, marcados, vertice, new int[Matriz.length][Matriz.length]); //Llamamos al método recursivo mandándole 
    }                                                                                     //un matriz nueva para que en ella nos 
                                                                                          //devuelva el árbol final
    private int[][] AlgPrim(int[][] Matriz, boolean[] marcados, String vertice, int[][] Final) {
        marcados[ListaVertices.indexOf(vertice)] = true;//marcamos el primer nodo
        int aux = -1;
        if (!TodosMarcados(marcados)) { //Mientras que no todos estén marcados
            for (int i = 0; i < marcados.length; i++) { //Recorremos sólo las filas de los nodos marcados
                if (marcados[i]) {
                    for (int j = 0; j < Matriz.length; j++) {
                        if (Matriz[i][j] != 0) {        //Si la arista existe
                            if (!marcados[j]) {         //Si el nodo no ha sido marcado antes
                                if (aux == -1) {        //Esto sólo se hace una vez
                                    aux = Matriz[i][j];
                                } else {
                                    aux = Math.min(aux, Matriz[i][j]); //Encontramos la arista mínima
                                }
                            }
                        }
                    }
                }
            }
            //Aquí buscamos el nodo correspondiente a esa arista mínima (aux)
            for (int i = 0; i < marcados.length; i++) {
                if (marcados[i]) {
                    for (int j = 0; j < Matriz.length; j++) {
                        if (Matriz[i][j] == aux) {
                            if (!marcados[j]) { //Si no ha sido marcado antes
                                Final[i][j] = aux; //Se llena la matriz final con el valor
                                Final[j][i] = aux;//Se llena la matriz final con el valor
                                return AlgPrim(Matriz, marcados, ListaVertices.get(j), Final); //se llama de nuevo al método con
                                                                                               //el nodo a marcar
                            }
                        }
                    }
                }
            }
        }
        return Final;
    }
    public boolean TodosMarcados(boolean[] vertice) { //Método para saber si todos están marcados
        for (boolean b : vertice) {
            if (!b) {
                return b;
            }
        }
        return true;
    }

Demostración

Sea $G$ un grafo conexo y ponderado.

En toda iteración del algoritmo de Prim, se debe encontrar una arista que conecte un nodo del subgrafo a otro nodo fuera del subgrafo.

Ya que $G$ es conexo, siempre habrá un camino para todo nodo.

La salida $Y$ del algoritmo de Prim es un árbol porque las aristas y los nodos agregados a $Y$ están conectados.

Sea $Y_{1}$ el árbol recubridor mínimo de $G$ .

Si $Y_{1}=Y\Rightarrow Y$ es el árbol recubridor mínimo.

Si no, sea $e$ la primera arista agregada durante la construcción de $Y$ , que no está en $Y_{1}$ y sea $V$ el conjunto de nodos conectados por las aristas agregadas antes que $e$ . Entonces un extremo de $e$ está en $V$ y el otro no. Ya que $Y_{1}$ es el árbol recubridor mínimo de $G$ hay un camino en $Y_{1}$ que une los dos extremos. Mientras que uno se mueve por el camino, se debe encontrar una arista $f$ uniendo un nodo en $V$ a uno que no está en $V$ . En la iteración que $e$ se agrega a $Y$ , $f$ también se podría haber agregado y se hubiese agregado en vez de $e$ si su peso fuera menor que el de $e$ . Ya que $f$ no se agregó se concluye:

P(f)\geq P(e)

Sea $Y_{2}$ el grafo obtenido al remover $f$ y agregando $e\in Y_{1}$ . Es fácil mostrar que $Y_{2}$ conexo tiene la misma cantidad de aristas que $Y_{1}$ , y el peso total de sus aristas no es mayor que el de $Y_{1}$ , entonces también es un árbol recubridor mínimo de $G$ y contiene a $e$ y todas las aristas agregadas anteriormente durante la construcción de $V$ . Si se repiten los pasos mencionados anteriormente, eventualmente se obtendrá el árbol recubridor mínimo de $G$ que es igual a $Y$ .

Esto demuestra que $Y$ es el árbol recubridor mínimo de $G$ .

Ejemplo de ejecución del algoritmo

Descripción	No visto	En el grafo	En el árbol
Este es el grafo ponderado de partida. No es un árbol, ya que para serlo se requiere que no haya ciclos, y en este caso sí hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida.	C, G	A, B, E, F	D
El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA.	C, G	B, E, F	A, D
El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el valor más pequeño, así que marcamos el vértice F y a la arista DF.	C	B, E, G	A, D, F
El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado.	null	C, E, G	A, D, F, B
Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol.	null	C, G	A, D, F, B, E
Solo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo.	null	G	A, D, F, B, E, C
G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39.	null	null	A, D, F, B, E, C, G

Véase también

Algoritmo de Dijkstra

Referencias

R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.