4.3.2. Árboles de expansión.
El algoritmo maneja los siguientes conjuntos:
- V: conjunto de vértices del grafo.
- U: conjunto de vértices seleccionados para el árbol en un momento dado.
- V-U: conjunto de vértices que quedan por coger.
Para calcular el siguiente vértice a coger 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 (almacenada en el array anterior).
Estructura del algoritmo de Prim
Inicialmente U={1} ? MAS_CERCANO[v] = 1. MENOR_COSTO[v] = C[1, v]
Suponemos que C[v, w] (Matriz de costes) contiene el coste de la arista (v, w)
Buscar el valor v, con valor MENOR_COSTO mínimo. Asignarle un valor muy grande (para no volver a cogerlo).
Recalcular los valores MAS_CERCANO y MENOR_COSTO de los demás nodos. Para cada w, comprobar si C[v, w] es menor que MENOR_COSTO[w].
Repetir los dos puntos anteriores hasta que se hayan añadido los n vértices.