Es un algoritmo de 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.
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, en la actualidad el algoritmo de Prim es útil en diversas ramas de la ciencia, como en la rama de optimización, ya que es una de las bases para diferentes algoritmos mas sofisticados, con el mismo principio pero más eficaces.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.
Referencias:
http://es.wikipedia.org/wiki/Algoritmo_de_Prim
http://www.slideshare.net/abrahamjso/algoritmo-de-prim
No hay comentarios:
Publicar un comentario