jueves, 14 de julio de 2011

Extra Algoritmos - Algoritmo de prim

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

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

1 comentario: