1 jul 2011

Algoritmo de Prim

Algoritmos Computacionales 
Tarea 1 

El Algoritmo de Prim es de los más conocidos en la teoría de grafos cuyo principal objetivo consiste en encontrar el árbol de expansión mínima en un cierto grafo, que debe ser conexo, no dirigido y cuyas aristas están etiquetadas.

Pero para entender esto, veamos que son estos conceptos:

Grafo - Se define como un conjunto de objetos llamados vértices o nodos y la unión de pares de vértices por líneas llamadas aristas, que pueden ser orientadas o no. Orientadas quiere decir si se indica la dirección en que se puede mover de vértice a vértice.

Conexo - Quiere decir que todos los pares de vértices deben de estar unidos por un camino o arista.


No dirigido - Es decir, que no se indica hacia dónde se mueve.

Aristas etiquetadas - Que nos indiquen un peso, cuota o distancia entre vértices.

Sin embargo este no es el único algoritmo que existe para encontrar el árbol de expansión mínima, ya que existe otro como lo es el:

  • Algoritmo de Kruskal

Ejemplo de grafo conexo, no dirigido y con aristas etiquetadas


Cada punto negro es un vértice o nodo, y se le suele asignar una letra para hacer referencia a cada uno. También es posible encontrar grafos donde sus vértices se indican con números, esto no afecta en nada.

"Sea V el conjunto de nodos de un grafo pesado no dirigido. El algoritmo de Prim comienza cuando se asigna a un conjunto U de nodos un nodo inicial perteneciente a V, en el cual crece un árbol de expansión, arista por arista. En cada paso se localiza la arista más corta (u,v) que conecta a U con V-U, y después se agrega v, el vértice en V-U, a U. Este paso se repite hasta que V=U. El algoritmo de Prim es de O(N^2), donde |V| = N."

En otras palabras:

"Este algoritmo construye un árbol agregando aristas de manera iterativa hasta que se obtiene un árbol de expansión mínima. El algoritmo comienza con un solo vértice. Después, en cada iteración, agrega al árbol actual una arista de peso mínimo que no completa un ciclo."

Aplicaciones en la vida real

Este algoritmo puede ser utilizado en muchos campos como lo son las carreteras, vías férreas, aéreas o marítimas. También en redes eléctricas o de telefonía.

Actualmente empresas con servicios de cable e internet que necesitan expandirse lo más posible por toda una ciudad, hacen uso de estos algoritmos para seleccionar las rutas cuyos caminos sean los mas cortos y que generen un ahorro en el uso de cable como la fibra óptica.


En este caso el resultado de encontrar el camino de mínima expansión sería el siguiente:


Un ejemplo simple imaginable sería el querer viajar en auto por carretera a ciertas ciudades y buscar los caminos que generan distancias más cortas entre ciudades, en el menor tiempo posible o viajando la mínima cantidad de horas.

Ejemplo de ejecución

Obtenido de Wikipedia, al final se encuentra el enlace.
Image Descripción No visto En el grafo En el árbol
Prim Algorithm 0.svg Este es el grafo ponderado de partida. No es un árbol ya que requiere que no haya ciclos y en este grafo los hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida. C, G A, B, E, F D
Prim Algorithm 1.svg El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA. C, G B, E, F A, D
Prim Algorithm 2.svg El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el valor más pequeño, así que marcamos el vértice F y a la arista DF. C B, E, G A, D, F
Prim Algorithm 3.svg El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado. null C, E, G A, D, F, B
Prim Algorithm 4.svg Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol. null C, G A, D, F, B, E
Prim Algorithm 5.svg Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo. null G A, D, F, B, E, C
Prim Algorithm 6.svg G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39. null null A, D, F, B, E, C, G

Código y ejecución



El código primero abre desde un archivo de texto los pares de vértices y la distancia entre ellos, para luego acomodar los valores en un arreglo.

Las iteraciones las logré gracias al ejemplo en C++ del blog de Ankit.

Esta es la captura de los datos de entrada, guardados en un archivo.


El grafo se ve de esta manera:


Ejecución:


El resultado obtenido como distancia mínima fue de 12.

El resultado obtenido fue:


Esto fue todo por hoy, para dudas o correcciones, dejen su comentario.

Bibliografía:
Libro: Matemáticas Discretas - Richard Johnsonbaugh (págs.398-401)
Algoritmos básicos de Grafos
Teoría de Grafos
Algoritmo de Prim

Blogs consultados:
Jonathan De La Rosa
Ankit Agrawal

7 comentarios:

  1. Te castigo con un punto por creer todo lo que dice wikipedia.
    17.

    ResponderEliminar
  2. Siempre me castiga a mi =/

    ResponderEliminar
  3. Hola , muy buen post .. tendrias por casualidad el codigo en c implementado ? para probarlo

    Gracias!

    ResponderEliminar
  4. pasa el codigo para revisarlo xfa

    ResponderEliminar
  5. xq da error en la parte de visitado dice que necesita un constructor o algo as

    ResponderEliminar
  6. Hola, alguien de ustedes tiene el código completo del algoritmo prim? estoy teniendo problemas para implementarlo, se lo agradecería mucho, saludos

    ResponderEliminar
  7. #Oliver Montoya Arestegui

    import numpy as np

    #grafo en documento grafo.txt
    #0 3 1 0 0 0 0 0
    #3 0 0 1 0 0 5 0
    #1 0 0 0 0 5 0 0
    #0 1 0 0 4 2 0 0
    #0 0 0 4 0 0 2 1
    #0 0 5 2 0 0 0 3
    #0 5 0 0 2 0 0 0
    #0 0 0 0 1 3 0 0




    ##sacar matrix y guardarla en matriz
    matriz=np.loadtxt('grafo.txt',skiprows=0)
    #print matriz
    #print A[0][3]
    ####guarda em B todos los primers valores de la matriz
    A,B,C,D,E,F,G,H=np.loadtxt('grafo.txt',skiprows=0,unpack=True)



    vertices = {0}
    ##T
    temporal = []
    ##U
    con = {0}
    ##
    aux = 99
    u = 1
    v = 1
    for i in range(8):
    print "vertices",vertices
    vertices.update({i})
    print "vertices2", vertices

    ##Inicio de Algoritmo
    while (con != vertices):
    # V-u
    verMenosU = vertices.difference(con)
    print "vermenos",verMenosU
    # Arista de costo Minimo
    for i in con:
    for j in verMenosU:
    if (matriz[i][j] < aux and matriz[i][j]>0):
    u = i
    v = j
    aux = matriz[u][v]

    temporal.append([u + 1, v + 1])
    print "CON", con
    con.update({v})
    aux = 99
    print "CON2", con
    print "temporal",temporal

    print ("El arbol es: "),
    print temporal

    ResponderEliminar