ALGORITMO DE PRIM.

Pseudo código del algoritmo:

La idea básica consiste en añadir, en cada paso, una arista de peso mínimo a un árbol previamente construido. Más explícitamente:
    Paso 1. Se elige un vértice u de G y se considera el árbol S={u}
    Paso 2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e
    Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina. En caso contrario se vuelve al paso 2

Demostración de la validez del algoritmo

Análisis de la complejidad
· Primera aproximación
    En el paso 2, si S tiene k vértices hay n-k vértices en V-S. Por tanto, necesitamos hallar la arista de mínimo peso entre k(n-k) aristas. Como k(n-k)<(n-1)2, el coste resulta O(n2). Pero el bucle del paso 2 se repite n-1 veces luego la complejidad es O(n3)
· Segunda aproximación
    Una buena estructura de datos mejora la complejidad. Consideremos las listas S y Z=V-S. A cada vértice de Z le etiquetamos inicialmente así:
                t(z)=w(uz)     si existe la arista uz,
t(z)=¥    si no existe
    Ahora en el paso 2, se elige el vértice z de Z con etiqueta mínima, se halla v ÎS tal que t(z)= w(vz) , se añade z a S y se actualizan las etiquetas de los vértices de Z así:
                t(x):=min{t(x), w(zx)}
    Ahora, en cada paso el mínimo se calcula entre n-k etiquetas. Y así el coste total es
                            (n-1)+(n-2)+…+1=n(n-1)/2 ÎO(n2)

Applet Java:

Funcionamiento:
    El algoritmo se ejecuta paso a paso haciendo click en la región del applet.
    - Primero se selecciona un vertice (vértice activo).
    - Se marcan en amarillo las aristas que pueden pertenecer al árbol.
    - Se elige la arista mas barata, en relación a las etiquetas de peso para alcanzar cada vértice. Estas etiquetas se sitúan en cada momento junto a cada vértice.
    - Se cambia el nodo activo.

    El grafo sobre el que trabaja el algoritmo esta generado aleatoriamente.
    Una vez acabada la ejecución del algoritmo, se puede volver a ejecutar desde el principio, ya que el estado de todos los vértices y aristas se inicializa de nuevo.