Algoritmo de PRIM
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
Pasos para realizar el algoritmo
1.- Se marca un nodo cualquiera, será el nodo de partido.
2.- Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.
3.- Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.
4.- El proceso termina cuando tenemos todos los nodos del grafo marcados.
Este algoritmo se usa normalmente para ahorrar recursos. Su aplicación más común es la implementación de cables de redes, de servidores, de postes de luz, etc.
Ejemplo:
Iniciamos en el nodo 0 y lo marcamos, observamos que hay dos posibles elecciones, 0-1 ó 0-3, de ellos elegimos el 0-1 pues es el que tiene el menos costo de los dos posibles caminos. Ahora tenemos dos nodos marcados, vemos las aristas incidentes en ellos y de allí elegimos la que tenga menor costo. Y continuamos así hasta que todos los nodos se marquen.
Referencias
No hay comentarios:
Publicar un comentario