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

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

El algoritmo de Kruskal es uno de los tres algoritmos más famosos para encontrar un árbol de expansión mínimo (MST) en un gráfico.

El algoritmo de Kruskal es un algoritmo codicioso que encuentra una solución óptima global encontrando óptimos locales pequeños y combinándolos. Además de eso, sigue siendo bastante útil y ampliamente difundido.

En esta lección, ilustraremos y explicaremos cómo funciona el algoritmo de Kruskal en un ejemplo práctico, y luego le daremos su implementación detallada en Python.

Ya hemos cubierto muchos temas relacionados con gráficos en Python. Si está interesado en obtener más información sobre temas o algoritmos específicos, definitivamente debería leer algunos de ellos:

{.icon aria-hidden=“true”}

Nota: En esta lección, explicaremos solo los conceptos que son necesarios para comprender el algoritmo de Kruskal para encontrar el MST en un gráfico.
Todos los demás conceptos se explican en la lección "Teoría de grafos y algoritmos relacionados con grafos", así que definitivamente deberías leerlo de antemano.

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

En términos simples, un árbol de expansión mínimo es un árbol construido a partir de un gráfico no dirigido ponderado, por lo que:

  • Conecta todos los nodos (también conocidos como vértices)
  • No tiene ciclos
  • Tiene la suma más pequeña posible de pesos de borde

Examinemos esta definición informal para aclarar todos los conceptos erróneos posibles sobre las condiciones definidas.

El primer hecho importante es que puede construir MST solo en un gráfico ponderado, no dirigido. Eso significa que cada borde del gráfico tiene un peso numérico asignado y que puede atravesar cada borde desde ambas direcciones (a diferencia de los gráficos dirigidos).

MST conecta todos los nodos del gráfico, lo que significa que debe poder acceder a cualquier nodo desde todos los demás nodos del gráfico. Obviamente, puede excluir algunos bordes del gráfico. De hecho, excluir los bordes innecesarios del gráfico reduce la suma de todos los pesos de los bordes, lo que aumenta la posibilidad de que el árbol producido se convierta en el MST.

El MST debe tener la suma más pequeña posible de pesos de borde. A veces hay varios árboles con la misma suma de pesos de borde. Si esa suma es la menor posible, cualquiera de ellos puede ser el MST.

El último hecho casi se explica por sí mismo. Como probablemente sepa, los árboles son un tipo especial de gráfico. Son, en términos simples, gráficos conectados sin ciclos, y un MST es un tipo de árbol, lo que implica que no debe tener ningún ciclo.

{.icon aria-hidden=“true”}

Propiedad importante: Si un gráfico tiene n nodos, cada árbol de expansión (incluido MST) tiene n-1 bordes.

Explicación del algoritmo de Kruskal

Junto con Remilgado y Borůvka, el algoritmo de Kruskal es uno de los algoritmos más famosos para encontrar el árbol de expansión mínimo de gráficos ponderados no dirigidos. En esta lección, usaremos el mismo gráfico que en la lección que describe el algoritmo de Borůvka:

{.icon aria-hidden=“true”}

Nota: Solo en esta sección hemos marcado cada nodo con una letra en lugar de un número para una mejor legibilidad.

La idea detrás del algoritmo de Kruskal es bastante simple, básicamente hay dos pasos que repites hasta que obtienes el MST:

  1. clasifica todos los bordes por su peso en orden ascendente

  2. elige el borde con el peso más pequeño e intenta agregarlo al árbol

    • if it forms a cycle, skip that edge
  3. repita estos pasos hasta que tenga un árbol conectado que cubra todos los nodos

Para este gráfico en particular, la lista ordenada de todos los bordes se verá así:

Peso del borde


FE 1 FC 1 DE 2 FH 3 AB 4 EH 5 GI 5 GD 6 CA 7 BD 9 EG 10 11 aC hola 12 Nº 15 BF 20

Los bordes EF y CF tienen el mismo peso, por lo que puede elegir cualquiera de ellos como borde inicial. Asumiremos que eligió el EF. En este momento, el árbol que utilizará para construir el MST está vacío. Ahora, intenta agregar EF al árbol y verifica si forma un ciclo.

Como puede ver, agregar EF no formó ningún ciclo, por lo que puede mantenerlo en el árbol. Luego repite estos pasos para cada borde en la lista ordenada. Por supuesto, primero verifica el borde con el peso mínimo, y así sucesivamente.

La situación interesante ocurre cuando intenta agregar el EH al árbol:

Agregar EH al árbol creará un ciclo - EFH. Por lo tanto, debe excluir ‘EH’ del árbol y verificar si puede incluir el siguiente borde con el peso mínimo: ‘GI’. Después de agregar GI al árbol, se visitan todos los nodos:

Aunque visitó todos los nodos, el árbol aún no está conectado. Puede observar tres subárboles distintos: {A, B}, {C, D, E, F, H} y {G, I}. Esos subárboles forman un bosque de expansión mínima que cubre todos los nodos del gráfico inicial pero no es un MST. MST debe conectar todos los nodos del gráfico inicial, por lo que debe continuar agregando bordes hasta que el bosque se convierta en un árbol conectado. El algoritmo de Kruskal asegura que esos bordes agregados tengan el mínimo peso posible.

{.icon aria-hidden=“true”}

Nota: Esencialmente, puedes pensar en el algoritmo de Kruskal como un algoritmo que forma subárboles y los conecta con los bordes del mínimo peso posible. De esa manera, crea el MST.

Unos pasos más adelante en la línea, después de agregar los bordes ‘DG’ y ‘AC’ al bosque ilustrado en la ilustración anterior, ese bosque se convierte en un árbol conectado. De hecho, se convierte en el árbol de expansión mínimo del grafo inicial.

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

Cómo implementar el algoritmo de Kruskal en Python

En esta sección, usaremos el mismo gráfico que en la sección anterior. La única diferencia es que marcaremos cada nodo con un número (a partir de cero) en lugar de una letra para simplificar la implementación.

Implementando una clase Graph

Lo primero que debe implementar es una clase Graph. Representa un gráfico y define todos los métodos que puede necesitar al trabajar con gráficos.

1
2
3
4
5
6
7
class Graph:
    def __init__(self, num_of_nodes):
        self.m_num_of_nodes = num_of_nodes
        self.m_graph = []

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

Esta es una implementación bastante genérica de una clase Graph pero tendrá algunos ajustes para que sea compatible con el algoritmo de Kruskal. Presentaremos esos ajustes en las siguientes subsecciones.

Como probablemente ya sepas, __init__ es efectivamente un constructor de cualquier clase dada en Python. En este caso, construyes un gráfico llamando a Graph(num_of_nodes). Los únicos dos valores que se almacenan en una clase Graph son el número de nodos en el gráfico (m_num_of_nodes) y una matriz de bordes (m_graph). Esa matriz de bordes es la estructura de datos que usará para almacenar el gráfico en este ejemplo.

Cada borde de cualquier gráfico ponderado conecta exactamente dos nodos y tiene un cierto peso asignado. El método add_edge(node1, node2, weight) ilustra esa propiedad. Agrega el borde a un objeto Gráfico de la siguiente forma - [nodo1, nodo2, peso]. Esta es la forma más simple y efectiva de representar un gráfico en Python.

Además de constructor y addEgde(), hay un par de métodos más que deberá implementar. Para comprender cómo y por qué, primero explicaremos algunas áreas clave de la implementación para que tenga un conocimiento básico antes de presentar esos nuevos métodos. Vamos a empezar.

Matrices auxiliares - parent y subtree_sizes

Implementar el algoritmo de Kruskal en sí mismo debería ser algo bastante sencillo de hacer. Solo hay un par de puntos clave que debes tener en cuenta. En primer lugar, suponiendo que ya tiene una lista de aristas (representadas de la manera descrita anteriormente), debe ordenar desde el peso de arista más pequeño hasta el más grande.

Después de eso, debe iniciar y mantener dos matrices auxiliares: parent y subtree_sizes. La forma en que se construyen es de gran importancia, así que siga con cuidado. Ambos tienen el tamaño que corresponde al número de nodos en el gráfico inicial (es decir, si el gráfico inicial tiene n nodos, esas dos matrices tienen n elementos).

De esa forma, cada índice de esas matrices corresponde directamente a exactamente un nodo del gráfico. Por ejemplo, puede acceder a toda la información que pueda necesitar sobre el nodo 3 llamando a parents[3] y subtree_sizes[3].

Ahora que entiende cómo construir esos dos arreglos, expliquemos por qué los necesitamos. Como hemos dicho antes, el algoritmo de Kruskal crea efectivamente un conjunto de subárboles (o un bosque) y los conecta con los bordes del mínimo peso posible. Al principio, considera que cada nodo individual es un árbol separado y comienza a conectarlos. Conecta subárboles hasta obtener un árbol que conecta todos los nodos del gráfico inicial.

Ahí es donde entra en juego la matriz parent. Como ya sabe, los índices de esa matriz representan nodos (por ejemplo, el índice 3 se refiere al nodo 3 del gráfico). En la matriz principal, mantiene información sobre qué nodo pertenece a qué subárbol. Dado que al principio considera que cada nodo es un subárbol separado, la matriz principal tendrá el siguiente aspecto:

Como puede ver, cada nodo es el padre de sí mismo y el árbol resultante está vacío. Cuando elige el borde con el peso mínimo y lo agrega al árbol resultante, en realidad conecta dos de los subárboles iniciales.

En el gráfico de ejemplo, la arista con el peso mínimo es la que conecta los nodos 5 y 2, que son subárboles del gráfico inicial. Al conectarlos se forma un nuevo subárbol más grande que contiene los nodos 2 y 5. La matriz principal refleja eso al asignar el nodo 2 como el nodo principal del nodo 5.

Esto continúa hasta que tenga un solo árbol en lugar de varios subárboles más pequeños.

Para ayudarlo a mantener las matrices parent y subtree_sizes de una manera descrita, debe implementar los siguientes métodos en la clase Graph*:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# Finds the root node of a subtree containing node `i`
def find_subtree(self, parent, i):
    if parent[i] == i:
        return i
    return self.find_subtree(parent, parent[i])

# Connects subtrees containing nodes `x` and `y`
def connect_subtrees(self, parent, subtree_sizes, x, y):
    xroot = self.find_subtree(parent, x)
    yroot = self.find_subtree(parent, y)
    if subtree_sizes[xroot] < subtree_sizes[yroot]:
        parent[xroot] = yroot
    elif subtree_sizes[xroot] > subtree_sizes[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        subtree_sizes[xroot] += 1

El método find_subtree() busca recursivamente la matriz parent y encuentra un subárbol que contiene el nodo i.

El método connect_subtrees() conecta dos subárboles. Un subárbol contiene el nodo x y el otro contiene el nodo y. En primer lugar, encuentra esos dos subárboles, luego compara sus tamaños y conecta el subárbol más pequeño con uno más grande.

Ahora que hemos codificado y explicado la implementación de la clase Graph junto con todos los métodos adicionales, podemos echar un vistazo a cómo implementar el propio algoritmo de Kruskal.

Algoritmo MST de Kruskal

Con todos los demás métodos de una clase Graph explicados, la implementación del algoritmo de Kruskal debería ser bastante fácil de entender. Hemos optado por implementar el algoritmo como método en una clase Graph:

 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
def kruskals_mst(self):
    # Resulting tree
    result = []
    
    # Iterator
    i = 0
    # Number of edges in MST
    e = 0

    # Sort edges by their weight
    self.m_graph = sorted(self.m_graph, key=lambda item: item[2])
    
    # Auxiliary arrays
    parent = []
    subtree_sizes = []

    # Initialize `parent` and `subtree_sizes` arrays
    for node in range(self.m_num_of_nodes):
        parent.append(node)
        subtree_sizes.append(0)

    # Important property of MSTs
    # number of egdes in a MST is 
    # equal to (m_num_of_nodes - 1)
    while e < (self.m_num_of_nodes - 1):
        # Pick an edge with the minimal weight
        node1, node2, weight = self.m_graph[i]
        i = i + 1

        x = self.find_subtree(parent, node1)
        y = self.find_subtree(parent, node2)

        if x != y:
            e = e + 1
            result.append([node1, node2, weight])
            self.connect_subtrees(parent, subtree_sizes, x, y)
    
    # Print the resulting MST
    for node1, node2, weight in result:
        print("%d - %d: %d" % (node1, node2, weight))

El algoritmo en sí combina todos los métodos descritos anteriormente. En primer lugar, ordena una lista de bordes por su peso e inicializa las matrices parent y subtree_sizes. Luego itera sobre la lista ordenada de bordes, los selecciona uno por uno y los agrega al árbol resultante si es posible. El algoritmo se detiene cuando el número de aristas del árbol resultante es igual a (num_of_nodes - 1). El árbol resultante es el árbol de expansión mínimo que hemos estado tratando de construir.

Probemos este algoritmo en el gráfico de ejemplo utilizado anteriormente.

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

En primer lugar, debe crear el objeto Graph que representa su gráfico de ejemplo:

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

Luego agrega todos los nodos del gráfico de ejemplo al example_graph usando el método add_edge():

 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.kruskals_mst()

Eso producirá el siguiente resultado:

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

Como puede ver, esta salida describe el MST que es el mismo que se ilustra en la sección Explicación del algoritmo de Kruskal. Cada fila de la salida representa un borde de la siguiente manera: nodo1 - nodo2: peso. Puede ver el MST construido en la siguiente ilustración.

¿Cuál es la complejidad del algoritmo de Kruskal

Supongamos que tiene un gráfico con bordes E y nodos N. Encontrará el MST usando el algoritmo de Kruskal en el tiempo de O(E log E), que es equivalente a O(E log N).

Conclusión

El algoritmo de Kruskal es uno de los algoritmos más utilizados para encontrar un árbol de expansión mínimo en un gráfico junto con el algoritmo de Prim y Borůvka. Cada uno de ellos tiene prácticamente la misma complejidad, por lo que depende de usted decidir cuál usar.

En este artículo, hemos ilustrado el algoritmo de Kruskal en un ejemplo práctico y le brindamos una implementación real, para que pueda usarlo en sus proyectos y comprender cómo funciona. na.

Licensed under CC BY-NC-SA 4.0