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
Como Funciona
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.
Pseudocodigo del Algoritmo con sus repectivos comentarios
// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL // Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas <nodo,distancia> del grafo por cada u en V[G] hacer distancia[u] = INFINITO padre[u] = NULL Añadir(cola,<u,distancia[u]>) distancia[u]=0 mientras cola != 0 hacer // OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor. u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola. por cada v adyacente a 'u' hacer si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces padre[v] = u distancia[v] = peso(u, v) Actualizar(cola,<v,distancia[v]>)Algoritmo de Prim
Ya que no me quiso agarrar el embed del video, aqui les dejo el link donde biene muy bien explicado el algoritmo de prim: http://www.youtube.com/watch?v=O8XEOz8FCDQ
REFERENCIAS
http://es.wikipedia.org/wiki/Algoritmo_de_Prim
No hay comentarios:
Publicar un comentario