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.

Pseudocódigo de Algoritmo

// 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 del grafo
por cada u en V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
Añadir(cola,)
distancia[u]=0
mientras cola != 0 hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el minimo 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,)

Pasos para realizar el Algoritmo

1. Se marca un nodo cualquiera, este será el nodo de partida.
2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente (nodo de partida), y marcamos el otro nodo en el que índice.
3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.
4. El proceso termina cuando tenemos todos los nodos del grafo marcados

Codigo en C++

// Declaraciones en el archivo .h
const int INF = 1000000;
int cn; //cantidad de nodos
vector< vector > ady; //matriz de adyacencia

// Devuelve la matriz de adyacencia del arbol minimo.
vector< vector > Grafo :: prim(){

// uso una copia de ady porque necesito eliminar columnas
vector< vector > adyacencia = this->ady;
vector< vector > arbol(cn);
vector markedLines;
vector :: iterator itVec;

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

int padre = 0;
int hijo = 0;
while(markedLines.size() + 1 < cn){ padre = hijo;
// Marco la fila y elimino la columna del nodo padre. markedLines.push_back(padre); 

for(int i = 0; i < cn; 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(itVec = markedLines.begin(); itVec != markedLines.end(); itVec++) for(int i = 0; i < cn; i++) if(min > adyacencia[*itVec][i]){
min = adyacencia[*itVec][i];
padre = *itVec;
hijo = i;
}

arbol[padre][hijo] = min;
arbol[hijo][padre] = min;
}

return arbol;
}

Referencias:
http://www.wikipedia.com