Implementación algoritmo Prim en Python

Marco teórico:

El algoritmo de Prim 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.
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 [?] .

Implementación en Python:

http://gist.github.com/218222

prim code

Corrida de ejemplo:

Para la corrida de ejemplo necesitamos un archivo de entrada el cual describa un grafo para esto he elegida el grafo de la documentacion de wikipedia http://es.wikipedia.org/wiki/Algoritmo_de_Prim .

Grafo a utlizar (Extraido de Wikipedia)

Grafo a utlizar (Extraido de Wikipedia)

Ahora necesitamos insertale al algorimo el grafo par este caso hemos generado el siguiente archivo denominado grafo el cual tine el siguinente formato (nodoA nodoB pesoEntreAyB), veamos el grafo que describe la imagen antes mostrada.

A B 7
A D 5
B C 8
B E 7
D E 15
D F 6
F E 8
F G 11
E G 9
C E 5
B D 9

Pasos:

Paso 1:Ninguna de las aristas está marcada, y el vértice A ha sido elegido arbitrariamente como el punto de
partida.
Paso 2: El Primer vértice es el más cercano a A es D está a 5 de distancia,ya que B se localiza a una
distancia de 7, así que marcamos la arista [(A,D),5] y el nodo A como visitado.
Paso 3: Ahora que solo conoce al Nodo A y D el nodo siguiente por conocer es F a travez de la arista
3
[(D,F),6].
Paso 4: Conociendo B a traves [(A,B),7]
Paso 5: Conociendo E a traves [(B,E),7]
Paso 6: Conociendo C a traves [(C,E),5]
Paso 7: Conociendo G a traves [(E,G),9]

salida en linea de comando

Por ultimo muestro la salida en linea de comandos al ejecutar el script.

usuario@host$./prim.py
archivo de entrada: ’grafo’
A B 7
A D 5
B C 8
B E 7
D E 15
D F 6
F E 8
F G 11
E G 9
C E 5
B D 9
Se inicio el algoritmo PRIM con el nodo A
Conociendo D a traves [(A,D),5]
Conociendo F a traves [(D,F),6]
Conociendo B a traves [(A,B),7]
Conociendo E a traves [(B,E),7]
Conociendo C a traves [(C,E),5]
Conociendo G a traves [(E,G),9]
Arbol de expansion minima:
[(A,D),5]
[(C,E),5]
[(D,F),6]
[(A,B),7]
[(B,E),7]
[(E,G),9]

Decargar Codigo
Anuncios