Algoritmo de prim

El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o vértices con arcos de peso mínimo del grafo sin formar ciclos.
Al igual que el algoritmo de Kruskal, el de Prim también ha sido aplicado para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros). También se ha utilizado para encontrar soluciones aproximadas a problemas NP-Hard como el del 'viajante de comercio'.
algoritmo de Prim


Consiste en dividir los nodos de un grafo en dos conjuntos: procesados y no procesados. Al principio, hay un nodo en el conjunto procesado que corresponde a el equipo central; en cada interacción se incrementa el grafo de procesados en un nodo (cuyo arco de conexión es mínimo) hasta llegar a establecer la conexión de todos los nodos del grafo a procesar. A continuación se muestra el pseudocódigo del algoritmo:

seudocodigo

Prim ( L [1..n , 1..n ]) : 'conjunto de arcos

'Inicialización: sólo el nodo 1 se encuentra en B

T =NULL 'T contendrá los arcos del árbol de extensión mínima Distmin[1]=-1

para i=2 hasta n hacer 
    más_próximo [ i ]=1 
    distmin [ i ]=L [ i , 1]

para i=1 hasta n -1 hacer 
    min=infinito

            para j=2 hasta n hacer 
                    si 0 <= distmin [ j ] < min entonces 
                    min=distmin [ j ] 
                    k=j

             T=T union {{mas_próximo [ k ], k }} 
             distmin [ k ]= -1 'se añade k a B

            para j=2 hasta n hacer 
                     si L [ j , k ] < distmin [ j ] entonces 
                    distmin [ j ]=L [ j , k ] 
                    más_próximo [ j ]=k

devolver t

El algoritmo de Prim es tal vez el algoritmo de MST (Arboles Generadores Mínimos) más sencillo de implementar y el mejor método para grafos densos. Este algoritmo puede encontrar el MST de cualquier grafo conexo pesado.
Sea V el conjunto de nodos de un grafo pesado no dirigido. El algoritmo de Prim comienza cuando se asigna a un conjunto U de nodos un nodo inicial Perteneciente a V, en el cual "crece" un árbol de expansión, arista por arista. En cada paso se localiza la arista más corta (u, v) que conecta a U con V-U, y después se agrega v, el vértice en V-U, a U. Este paso se repite hasta que V=U. El algoritmo de Prim es de O(N2), donde | V | = N.

Grafo - Se define como un conjunto de objetos llamados vértices o nodos y la unión de pares de vértices por líneas llamadas aristas, que pueden ser orientadas o no. Orientadas quiere decir si se indica la dirección en que se puede mover de vértice a vértice.

Conexo - Quiere decir que todos los pares de vértices deben de estar unidos por un camino o arista.

No dirigido - Es decir, que no se indica hacia dónde se mueve.

Aristas etiquetadas - Que nos indiquen un peso, cuota o distancia entre vértices.

video

CONCLUSION

El algoritmo de PRIM es un método para poder hallar un árbol recubridor mínimo en un grafo aciclico conexo no dirigido que nos permita hallar en un grafo el coste mínimo para una serie de actividades.


Aplicación del Algoritmo de Prim

Este algoritmo se usa normalmente para ahorrar recursos, su aplicación mas común es la implementación de cables de redes, de servidores, de postes de luz entre otros.
Es decir el Algoritmo de Prim sirve para poder hallar el "árbol recubridor mínimo", en un grafo conexo no dirigido.

Ejemplos

Aplicando el algoritmo de Prim en un problema de la vida real:
Situación: Implementación del cableado para el servicio de televisión por cable en ciertos puntos de un sector de la ciudad de Puno.
Problema: Ahorrar la mayor cantidad de cable (recursos) en los puntos estratégicos (torres de distribución) para llegar a todos los destinos deseados.
Datos: Distancia entre torres y casas es de 10 metros (cada casa)
Planteamiento: En el figura 3 se observa la ubicación de las torres de distribución y las viviendas