Gráficos en Python - Teoría e implementación - Árboles de expansión mínimos - Algoritmo de Prim

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de modo...

Los MST se usan ampliamente para calcular rutas óptimas en muchos campos diferentes. Desde una oficina de correos que calcula la ruta óptima para un cartero que necesita cubrir un área determinada, hasta empresas de telecomunicaciones a gran escala que encuentran las rutas más económicas para tender cables de comunicación.

Gracias al poder computacional en constante aumento, puede manipular gráficos más fácilmente que nunca. El estudio de estructuras de datos y algoritmos nos ha brindado una mejor comprensión del uso de gráficos, gracias a los algoritmos creados por grandes mentes a lo largo de los años.

Uno de estos algoritmos es Algoritmo de Prim. Inicialmente fue diseñado por Vojtech Jarnik en 1930, luego Robert C. Prim lo rediseñó en 1957. Este algoritmo se usa para encontrar el Árbol de expansión mínimo en un gráfico ponderado, no dirigido.

En esta lección, aprenderá cómo implementar el algoritmo de Prim en Python; cubriremos los pasos utilizados en el algoritmo y los implementaremos a través de un ejemplo funcional. Antes de eso, nos sumergiremos en las definiciones de los conceptos que necesita comprender antes de intentar implementar el algoritmo en sí: árboles, gráficos, matrices de adyacencia y árboles de expansión mínimos.

¿Qué es un árbol (de expansión mínima)? {#lo que es un árbol de expansión mínimo}

Un árbol es un tipo de gráfico, aunque no todos los gráficos son árboles. La característica principal de un árbol es que cada par de nodos está conectado por un solo camino, por lo que, a diferencia de otros tipos de gráficos, no puede haber ciclos en el gráfico: son acíclicos.

Además, los árboles son no dirigidos: no hay instrucciones estrictas entre los nodos que deba seguir. La siguiente ilustración le ayudará a obtener una comprensión intuitiva de lo que realmente es un árbol:

trees in computer science

El gráfico de la izquierda es un árbol y el de la derecha no lo es porque tiene un ciclo. Aunque es posible que no se parezca mucho a un árbol que está acostumbrado a ver en el parque, muchos árboles en realidad se parecen a ellos, ya que tienen una jerarquía desde el nodo raíz con muchas ramas y hojas. Sin embargo, para ser justos, la mayoría de los árboles en informática están al revés, con la raíz en la parte superior.

Encontrar Árbol de expansión mínimo (MST) es una ocurrencia común en el mundo real. Por lo general, es útil cuando desea encontrar la cobertura "más barata" de un área determinada. Por ejemplo, una cadena de pizzerías podría querer saber dónde abrir sus restaurantes para cubrir la mayor área de entrega, dentro de su tiempo garantizado, con el número mínimo de restaurantes abiertos, sirviendo al máximo número de personas, con el mínimo inversión, lo que resulta en el mayor retorno. El resultado es un árbol de expansión mínimo de sus restaurantes.

La misma analogía se puede transferir a varios otros dominios, incluidas las redes de suministro, las redes de telecomunicaciones, las redes eléctricas, las redes de suministro de agua y casi cualquier red de infraestructura.

{.icon aria-hidden=“true”}

Nota: En la analogía de la pizzería: el tiempo que lleva atravesar una calle es su peso, por lo que el objetivo es crear un árbol dentro de la ciudad, que conecte todos los nodos (áreas de entrega/ casas), sin ningún ciclo (lo cual es ineficiente), y que la suma de todos los pesos sea lo más baja posible. En la práctica, el "peso" de una calle es difícil de determinar, ya que es dinámico, pero se pueden realizar aproximaciones para asegurarse de que el árbol esté bien la mayor parte del tiempo.

Puede calcular un árbol de expansión mínimo para cada gráfico no dirigido que tiene pesos asignados a sus bordes. Cada uno de estos árboles cumple todas las siguientes condiciones:

  • Es un subgrafo (esto significa que el MST contiene algunas o todas las relaciones del grafo original, no más)
  • Es un árbol, lo que implica que no tiene ciclos
  • El peso MST (suma de pesos) es el peso mínimo posible de los diferentes árboles de expansión potenciales en el gráfico.

Un árbol de expansión (máximo o mínimo) conecta todos los nodos del gráfico general, pero no necesariamente todos los bordes del gráfico; algunos se evitan para reducir el costo, e incluso si no, usar todos los bordes puede convertir el camino en uno cíclico, que luego anula el propósito de un árbol.

¿Qué es una Matriz de Adyacencia?

Otro concepto que debe comprender antes de sumergirse en la implementación del algoritmo de Prim es la estructura de datos utilizada para representar un gráfico. Las relaciones en un gráfico se pueden representar de muchas maneras, pero la que es particularmente interesante cuando se implementa el algoritmo de Prim es una matriz de adyacencia.

Esta estructura muestra qué nodos están conectados a cuáles, lo que significa que ilustra la estructura de borde de un gráfico. Una matriz de adyacencia es una matriz cuadrada con dimensiones n x n, donde n es el número de nodos en el gráfico. Una vez que se define la estructura de la matriz, sus campos definen qué nodos tienen rutas conectadas a otros nodos.

Aquí está nuestro árbol de ejemplo, representado nuevamente como una matriz de adyacencia:

Hemos etiquetado cada nodo en el árbol con una letra. Además, hemos etiquetado cada fila y columna de la matriz de adyacencia correspondiente por un nodo. Por lo tanto, cada campo de la matriz de adyacencia corresponde a dos nodos. Por ejemplo, si un árbol tiene un borde entre los nodos A y B, el campo [A][B] de una matriz de adyacencia se marca con 1. Por otro lado, si no hay borde entre esos nodos, el campo [A][B] se marca con 0.

{.icon aria-hidden=“true”}

Nota: Si estás trabajando con un gráfico con pesos, puedes llenar los campos con los pesos de los bordes en lugar del 1 cuando hay una relación.

Si vuelve a mirar el árbol de ejemplo, notará que no está dirigido, lo que significa que puede atravesar cada borde desde ambas direcciones. La matriz de adyacencia ilustra eso al marcar tanto [A][B] como [B][A] cuando hay un borde entre los nodos A y B.

{.icon aria-hidden=“true”}

¿Cómo leer una matriz de adyacencia?
Cuando una matriz de adyacencia tiene un campo [A][B] lleno con el número 10, debe leerse de la siguiente manera: Un gráfico tiene un borde que conecta los nodos A y B. El peso de esa arista es 10.

Es por eso que una matriz de adyacencia de un árbol es una matriz simétrica. Puede notar una diagonal distinta (marcada en la ilustración de arriba) que divide la matriz en dos secciones reflejadas, llamadas triángulos superior e inferior.

Con este resumen, podemos entrar en el Algoritmo de Prim.

Intuición del algoritmo de Prim

En 1957, Robert C. Prim diseñó (o mejor dicho, rediseñó) una secuencia de pasos para encontrar el árbol de expansión mínimo de un gráfico utilizando pesos de ruta. Los pasos del algoritmo son estos:

  1. Seleccione un nodo aleatorio.
  2. Elija la ruta con el peso mínimo conectado al nodo elegido.
  3. El camino te llevará a un nuevo nodo, ubícate allí.
  4. Una vez que hayas formado/actualizado el árbol inicial, elige la ruta con el peso mínimo que esté conectado a todo el árbol. Ten en cuenta que debes evitar crear ciclos.
  5. Repite los pasos 3 y 4 hasta que hayas cubierto todos los vértices.

Echemos un vistazo al gráfico de ejemplo y encontremos su árbol de expansión mínimo usando el algoritmo de Prim. Este gráfico es el mismo que se usa en las lecciones sobre otros dos algoritmos para encontrar MST en un gráfico: el de Kruskal y el de Borůvka:

En primer lugar, debe elegir un nodo aleatorio para iniciar un algoritmo. En este ejemplo, digamos que optó por comenzar desde el nodo A.

Después de elegir el nodo inicial, eche un vistazo a todos los bordes que están conectados a él. En este caso, hay dos aristas de este tipo: ‘AB’ y ‘AC’. Luego, elige el que tiene el peso más pequeño: ‘AB’ e intenta agregarlo a un árbol resultante. Si forma un ciclo, lo saltas y eliges un borde con el segundo peso mínimo, etc.

En este caso, el borde AB no forma ningún ciclo, por lo que puede agregarlo a un árbol resultante:

Ahora, tienes un árbol que consta de los nodos ‘A’ y ‘B’, y el borde que conecta esos dos nodos. Nuevamente, debe observar todos los bordes conectados a los nodos del árbol que formó hasta ahora. El que tiene el peso mínimo es el filo AC. Como no crea ningún ciclo, puede agregarlo al árbol.

Después de eso, elige un nuevo borde para agregar y así sucesivamente. Echemos un vistazo a esta interesante situación que ocurre después de un par de iteraciones:

Si observa todos los bordes conectados al árbol resultante, verá que el que tiene el peso mínimo es ‘EH’. Pero si intenta agregarlo a un árbol resultante, verá que forma un ciclo. Por lo tanto, debe omitirlo y elegir el borde con el segundo peso mínimo: DG.

Después de repetir los pasos del algoritmo unas cuantas veces más, obtendrá el árbol de expansión mínimo de un gráfico resultante:

Este proceso se puede apreciar realmente a través de una animación:

Cómo implementar el algoritmo de Prim en Python

En esta sección, etiquetaremos los nodos del gráfico de ejemplo con números en lugar de letras. Eso nos ayudará a implementar el algoritmo más fácilmente:

Lo primero que debe implementar para el algoritmo de Prim es una clase Graph. Es una clase de Python que usará para representar un gráfico y todos los métodos relacionados que lo ayudarán a manipular gráficos. En este artículo, usaremos su implementación simple y la modificaremos un poco para que sea más compatible con el algoritmo de Prim:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Graph:
    def __init__(self, num_of_nodes):
        self.m_num_of_nodes = num_of_nodes
        # Initialize the adjacency matrix with zeros
        self.m_graph = [[0 for column in range(num_of_nodes)] 
                    for row in range(num_of_nodes)]

    def add_edge(self, node1, node2, weight):
        self.m_graph[node1][node2] = weight
        self.m_graph[node2][node1] = weight

Como puede ver, esta clase tiene un constructor y un método para agregar bordes a un gráfico. En este ejemplo, modificamos el constructor genérico para almacenar una cantidad de nodos en un gráfico y una matriz de adyacencia que representa un gráfico en sí mismo. Cuando se le llama, el constructor inicializará la matriz de adyacencia con todos los elementos establecidos en cero.

{.icon aria-hidden=“true”}

Nota: Hemos inicializado una matriz de adyacencia en el método __init__ utilizando la comprensión de listas. Hemos creado una lista llena de otras listas. Cada fila es otra lista y almacenamos los valores de peso allí.

El método add_edge() agrega un borde a una matriz de adyacencia. Dado que el algoritmo de Prim funciona con gráficos no dirigidos, add_edge() asegura que la matriz resultante sea simétrica.

{.icon aria-hidden=“true”}

Nota: Un atributo útil de la matriz de adyacencia de un gráfico no dirigido es que es simétrica. Esto significa que la mitad superior (sobre la diagonal del gráfico) es un espejo de la mitad inferior. Sabiendo esto significa que no tenemos que llenar toda la matriz porque habrá valores repetidos.

Algoritmo de árbol de expansión mínimo de Prim

Ahora, puedes definir el método prims_mst() dentro de la clase Graph. Lo usará para definir todos los pasos del algoritmo de Prim y, por lo tanto, producirá el MST como resultado.

Como va a comparar pesos y buscar el mínimo para el nodo inicial, debe definir el número que funciona como un mínimo temporal antes de que se asigne el primer nodo al MST. Ayuda tener este número ridículamente alto, como el infinito, para garantizar que el primer nodo que encontremos sea de menor peso y que sea seleccionado. Es por eso que definiremos un positive_inf por si acaso, aunque, en nuestro ejemplo donde se garantiza que los números estén por debajo de 10, establecer el valor temporal en 10 sería técnicamente válido.

Tenemos que rastrear los nodos seleccionados para discernir cuáles están incluidos en el MST. Una vez que todos los nodos sean parte del subgrafo, puede dejar de buscar el MST. Para lograr esto, vamos a crear otra lista de comprensión con valores booleanos: selected_nodes. Cada columna en esta nueva lista de comprensión representa un nodo. Si el nodo se eligió como parte del MST, el campo será Verdadero y Falso en caso contrario.

El resultado almacenará el árbol de expansión mínimo que es el resultado del algoritmo de Prim. Todos estos se unen en la sección principal del algoritmo: el bucle while (False in selected_nodes), en el que recorremos todos los nodos que aún no se han seleccionado.

Un MST para este propósito realmente no tiene un inicio o un final, aunque, algorítmicamente, ayudará tener un nodo de “inicio” y “fin”. El ‘inicio’ será simplemente el primer nodo seleccionado al azar, y el ‘final’ será el último nodo que agreguemos al MST. Estas variables actúan como los nodos a conectar y las vamos a utilizar para completar nuestra matriz MST:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def prims_mst(self):
    # Defining a really big number, that'll always be the highest weight in comparisons
    postitive_inf = float('inf')

    # This is a list showing which nodes are already selected 
    # so we don't pick the same node twice and we can actually know when stop looking
    selected_nodes = [False for node in range(self.m_num_of_nodes)]

    # Matrix of the resulting MST
    result = [[0 for column in range(self.m_num_of_nodes)] 
                for row in range(self.m_num_of_nodes)]
    
    indx = 0
    for i in range(self.m_num_of_nodes):
        print(self.m_graph[i])
    
    print(selected_nodes)

    # While there are nodes that are not included in the MST, keep looking:
    while(False in selected_nodes):
        # We use the big number we created before as the possible minimum weight
        minimum = postitive_inf

        # The starting node
        start = 0

        # The ending node
        end = 0

        for i in range(self.m_num_of_nodes):
            # If the node is part of the MST, look its relationships
            if selected_nodes[i]:
                for j in range(self.m_num_of_nodes):
                    # If the analyzed node have a path to the ending node AND its not included in the MST (to avoid cycles)
                    if (not selected_nodes[j] and self.m_graph[i][j]>0):  
                        # If the weight path analized is less than the minimum of the MST
                        if self.m_graph[i][j] < minimum:
                            # Defines the new minimum weight, the starting vertex and the ending vertex
                            minimum = self.m_graph[i][j]
                            start, end = i, j
        
        # Since we added the ending vertex to the MST, it's already selected:
        selected_nodes[end] = True

        # Filling the MST Adjacency Matrix fields:
        result[start][end] = minimum
        
        if minimum == postitive_inf:
            result[start][end] = 0

        print("(%d.) %d - %d: %d" % (indx, start, end, result[start][end]))
        indx += 1
        
        result[end][start] = result[start][end]

    # Print the resulting MST
    # for node1, node2, weight in result:
    for i in range(len(result)):
        for j in range(0+i, len(result)):
            if result[i][j] != 0:
                print("%d - %d: %d" % (i, j, result[i][j]))

Aquí, nos hemos movido a través de la matriz de adyacencia del gráfico inicial, usando dos bucles. El primer ciclo es para el eje X (filas) y el segundo ciclo es para el eje Y (columnas). Antes de ingresar al segundo bucle, debe validar que el nodo dado por el primer bucle esté seleccionado, lo que garantiza que sea parte del gráfico MST. Manejamos esto con el bloque if selected_nodes[i]: en el código anterior.

Cuando comienza a construir el árbol, ninguno de los nodos se selecciona inicialmente, todos son Falsos, por lo que el primer bucle terminaría incluso antes de que entremos en el segundo bucle. Por esta razón, start y end se establecen inicialmente en 0, y cuando salimos del bucle, el valor booleano asignado a la posición end se convertirá en True. Como resultado, un campo del resultado se llenará con el mínimo existente, y dado que el resultado es simétrico, podemos usar el mismo truco en self.m_graph para llenar otro campo.

Ahora que tenemos un nodo seleccionado, que es el Paso 1 del Algoritmo de Prim, ¡llegamos al Paso 2, dentro del segundo bucle! Primero, se desplaza por cada columna y examina las relaciones entre nuestro nodo seleccionado y otros nodos. Nuestro nodo seleccionado se comparará con los otros n nodos según los siguientes parámetros:

  • El vértice dado por i debe tener un camino que lo conecte con el vértice j (esto significa que el peso en la posición (i,j) de la matriz de adyacencia debe ser mayor que cero).
  • El vértice j no debe estar seleccionado (si ya está seleccionado esto puede dar lugar a un ciclo).

Dadas estas dos condiciones, puede comparar el peso del borde de una relación dada con el mínimo general del MST. Si el peso es inferior al mínimo, se convertirá en el nuevo mínimo y las variables start y end recibirán los valores i y j. Si el peso es superior al mínimo, sigue buscando en las columnas restantes.

El ‘inicio’ y el ‘fin’ llenarán la matriz MST, creando el árbol que estamos buscando. Después de eso, repite el proceso descrito hasta que seleccione todos los nodos del gráfico inicial.

Prueba del algoritmo de Prim en el gráfico de ejemplo

Para probar la implementación del algoritmo de Prim descrita anteriormente, creemos una instancia de Graph con 9 nodos:

1
2
# Example graph has 9 nodes
example_graph = Graph(9)

Luego, recreemos el gráfico de ejemplo que hemos estado usando anteriormente en las ilustraciones y la animación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
example_graph.add_edge(0, 1, 4)
example_graph.add_edge(0, 2, 7)
example_graph.add_edge(1, 2, 11)
example_graph.add_edge(1, 3, 9)
example_graph.add_edge(1, 5, 20)
example_graph.add_edge(2, 5, 1)
example_graph.add_edge(3, 6, 6)
example_graph.add_edge(3, 4, 2)
example_graph.add_edge(4, 6, 10)
example_graph.add_edge(4, 8, 15)
example_graph.add_edge(4, 7, 5)
example_graph.add_edge(4, 5, 1)
example_graph.add_edge(5, 7, 3)
example_graph.add_edge(6, 8, 5)
example_graph.add_edge(7, 8, 12)

Y, finalmente, ejecute el algoritmo:

1
example_graph.prims_mst()

Eso generará lo siguiente:

1
2
3
4
5
6
7
8
0 - 1: 4
0 - 2: 7
2 - 5: 1
3 - 4: 2
3 - 6: 6
4 - 5: 1
5 - 7: 3
6 - 8: 5

¡Y eso es! Ese es nuestro MST para ese gráfico, el mismo que en la sección sobre Intuición del algoritmo de Prim. Cada fila de la salida representa un borde del MST resultante en forma de nodo1 - nodo2: peso:

Recuerde que podemos comenzar con un nodo aleatorio, no necesariamente necesitamos comenzar con el primero. Si quiere desafiarse a sí mismo, puede modificar el código para que tome un número aleatorio (en el rango correcto, por supuesto) como el nodo inicial y observe cómo el algoritmo encuentra el mismo árbol en un orden diferente.

¿Cuál es la complejidad del algoritmo de Prim?

Si implementa el algoritmo de Prim usando solo una matriz de adyacencia, su complejidad temporal es O(N²), donde N es el número de nodos en un gráfico. La implementación simple produce una gran complejidad de tiempo en este caso.

Puede mejorar la complejidad del tiempo optando por una implementación más compleja, que consiste en Fibonacci o Binary Heap junto con la matriz de adyacencia. En ese caso, la complejidad del tiempo podría ser O(E log N), lo que significa que el algoritmo de Prim puede ejecutarse tan rápido como el de Kruskal y Borůvka.

{.icon aria-hidden=“true”}

Nota: E es el número de aristas en el gráfico inicial

Conclusión

El algoritmo de Prim no solo es eficiente sino también flexible cuando se trata de encontrar el árbol de expansión mínimo de un gráfico. La implementación de Python también es realmente simple. Los MST son estructuras útiles que se pueden aplicar en una amplia variedad de campos, lo que hace que el algoritmo de Prim sea increíblemente importante. te.

Licensed under CC BY-NC-SA 4.0