Algoritmo de Prim

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 elgrafo 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 conocidocomo algoritmo DJP o algoritmo de Jarnik.



Descripción conceptual[editar]
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.
El árbol recubridormínimo está completamente construido cuando no quedan más vértices por agregar.
Pseudocódigo del algoritmo[editar]
Estructura de datos auxiliar: Cola = Estructura de datos 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 deprioridad
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 !esta_vacia(cola) hacer
// ATENCIÓN: Se entiende por mayor prioridad aquel nodo cuyadistancia[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,)
Código en C++[editar]
//**** Comienza Archivografo.h *****//
#include

using namespace std;
class Grafo
{
public:
Grafo();
Grafo(int nodos);
vector< vector > prim();
private:
const int INF = -1;
int cn; //cantidad de nodos
vector< vector > ady; //matriz de adyacencia
};

//**** Finaliza Archivo grafo.h *****//


//**** Comienza Archivo grafo.cpp *****//

Grafo::Grafo()
{

}

Grafo::Grafo(intnodos)
{
this->cn = nodos;
this->ady = vector< vector > (cn);

for(int i = 0; i < cn; i++)
ady[i] = vector (cn, INF);
}

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 =...

Leer documento completo

Regístrate para leer el documento completo.