Mate discreta

Árboles de expansión mínima

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ánetiquetadas.

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ínimoposible. 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 1930por 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 estambién conocido como algoritmo DJP o algoritmo de Jarnik.

Pseudocódigo del Algoritmo de PRIM

PRIM (Grafo G, nodo_fuente s)
// inicializamos todos los nodos del grafo. La distancia laponemos 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 todoslos 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 deprioridad
u = extraer_minimo(cola)
for v ∈ adyacencia[u] do
if ((v ∈ cola) && (distancia[v] > peso(u, v)) do
padre[v] = udistancia[v] = peso(u, v)

Código en C

void Prim(int grafo[N][N])
{
int MENOR_COSTO[N];
int MAS_CERCANO[N];
int i,j,k,min;
printf("\n Arbol de extension obtenidomediante el algoritmo de Prim:\n");
printf(" (Se indican las aristas y sus costos correspondientes)\n");
printf(" ----------------------------------------------------------\n\n");...