Page 84 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Utilizando como grafo a la figura 3.2, en la siguiente imagen se muestra la forma en que trabaja el
método Prim (figura 3.3). El árbol de expansión tiene un costo de 105.

Figura 3.3. Solución paso a paso del árbol de expansión mínima (Horowitz y Sahni, 1978)

El algoritmo inicia con un árbol que incluye solo un borde con costo mínimo de G. Entonces, las
aristas serán adicionadas al árbol una por una. La siguiente arista (i, j) a ser adicionada es tal que el
vértice i se encuentra incluido en el árbol, j es el vértice aún no incluido y el costo (i, j) es mínimo sobre
todas las aristas (k, l), donde el vértice k es parte del árbol y el vértice l no se encuentra en el árbol.
Para determinar este vértice (i, j) en forma eficiente, nosotros asociamos por cada vértice j aún no
incluido en el árbol un valor NEAR(j). NEAR(j) es un vértice en el árbol tal que costo (j, NEAR(j)) es
mínimo sobre todas las elecciones para NEAR(j). Se define NEAR(j) = 0 para todos los vértices j que
se encuentran en el árbol. La siguiente arista a incluir es definida por el vértice j, tal que NEAR(j) ≠ 0 (j
no se encuentra aún en el árbol) y costo (j, NEAR(j)) es mínimo. El algoritmo 3.3 muestra la estrategia
Prim para el árbol de expansión mínima:

78