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

7 thoughts on “Implementación algoritmo Prim en Python

    • Que onda Victor, cualquier comentario respecto al código y la implementación del algoritmo es bien venida :¬D , es mas es descargable y si gustas puedes poner una versión mejorada del PRIM o incluso tu propia implementación, yo creo que es lo que deberías hacer en lugar de andar molestando a la gente en tu blog (hackunispace.blogspot.com)

  1. dudo que aún leas esto, pero si lo lees, que sepas que tu código sigue ayudando gente.
    (y yo tampoco entendí el insulto del primer comentario, a mi me funcionó perfectamente)

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s