Esquema del algoritmo de Prim:
Empezar en un vértice cualquiera v. El árbol consta inicialmente sólo del nodo v.
Del resto de vértices, buscar el que esté más próximo a v (es decir, con la arista (v, w) de coste mínimo). Añadir w y la arista (v, w) al árbol.
Buscar el vértice más próximo a cualquiera de estos dos. Añadir ese vértice y la arista al árbol de expansión.
Repetir sucesivamente hasta añadir los n vértices.
• La solución se construye poco a poco, empezando con una solución “vacía”.
• Implícitamente, el algoritmo maneja los conjuntos:
– V: Vértices del grafo.
– U: Vértices añadidos a la solución.
– V-U: Vértices que quedan por añadir.
– ¿Cómo implementar eficientemente la búsqueda: encontrar el vértice de V-U más próximo a alguno de los de U?
• Se usan dos arrays:
– MAS_CERCANO: Para cada vértice de V-U indica el vértice de U que se encuentra más próximo.
– MENOR_COSTO: Indica el costo de la arista más cercana.
–
Estructura del algoritmo de Prim: C[v, w] Matriz de costos
1. Inicialmente U= {1}. MAS_CERCANO[v]= 1.
MENOR_COSTO[v]= C[1, v], para v= 2..n
(en este caso se supone que se inicia desde el vértice 1, pero puede ser desde cualquier otro vértice v)
2. Buscar el nodo v, con MENOR_COSTO mínimo.
Asignarle un valor muy grande (para no volver a cogerlo).
3. Recalcular MAS_CERCANO y MENOR_COSTO de los nodos
de V-U. Para cada w de V-U, comprobar si C[v, w] es menor que MENOR_COSTO[w].
4. Repetir los dos puntos anteriores hasta que se hayan añadido los n nodos.
Pseudocódigo del Algoritmo de Prim
Prim (Grafo G, nodo inicial s)
visitado [n] = { false , . . . , false } / / indica si un nodo ya fue visitado
distancia [n] = { Infinito , . . . , Infinito } / / guarda las distancias de cada nodo al conjunto visitado
para cada w en V[G] hacer
si existe arista entre s y w entonces
distancia [w] = peso (s, w)
distancia [s] = 0
visitado [s] = true
mientras que no estén visitados todos hacer
v = nodo de menor distancia del conjunto que no ha sido visitado aun ( iterar el arreglo)
visitado [v] = true
para cada w en los vecinos de v hacer
si distancia[w] > peso (v, w) entonces
distancia [w] = peso (v, w)
padre[w] = v
finsi
finpara
finmientras
Consultar el siguiente Link:
https://elibro.bibliotecabuap.elogim.com/es/ereader/bibliotecasbuap/50117?page=503