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

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...

Algoritmo de Borůvka es un algoritmo codicioso publicado por Otakar Borůvka, un matemático checo mejor conocido por su trabajo en teoría de grafos. Su aplicación más famosa nos ayuda a encontrar el árbol de expansión mínimo en un gráfico.

Una cosa que vale la pena señalar acerca de este algoritmo es que es el algoritmo de árbol de expansión mínimo más antiguo registrado. A Borůvka se le ocurrió en 1926, antes de que existieran las computadoras tal como las conocemos hoy. Fue publicado como un método para construir una red eléctrica eficiente.

En esta lección, repasaremos los gráficos y qué son los árboles de expansión mínimos, y luego saltaremos al algoritmo de Borůvka y lo implementaremos en Python.

Gráficos y árboles de expansión mínimos

Un grafo es una estructura abstracta que representa un grupo de ciertos objetos llamados nodos (también conocidos como vértices), en los cuales ciertos pares de esos nodos están conectados o relacionados. Cada una de estas conexiones se denomina borde.

Un árbol es un ejemplo de un gráfico:

Ejemplo básico de gráfico

En la imagen de arriba, el primer gráfico tiene 4 nodos y 4 aristas, mientras que el segundo gráfico (un árbol binario) tiene 7 nodos y 6 aristas.

Los gráficos se pueden aplicar a muchos problemas, desde ubicaciones geoespaciales hasta gráficos de redes sociales y redes neuronales. Conceptualmente, gráficos como estos están a nuestro alrededor. Por ejemplo, supongamos que nos gustaría trazar un árbol genealógico o explicarle a alguien cómo conocimos a nuestra pareja. Podríamos presentar una gran cantidad de personas y sus relaciones para que la historia sea tan interesante para el oyente como lo fue para nosotros.

Dado que esto es realmente solo un gráfico de personas (nodos) y sus relaciones (bordes), los gráficos son una excelente manera de visualizar esto:

visualizando relaciones con grafos

Tipos de gráficos

Dependiendo de los tipos de bordes que tenga un gráfico, tenemos dos categorías distintas de gráficos:

  • Gráficos no dirigidos
  • Gráficos dirigidos

Un gráfico no dirigido es un gráfico en el que los bordes no tienen orientaciones. Todos los bordes de un gráfico no dirigido se consideran, por lo tanto, bidireccionales.

Formalmente, podemos definir un gráfico no dirigido como G = (V, E) donde V es el conjunto de todos los nodos del gráfico, y E es un conjunto que contiene pares de elementos desordenados de E, que representan los bordes.

Los pares no ordenados aquí significan que la relación entre dos nodos siempre es de dos lados, por lo que si sabemos que hay un borde que va de A a B, sabemos con seguridad que hay un borde que va de ‘B’ a ‘A’.

Un gráfico dirigido es un gráfico en el que los bordes tienen orientaciones.

Formalmente, podemos definir un gráfico dirigido como G = (V, E) donde V es el conjunto de todos los nodos del gráfico, y E es un conjunto que contiene pares ordenados de elementos de MI.

Los pares ordenados implican que la relación entre dos nodos puede ser de uno o dos lados. Lo que significa que si hay un borde que va de A a B, no podemos saber si hay un borde que va de B a A.

La dirección de un borde se indica con una flecha. Tenga en cuenta que las relaciones de dos lados se pueden mostrar dibujando dos flechas distintas o simplemente dibujando dos puntas de flecha a cada lado del mismo borde:

gráficos dirigidos y no dirigidos

Otra forma de diferenciar gráficos en función de sus bordes es con respecto al peso de esos bordes. En base a eso, un gráfico puede ser:

  • Ponderado
  • Sin ponderar

Un gráfico ponderado es un gráfico en el que a cada borde se le asigna un número: su peso. Estos pesos pueden representar la distancia entre nodos, capacidad, precio, etcétera, dependiendo del problema que estemos resolviendo.

Los gráficos ponderados se utilizan con bastante frecuencia, por ejemplo, en problemas en los que necesitamos encontrar el más corto o, como veremos pronto, en problemas en los que tenemos que encontrar un árbol de expansión mínimo.

Un gráfico no ponderado no tiene pesos en sus bordes.

{.icon aria-hidden=“true”}

Nota: En este artículo, nos centraremos en gráficos ponderados no dirigidos.

Un gráfico también puede estar conectado y desconectado. Un grafo es conexo si hay un camino (que consiste en uno o más bordes) entre cada par de nodos. Por otro lado, un gráfico está desconectado si hay un par de nodos que no pueden estar conectados por un camino de aristas.

gráficos conectados y desconectados

Árboles y árboles de expansión mínimos

Hay bastante que decir sobre árboles, subgrafos y árboles de expansión, aunque aquí hay un desglose muy rápido y conciso:

  • Un árbol es un gráfico no dirigido donde cada dos nodos tienen exactamente un camino que los conecta, ni más ni menos.

  • Un subgrafo de un grafo A es un grafo que esta comprometido de un subconjunto de los nodos y bordes del grafo A.

  • Un árbol de expansión del gráfico A es un subgráfico del gráfico A que es un árbol, cuyo conjunto de nodos es el mismo que el del gráfico A.

  • Un árbol de expansión mínimo es un árbol de expansión, tal que la suma de todos los pesos de las aristas es la menor posible. Dado que es un árbol (y la suma del peso del borde debe ser mínima), no debería haber ningún ciclo.

Nota: En caso de que todos los pesos de borde en un gráfico sean distintos, el árbol de expansión mínimo de ese gráfico será único. Sin embargo, si los pesos de los bordes no son distintos, puede haber varios árboles de expansión mínimos para un solo gráfico.

Ahora que estamos cubiertos en términos de teoría de grafos, podemos abordar el algoritmo en sí.

Algoritmo de Blueberry

La idea detrás de este algoritmo es bastante simple e intuitiva. Mencionamos antes que este era un algoritmo codicioso.

Cuando un algoritmo es codicioso, construye una solución "óptima" global utilizando soluciones más pequeñas y localmente óptimas para subproblemas más pequeños. Por lo general, converge con una solución suficientemente buena, ya que seguir los óptimos locales no garantiza una solución óptima global.

En pocas palabras, los algoritmos codiciosos hacen la elección óptima (entre las opciones actualmente conocidas) en cada paso del problema, con el objetivo de llegar a la solución general más óptima cuando se suman todos los pasos más pequeños.

Podrías pensar en los algoritmos codiciosos como un músico que está improvisando en un concierto y en todo momento tocará lo que suene mejor. Por otro lado, los algoritmos no codiciosos se parecen más a un compositor, que pensará en la pieza que está a punto de interpretar y se tomará su tiempo para escribirla como partitura.

Ahora, desglosaremos el algoritmo en un par de pasos:

  1. Inicializamos todos los nodos como componentes individuales.
  2. Inicializamos el árbol de expansión mínimo S como un conjunto vacío que contendrá la solución.
  3. Si hay más de un componente:
    • Find the minimum-weight edge that connects this component to any other component.
    • If this edge isn't in the minimum spanning tree S, we add it.
  4. Si solo queda un componente, hemos llegado al final del árbol.

Este algoritmo toma un gráfico conectado, ponderado y no dirigido como entrada, y su salida es el árbol de expansión mínimo correspondiente del gráfico.

Echemos un vistazo al siguiente gráfico y encontremos su árbol de expansión mínimo usando el algoritmo de Borůvka:

minimum spanning tree graph

Al principio, cada representa un componente individual. Eso significa que tendremos 9 componentes. Veamos cuáles serían los bordes de menor peso que conectan estos componentes con cualquier otro componente:

Componente Borde de menor peso que lo conecta con algún otro componente Peso del borde


{0} 0 - 1 4 {1} 0 - 1 4 {2} 2 - 4 2 {3} 3 - 5 5 {4} 4 - 7 1 {5} 3 - 5 10 {6} 6 - 7 1 {7} 4 - 7 1 {8} 7 - 8 3

Ahora, nuestro gráfico va a estar en este estado:

applying boruvka for minimum spanning tree

Los bordes verdes en este gráfico representan los bordes que unen sus componentes más cercanos. Como podemos ver, ahora tenemos tres componentes: {0, 1}, {2, 4, 6, 7, 8} y {3, 5}. Repetimos el algoritmo e intentamos encontrar los bordes de peso mínimo que pueden unir estos componentes:

Componente Borde de menor peso que lo conecta con algún otro componente Peso del borde


{0, 1} 0 - 6 7 {2, 4, 6, 7, 8} 2 - 3 6 {3, 5} 2 - 3 6

Ahora, nuestro gráfico va a estar en este estado:

boruvka\'s algorithm mst

Como podemos ver, nos quedamos con un solo componente en este gráfico, que representa nuestro árbol de expansión mínimo. El peso de este árbol es 29, que obtuvimos después de sumar todas las aristas:

boruvka algorithm mst

Ahora, lo único que queda por hacer es implementar este algoritmo en Python.

Implementación

Vamos a implementar una clase Graph, que será la estructura de datos principal con la que trabajaremos. Comencemos con el constructor:

1
2
3
4
5
class Graph:
    def __init__(self, num_of_nodes):
        self.m_v = num_of_nodes
        self.m_edges = []
        self.m_component = {}

En este constructor, proporcionamos el número de nodos en el gráfico como argumento e inicializamos tres campos:

  • m_v - el número de nodos en el gráfico.
  • m_edges - la lista de bordes.
  • m_component - el diccionario que almacena el índice del componente al que pertenece un nodo.

Ahora, hagamos una función auxiliar que podamos usar para agregar un borde a los nodos de un gráfico:

1
2
    def add_edge(self, u, v, weight):
        self.m_edges.append([u, v, weight])

Esta función agregará un borde en el formato [primero, segundo, peso del borde] a nuestro gráfico.

Debido a que finalmente queremos crear un método que unifique dos componentes, primero necesitaremos un método que propague un nuevo componente a través de un componente dado. Y en segundo lugar, necesitaremos un método que encuentre el índice de componente de un nodo dado:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def find_component(self, u):
        if self.m_component[u] == u:
            return u
        return self.find_component(self.m_component[u])

    def set_component(self, u):
        if self.m_component[u] == u:
            return
        else:
            for k in self.m_component.keys():
                self.m_component[k] = self.find_component(k)

En este método, trataremos artificialmente el diccionario como un árbol. Preguntamos si hemos encontrado o no la raíz de nuestro componente (porque solo los componentes raíz siempre apuntarán a sí mismos en el diccionario m_component). Si no hemos encontrado el nodo raíz, buscamos recursivamente el padre del nodo actual.

Nota: La razón por la que no asumimos que m_components apunta al componente correcto es porque cuando comenzamos a unificar componentes, lo único que sabemos con certeza que no cambiará su índice de componente es la raíz componentes

Por ejemplo, en nuestro gráfico en el ejemplo anterior, en la primera iteración, el diccionario se verá así:

valor de índice


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

Tenemos 9 componentes, y cada miembro es el componente por sí mismo. En la segunda iteración, se verá así:

valor de índice


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

Ahora, volviendo a las raíces, veremos que nuestros nuevos componentes serán: {0, 1}, {2, 4, 7, 6, 8} y {3, 5}.

El último método que vamos a necesitar antes de implementar el algoritmo en sí es el método que unifica dos componentes en uno, dados dos nodos que pertenecen a sus respectivos componentes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def union(self, component_size, u, v):
        if component_size[u] <= component_size[v]:
            self.m_component[u] = v
            component_size[v] += component_size[u]
            self.set_component(u)

        elif component_size[u] >= component_size[v]:
            self.m_component[v] = self.find_component(u)
            component_size[u] += component_size[v]
            self.set_component(v)

        print(self.m_component)

En esta función, encontramos las raíces de los componentes de dos nodos (que son sus índices de componentes al mismo tiempo). Luego, comparamos los componentes en términos de tamaño y unimos el más pequeño al más grande. Luego, solo agregamos el tamaño del más pequeño al tamaño del más grande, porque ahora son un componente.

Finalmente, si los componentes son del mismo tamaño, simplemente los unimos como queramos; en este ejemplo en particular, lo hicimos agregando el segundo al primero.

Ahora que hemos implementado todos los métodos de utilidad que necesitamos, finalmente podemos sumergirnos en el algoritmo de Borůvka:

 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
    def boruvka(self):
        component_size = []
        mst_weight = 0

        minimum_weight_edge = [-1] * self.m_v

        for node in range(self.m_v):
            self.m_component.update({node: node})
            component_size.append(1)

        num_of_components = self.m_v

        print("---------Forming MST------------")
        while num_of_components > 1:
            for i in range(len(self.m_edges)):

                u = self.m_edges[i][0]
                v = self.m_edges[i][1]
                w = self.m_edges[i][2]

                u_component = self.m_component[u]
                v_component = self.m_component[v]

                if u_component != v_component:
                    if minimum_weight_edge[u_component] == -1 or \
                            minimum_weight_edge[u_component][2] > w:
                        minimum_weight_edge[u_component] = [u, v, w]
                    if minimum_weight_edge[v_component] == -1 or \
                            minimum_weight_edge[v_component][2] > w:
                        minimum_weight_edge[v_component] = [u, v, w]

            for node in range(self.m_v):
                if minimum_weight_edge[node] != -1:
                    u = minimum_weight_edge[node][0]
                    v = minimum_weight_edge[node][1]
                    w = minimum_weight_edge[node][2]

                    u_component = self.m_component[u]
                    v_component = self.m_component[v]

                    if u_component != v_component:
                        mst_weight += w
                        self.union(component_size, u_component, v_component)
                        print("Added edge [" + str(u) + " - "
                              + str(v) + "]\n"
                              + "Added weight: " + str(w) + "\n")
                        num_of_components -= 1

            minimum_weight_edge = [-1] * self.m_v
        print("----------------------------------")
        print("The total weight of the minimal spanning tree is: " + str(mst_weight))

Lo primero que hicimos en este algoritmo fue inicializar listas adicionales que necesitaríamos en el algoritmo:

  • Una lista de componentes (inicializados en todos los nodos).
  • Una lista que mantiene su tamaño (inicializado a 1), así como la lista de los bordes de peso mínimo (-1 al principio, ya que aún no sabemos cuáles son los bordes de peso mínimo).

Luego, recorremos todos los bordes del gráfico y encontramos la raíz de los componentes en ambos lados de esos bordes.

Después de eso, buscamos el borde de peso mínimo que conecta estos dos componentes usando un par de cláusulas if:

  • Si el borde de peso mínimo actual del componente u no existe (es -1), o si es mayor que el borde que estamos observando en este momento, asignaremos el valor del borde que estamos observando.
  • Si el borde de peso mínimo actual del componente v no existe (es -1), o si es mayor que el borde que estamos observando en este momento, asignaremos el valor del borde que estamos observando.

Después de encontrar los bordes más baratos para cada componente, los agregamos al árbol de expansión mínimo y disminuimos la cantidad de componentes en consecuencia.

Finalmente, restablecemos la lista de bordes de peso mínimo a -1, para que podamos hacer todo esto nuevamente. Seguimos iterando mientras haya más de un componente en la lista de componentes.

Pongamos el gráfico que usamos en el ejemplo anterior como la entrada de nuestro algoritmo implementado:

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

Tirarlo en la implementación del algoritmo dará como resultado:

 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
---------Forming MST------------
{0: 1, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge [0 - 1]
Added weight: 4

{0: 1, 1: 1, 2: 4, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge [2 - 4]
Added weight: 2

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge [3 - 5]
Added weight: 5

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 4, 8: 8}
Added edge [4 - 7]
Added weight: 1

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 8}
Added edge [6 - 7]
Added weight: 1

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4}
Added edge [7 - 8]
Added weight: 3

{0: 4, 1: 4, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4}
Added edge [0 - 6]
Added weight: 7

{0: 4, 1: 4, 2: 4, 3: 4, 4: 4, 5: 4, 6: 4, 7: 4, 8: 4}
Added edge [2 - 3]
Added weight: 6

----------------------------------
The total weight of the minimal spanning tree is: 29

La complejidad de tiempo de este algoritmo es O(ElogV), donde E representa el número de aristas, mientras que V representa el número de nodos.

La complejidad espacial de este algoritmo es O(V + E), ya que tenemos que mantener un par de listas cuyos tamaños sean iguales al número de nodos, así como mantener todos los bordes de un gráfico dentro del estructura de datos en sí.

Conclusión

Aunque el algoritmo de Borůvka no es tan conocido como otros algoritmos de árbol de expansión mínimo como los algoritmos de árbol de expansión mínimo de Prim o Kruskal, nos da prácticamente el mismo resultado: todos encuentran el árbol de expansión mínimo , y la complejidad del tiempo es aproximadamente la misma.

Una ventaja que tiene el algoritmo de Borůvka en comparación con las alternativas es que no necesita ordenar previamente los bordes o mantener una cola de prioridad para encontrar el árbol de expansión mínimo. Aunque eso no ayuda a su complejidad, ya que aún pasa los bordes logE veces, es un poco más simple de codificar.

Licensed under CC BY-NC-SA 4.0