Algoritmo de Prim

Algoritmo de Prim
En el algoritmo de Kruskal, la función de selección escoge las aristas por orden creciente de longitud, sin preocuparse demasiado por su conexión con las aristas seleccionadasanteriormente, salvo que se tiene cuidado para no formar nunca un ciclo. El resultado es un bosque de árboles que crece al azar, hasta que finalmente todas las componentes del bosque se fusionan en unúnico árbol. En el algoritmo de Prim, por otra parte, el árbol de recubrimiento mínimo crece de forma natural, comenzando por una raíz arbitraria se detiene cuando se han alcanzado todos los nodos.
SeaB un conjunto de nodos, y sea T un conjunto de aristas. Inicialmente, B contiene un único nodo arbitrario, y T esta vacío. En cada paso, el algoritmo de Prim busca la arista más corta posible {u,v}tal que u ∈ B y v ∈ N\B. Entonces añade v a B y {u, v} a T. De esta manera las aristas de T forman en todo momento un árbol de recubrimiento minimo para los nodos de B. Continuamos mientras B ≠ N. lOque sigue es un enunciado informal del algoritmo:
Función Prim { G = : grafo; longitud A →+): conjunto de aristas
{Iniciación}
T←∅≠
B ← {un miembro arbitrario de N}
Mientras B ≠ N hacerBuscar e = {u, v} ce longitud mínima tal que
u∈ B y v∈ N\B
T ← T U {e}
B ← B U {v}
Devolver T

Para ilustrar este algoritmo, considérese una vez más el grafo de la figura 6.2.Arbitrariamente, seleccionamos el nodo uno como nodo inicial. Ahora el algoritmo podría progresar en la forma siguiente:
Paso {u,v} B
Inicialización - {1}
1 {1,2}{1,2}
2 {2,3} {1,2,3}
3 {1,4} {1,2,3,4}
4 {4,5} {1,2,3,4,5}
5 {4,7} {1,2,3,4,5,7}
6 {7,6}{1,2,3,4,5,6, 7}

Cuando se detiene el algoritmo, T contiene las aristas seleccionadas {1,2}, {2,3}, {1,4},{4,5}, {4,7}, {7,6}. La demostración de que el algoritmo funciona es parecida a la demostración...