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.
El algoritmo consiste en encontrar 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.
Pseudo código del algoritmo:
La idea básica consiste en añadir, en cada paso, una arista de peso mínimo a un árbol previamente construido. Más explícitamente:
Paso 1. Se elige un vértice u de G y se considera el árbol S={u}
Paso 2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e
Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina. En caso contrario se vuelve al paso 2
Paso 1. Se elige un vértice u de G y se considera el árbol S={u}
Paso 2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e
Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina. En caso contrario se vuelve al paso 2
Referencia:
http://www.dma.fi.upm.es/gregorio/grafos/PrimKruskal/prim/prim.html
http://es.wikipedia.org/wiki/Algoritmo_de_Prim
No hay comentarios:
Publicar un comentario