14 nov 2020

El algoritmo de Prim

Posted on   by

Considere un grafo $G$ conexo y no dirigido, se dice que un árbol generador es un subgrafo que contiene todos los vértices de $G$. En un grafo ponderado, el peso de un subgrafo es la suma de los pesos de cada una de las aristas en el subgrafo. Así, un árbol generador mínimo (MST por sus siglas en inglés) es un subgrafo ponderado no dirigido que es un árbol generador con peso mínimo.

Hay muchos problemas en los que se requiere hallar un MST de un grafo no dirigido. Por ejemplo, la longitud mínima del cable necesaria para conectar un conjunto de computadores en una red, puede ser determinada por un MST del grafo no dirigido que contiene todas las posibles conexiones.

El Algoritmo de Prim, es el primero y el más sencillo de los algoritmos de la teoría de grafos para encontrar un árbol generador mínimo en un grafo ponderado, conexo y no dirigido, este problema se conoce como el problema del árbol generador mínimo. 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.

Este algoritmo fue desarrollado por primera vez por el matemático checo Vojtêch Jarník, no sería hasta más tarde, en 1957, cuando aparecería publicado de forma independiente bajo la autoría del ingeniero informático estadounidense Robert C. Prim. Es él quien le dio fama y por cuyo apellido es hoy conocido. Creado durante su etapa en Bell Labs, Prim trataba de abordar el problema de cómo conectar redes, ya fueran de telecomunicaciones o de transporte y distribución, mediante un número reducido o barato de conexiones.

¿Cómo funciona el algoritmo Prim?

La solución al problema del árbol generador propuesta por Prim se basa en la idea de ir conectando vértices secuencialmente hasta alcanzarlos a todos. Si se tiene como dato de entrada un grafo no dirigido $G=(V, A, W)$, donde $V$ son los vértices, $A$ las aristas y $W$ la matriz de pesos. El algoritmo empieza a construir el árbol a partir de un vértice seleccionado arbitrariamente como punto de inicio. A continuación se itera seleccionando en cada etapa la arista de menor peso (una cualquiera si hay varias posibilidades) que une un vértice del árbol con otro que aún no está en él; luego se incorpora dicha arista y el vértice de destino al árbol. El proceso se repite hasta añadir todos los vértices, obteniendo como resultado un árbol generador cuyo peso será mínimo.

El algoritmo podría ser informalmente descrito siguiendo los siguientes pasos:

  1. Inicializar un árbol $T$ con un único vértice, elegido arbitrariamente del grafo $G$.
  2. Aumentar el árbol por una arista. Encontrar la arista de menor costo de las posibles aristas que pueden conectar el árbol a los vértices que no están aún en el árbol y agregarla al árbol.
  3. Repetir el paso 2 hasta que todos los vértices del grafo pertenezcan al árbol.

Con más detalle, se debe implementar el siguiente pseudocódigo:

Algoritmo de Prim

Input: $G=(V, A, W), s\in V$ 
1.     $V^{\top}\leftarrow \{s\}$ 
2.     $A^{\top}\leftarrow \emptyset$ 
3.     while $card(V^{\top}) < card(V)$ do: 
4.          $\displaystyle (i, j)=\operatorname*{argmin\,\,}_{(i, j)}\{w_{ij}:i\in V^{\top}, j\in V\setminus V^{\top}\}$ 
5.           $A^{\top} \leftarrow A^{\top}\cup\{(i, j)\}$ 
6.           $V^{\top} \leftarrow V^{\top}\cup\{j\}$ 
8.     end 
return: $T$, $V(T)\leftarrow V^{\top}$, $A(T)\leftarrow A^{\top}$.

Ejemplo

En la figura 1 se ilustra la ejecución del algoritmo de Prim sobre un grafo $G$. Se empieza por el vértice $v_{_0}$. Dado que $(v_{_0},v_{_1})$ es la arista de peso mínimo que incide sobre $v_{_0}$, se incluye en el árbol generador que se está construyendo (figura 1a). En la figura 1a , se añade la arista $(v_{_1}, v_{_5})$ porque es la arista más pequeña entre $\{v_{_0}, v_{_1}\}$ y $V(G)\setminus \{v_{_0}, v_{_1}\}$. Cuando hay un empate, como en la figura 1c, cualquier arista más pequeña podría funcionar bien. Se procede de esta forma hasta que se pasa por todos los vértices. El árbol generador mínimo definitivo se muestra en la figura 1f.

La complejidad de tiempo del algoritmo de Prim depende de las estructuras de datos usada para el grafo y para ordenar las aristas por peso, lo que se puede hacer usando una cola de prioridad. La siguiente muestra las opciones típicas:

  1. Para una matriz de adyacencia y un algoritmo de busqueda clásico la complejidad de ejecución es del orden de $O(\operatorname*{card\,\,}(V)^{2})$.
  2. Para una pila binaria y una lista de adyacencia la complejidad de ejecución es del orden de $O((\operatorname*{card\,\,}(V)+\operatorname*{card\,\,}(E))\log\operatorname*{card\,\,}(V))$.
  3. Para una pila de Fibonacci y una lista de adyacencia la complejidad de ejecución es del orden de $O(\operatorname*{card\,\,}(E) + \operatorname*{card\,\,}(V)log(\operatorname*{card\,\,}(V))$.

¿Cómo se implementa en Python el algoritmo de Prim?

Una forma de implementar el algoritmo de Prim es así:

In [1]:
import numpy as np
import timeit
In [2]:
from graphs import NotOrientedGraph
from graphs import Vertex

El módulo graph contiene la estructura de datos utilizada para el grafo y la puedes encontrar en el repositorio de Nerve. El resto del algoritmo es:

In [3]:
def prim(graph: NotOrientedGraph, initial_vertex: Vertex) -> NotOrientedGraph:
    """
    Input:
        graph: It's a graph not oriented and connected.
        initial_vertex: It's one vertex from graph.
    Output:
        The return is a graph not oriented and connected.
    """
    # Initialize empty edges array and empty minimum spanning tree:
    minimum_spanning_tree = dict()
    visited_vertices = list()
    edges = list()
    min_edge = (None, None, np.infty)


    # Arbitrarily choose initial vertex from graph:
    vertex = initial_vertex


    # Indices:
    start_vertex, end_vertex, weight = range(3)


    # Run prim's algorithm until we create an minimum spanning tree that
    # contains every vertex from the graph:
    
    try:
        while len(visited_vertices) < graph.num_vertices - 1:


            # Mark this vertex as visited:


            visited_vertices.append(vertex)


            # Set of potential edges:
            edges += vertex.edges


            # Find edge with the smallest weight to a vertex that has not yet
            # been visited:
            for edge in edges:
                inequality = edge[weight] < min_edge[weight]
                membership = edge[end_vertex] not in visited_vertices
                if inequality and membership:
                    min_edge = edge


            # Get the start and end node from minimum edge:
            start_min_edge = min_edge[start_vertex]
            end_min_edge = min_edge[end_vertex]
            min_weight = min_edge[weight]


            # Add the minimum edge to minimum spanning tree:
            if minimum_spanning_tree.get(start_min_edge.id):
                edge = (end_min_edge.id, min_weight)
                minimum_spanning_tree[start_min_edge.id].append(edge)
            else:
                edge = [(end_min_edge.id, min_weight)]
                minimum_spanning_tree[start_min_edge.id] = edge


            # Remove min weight edge form list of edges:
            edges.remove(min_edge)


            # Start at new vertex and reset min edge:
            vertex = end_min_edge
            min_edge = (None, None, np.infty)
            
    except Exception as e:
        print('The graph is not connected or has no edges!')


    # Return the optimal tree:
    return NotOrientedGraph(minimum_spanning_tree)

Para usar el algoritmo de Prim es necesario tener un grafo no orientado que podemos construir de la siguiente manera:

In [4]:
data = {
    'a': [('c', 0)], 
    'b': [('c', 1), ('e', 3)], 
    'c': [('a', 3), ('b', 3), ('d', 2), ('e', 1)]
}
In [5]:
graph = NotOrientedGraph(data)

La clase NotOrientedGraph tiene varios métodos que permite consultar algunas de las propiedades de nuestro grafo, a continuación veamos algunos ejemplos:

In [6]:
graph.get_vertices()
Out[6]:
['a', 'c', 'b', 'e', 'd']
In [7]:
graph.get_edges()
Out[7]:
([('a', 'c', 0),
  ('c', 'a', 3),

  ('c', 'd', 2),
  ('c', 'b', 3),
  ('c', 'e', 1),

  ('b', 'e', 3)],
  ('b', 'c', 1),

 graphs.NotOrientedGraph)
In [8]:
graph.weight_matrix()
Out[8]:
(matrix([[inf,  0., inf, inf, inf],
         [ 3., inf,  3.,  1.,  2.],

         [inf, inf, inf, inf, inf],
         [inf,  1., inf,  3., inf],

 ['a', 'c', 'b', 'e', 'd'])
         [inf, inf, inf, inf, inf]]),
In [9]:
graph.adjacency_matrix()
Out[9]:
(matrix([[0, 1, 0, 0, 0],
         [1, 0, 1, 1, 1],

         [0, 0, 0, 0, 0],
         [0, 1, 0, 1, 0],

 ['a', 'c', 'b', 'e', 'd'])
         [0, 0, 0, 0, 0]]),

Además también se necesita de un vértice inicial que para nuestro ejemplo será:

In [10]:
initial_vertex = graph.get_vertex('a')

Al ejecutar el algoritmo de Prim se obtiene un nuevo grafo conexo y no orientado:

In [11]:
tree = prim(graph, initial_vertex)

Para nuestro ejemplo, se peude verificar que en efecto el grafo obtenido pasa por todos los vertices y además también nos entrega cuales son la arista que se usando para construirlo.

In [12]:
tree.get_vertices()
Out[12]:
['a', 'c', 'e', 'd', 'b']
In [13]:
tree.get_edges()
Out[13]:
([('a', 'c', 0), ('c', 'e', 1), ('c', 'd', 2), ('c', 'b', 3)],
 graphs.NotOrientedGraph)

¿Por qué funciona el algoritmo de Prim?

A continuación vamos a establecer el siguiente resultado:

Teorema. Sea $G$ un grafo conexo, no orientado y ponderado. Entonces al aplicar el algoritmo de Prim desde cualquier vértice se obtiene un árbol de expansión con costo mínimo.

Como $G$ es un grafo conexo entonces siempre es posible encontrar una camino $r$ que une a cualquier par de vértices de $G$. Observe que para la $k$ - ésima iteración del algoritmo de Prim el subgrafo $T_{_k}$ es conexo, no orientado y ponderado. Es fácil ver ue cada par de vértices de $T_{_k}$ está conectado por exactamente un camino. Además es claro que existe una $n$ - ésima iteración, $n < \operatorname*{card\,\,}(V(G))$, donde $T_{_n}$ es un grafo que contiene todo los vértices de $G$, es decir $V(T_{_n}) )= V(G)$. Es claro que $T_{_n}$ es un árbol.

¿Es $T_{_n}$ un árbol de expansión con costo mínimo para el graho $G$? Suponga que $Y_{_1}$ es un árbol de expansión con costo mínimo para el grafo $G$. Si $T_{_n} = Y_{_1}$ entonces $T_{_n}$ es un árbol mínimo. Por otro lado si $T_{_n} \neq Y_{_1}$, entonces considera la $k$ - ésima iteración del algoritmo de Prim donde se agregó la primera arista $e$ al subgrafo $T_{_{k-1}}$ que no está en $Y_{_1}$. Observe que uno de los extremos de $e$ esta en $V(T_{_{k-1}})$ y el otro no. Como $Y_{_1}$ es un árbol de expansión con costo mínimo de $G$, entonces existe un camino $r$ en $Y_{_1}$ que une los extremos de $e$. En el camino $r$ debe existir una arista $f$ que une al subgrafo $T_{_{k-1}}$ con algún vértice que no está en $V(T_{_{k-1}})$. Observe que en la $k$ - ésima iteración en donde se agregó $e$ también era posible agregar $f$ en vez de $e$ si y sólo si el peso $w(f)$ de $f$ era menor o igual al peso $w(e)$ de $e$, como $f$ no se agregó se concluye que $w(f)\geq w(e)$.

Sea $Y_{2}$ es grafo tal que $A(Y_{_2}) = (A(Y_{_1})\setminus\{f\})\cup \{e\}$, es decir, el grafo que resulta de remover de $Y_{_1}$ la arista $f$ y agregar la arista $e$. Es fácil ver que $Y_{_2}$ es conexo, tiene el mismo número de vértices que $Y_{_1}$ y su costo total no supere al coso total de $Y_{_1}$, por lo tanto $Y_{_2}$ también es un árbol de expansión con costo mínimo de $G$ que contiene a $e$ y a todas las aristas de $T_{_{k-1}}$. Repitiendo este mismo proceso para $Y_{2}$, buscamos la $k$ - ésima iteración en el algoritmo de Prim donde se haya agregado una arista que está en $T_{_{k-1}}$ pero no está en $Y_{_2}$, eventualmente se encontrará un árbol de expansión con costo mínimo para $G$ que será igual a $T_{_n}$. Esto prueba que el árbol obtenido por el algoritmo de Prim es un árbol de expansión con costo mínimo.

Conclusiones

Una implementación simple de Prim, usando una matriz de adyacencia o una representación del grafo en una lista de adyacencia y buscando linealmente una matriz de pesos para encontrar el borde de peso mínimo para agregar, requiere un tiempo de ejecución de $O( \operatorname*{card\,\,}(V)^2)$. Sin embargo, este tiempo de ejecución se puede mejorar mucho más mediante el uso de pilas para implementar la búsqueda de aristas de peso mínimo en el bucle interno del algoritmo.

Una primera versión mejorada usa una pila para almacenar todos las del grafo de entrada, ordenados por su peso. Esto conduce a un tiempo de ejecución en el peor de los casos de $O ( \operatorname*{card\,\,} (E) \log \operatorname*{card\,\,}(E))$. Pero almacenar vértices en lugar de arista puede mejorarlo aún más. La pila debe ordenar los vértices por el peso de borde más pequeño que los conecte a cualquier vértice en el árbol de expansión mínimo parcialmente construido (MST) (o infinito si no existe tal arista). Cada vez que se elige un vértice $v$ y se agrega al MST, se realiza una operación de disminución de clave en todos los vértices $w$ fuera del MST parcial de manera que $v$ está conectado a $w$, estableciendo la clave al mínimo de su valor anterior y el costo de la arista de $(v, w)$.

Usando una estructura de datos de pila binaria simple, ahora se puede mostrar que el algoritmo de Prim se ejecuta en el tiempo $O ( \operatorname*{card\,\,}(E) \log \operatorname*{card\,\,}( V))$ donde $ \operatorname*{card\,\,}(E)$ es el número de aristas y $\operatorname*{card\,\,}(V)$ es el número de vértices. Usando una pila de Fibonacci más sofisticada, esto se puede reducir a $O ( \operatorname*{card\,\,}( E) + \operatorname*{card\,\,}( V ) \log \operatorname*{card\,\,}( V ))$, que es asintóticamente más rápido cuando el grafo es lo suficientemente denso que $\operatorname*{card\,\,}( E)$ es $\omega ( \operatorname*{card\,\,}(V))$, y el tiempo lineal cuando $\operatorname*{card\,\,}( E)$ es al menos $ \operatorname*{card\,\,}( V ) \log \operatorname*{card\,\,}( V )$. Para grafos de densidad aún mayor (que tienen al menos $c\operatorname*{card\,\,}( V )$ aristas con $c> 1$), se puede hacer que el algoritmo de Prim se ejecute en tiempo lineal de manera aún más simple, utilizando una pila d-aria en lugar de una pila de Fibonacci.

No olvides comentar y suscribirte al blog para que estés enterando de los posts que voy a ir subiendo semana a semana. También sientete en libertad de seguirme en Twitter, Github e Instagram.

Contacto

  • Participa de la canal de Nerve a través de Discord.
  • Se quieres conocer más acerca de este tema me puedes contactar a través de Classgap.
Suscribirse a: Enviar comentarios (Atom)