Árbol de expansión mínima - algoritmo de Kruskal

Se da un grafo no dirigido ponderado. Queremos encontrar un subárbol de este grafo que conecte todos los vértices (es decir, que sea un árbol de expansión) y que tenga el menor peso (es decir, que la suma de los pesos de todas las aristas sea mínima) entre todos los árboles de expansión posibles. Este árbol de expansión se llama árbol de expansión mínima (MST).

En la imagen de la izquierda se ve un grafo no dirigido ponderado, y en la de la derecha el árbol de expansión mínima (MST) correspondiente.

Grafo aleatorio MST de este grafo

Este artículo trata algunos hechos importantes asociados a los árboles de expansión mínima, y después da la implementación más simple del algoritmo de Kruskal para encontrar un árbol de expansión mínima.

Propiedades del árbol de expansión mínima

Un árbol de expansión mínima de un grafo es único si los pesos de todas las aristas son distintos. En caso contrario, puede haber varios árboles de expansión mínima. (Los algoritmos concretos suelen emitir uno de los árboles de expansión mínima posibles).
El árbol de expansión mínima es también el árbol con producto mínimo de los pesos de las aristas. (Se puede demostrar fácilmente reemplazando los pesos de todas las aristas por sus logaritmos)
En un árbol de expansión mínima de un grafo, el peso máximo de una arista es el mínimo posible entre todos los árboles de expansión posibles de ese grafo. (Esto se sigue de la validez del algoritmo de Kruskal).
El árbol de expansión máxima (árbol de expansión con suma de pesos de aristas máxima) de un grafo se puede obtener de forma similar al árbol de expansión mínima, cambiando los signos de los pesos de todas las aristas por su opuesto y aplicando después cualquiera de los algoritmos de árbol de expansión mínima.

Algoritmo de Kruskal

Este algoritmo fue descrito por Joseph Bernard Kruskal, Jr. en 1956.

El algoritmo de Kruskal coloca inicialmente todos los nodos del grafo original aislados entre sí, formando un bosque de árboles de un solo nodo, y después fusiona gradualmente estos árboles, combinando en cada iteración dos cualesquiera de todos los árboles mediante alguna arista del grafo original. Antes de la ejecución del algoritmo, se ordenan todas las aristas por peso (en orden no decreciente). Luego comienza el proceso de unificación: se toman todas las aristas de la primera a la última (en ese orden) y, si los extremos de la arista actualmente elegida pertenecen a subárboles distintos, estos subárboles se combinan y la arista se agrega a la respuesta. Tras iterar sobre todas las aristas, todos los vértices pertenecerán al mismo subárbol, y obtendremos la respuesta.

La implementación más simple

El siguiente código implementa de forma directa el algoritmo descrito arriba, y tiene complejidad temporal $O(M \log M + N^2)$ . Ordenar las aristas requiere $O(M \log N)$ (que es lo mismo que $O(M \log M)$ ) operaciones. La información sobre el subárbol al que pertenece un vértice se mantiene con ayuda de un arreglo tree_id[]: para cada vértice v, tree_id[v] almacena el número del árbol al que pertenece v. Para cada arista, se puede determinar en $O(1)$ si sus extremos pertenecen a árboles distintos. Por último, la unión de los dos árboles se realiza en $O(N)$ con un simple recorrido del arreglo tree_id[]. Dado que el número total de operaciones de fusión es $N-1$ , obtenemos el comportamiento asintótico $O(M \log N + N^2)$ .


struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};
 
int n;
vector<Edge> edges;
 
int cost = 0;
vector<int> tree_id(n);
vector<Edge> result;
for (int i = 0; i < n; i++)
    tree_id[i] = i;
 
sort(edges.begin(), edges.end());
   
for (Edge e : edges) {
    if (tree_id[e.u] != tree_id[e.v]) {
        cost += e.weight;
        result.push_back(e);
 
        int old_id = tree_id[e.u], new_id = tree_id[e.v];
        for (int i = 0; i < n; i++) {
            if (tree_id[i] == old_id)
                tree_id[i] = new_id;
        }
    }
}

Demostración de corrección

¿Por qué el algoritmo de Kruskal nos da el resultado correcto?

Si el grafo original era conexo, entonces el grafo resultante también será conexo. Porque, de lo contrario, habría dos componentes que se podrían conectar con al menos una arista. Sin embargo esto es imposible, porque Kruskal habría elegido una de estas aristas, ya que los ids de las componentes son distintos. Además el grafo resultante no contiene ciclos, porque lo prohibimos explícitamente en el algoritmo. Por lo tanto el algoritmo genera un árbol de expansión.

¿Y por qué este algoritmo nos da un árbol de expansión mínima?

Podemos mostrar la afirmación “si $F$ es un conjunto de aristas elegidas por el algoritmo en cualquier etapa del algoritmo, entonces existe un MST que contiene todas las aristas de $F$ ” usando inducción.

La afirmación es obviamente cierta al comienzo: el conjunto vacío es un subconjunto de cualquier MST.

Ahora supongamos que $F$ es algún conjunto de aristas en cualquier etapa del algoritmo, $T$ es un MST que contiene a $F$ y $e$ es la nueva arista que queremos agregar usando Kruskal.

Si $e$ genera un ciclo, entonces no la agregamos, y así la afirmación sigue siendo cierta después de este paso.

En caso de que $T$ ya contenga a $e$ , la afirmación también es cierta después de este paso.

En caso de que $T$ no contenga la arista $e$ , entonces $T + e$ contendrá un ciclo $C$ . Este ciclo contendrá al menos una arista $f$ que no está en $F$ . El conjunto de aristas $T - f + e$ también será un árbol de expansión. Nótese que el peso de $f$ no puede ser menor que el peso de $e$ , porque de lo contrario Kruskal habría elegido $f$ antes. Tampoco puede tener un peso mayor, ya que eso haría que el peso total de $T - f + e$ fuera menor que el peso total de $T$ , lo cual es imposible porque $T$ ya es un MST. Esto significa que el peso de $e$ tiene que ser el mismo que el peso de $f$ . Por lo tanto $T - f + e$ también es un MST, y contiene todas las aristas de $F + e$ . Así que también aquí la afirmación sigue cumpliéndose después del paso.

Esto demuestra la afirmación. Lo que significa que, tras iterar sobre todas las aristas, el conjunto de aristas resultante será conexo y estará contenido en un MST, lo que significa que ya tiene que ser un MST.

Implementación mejorada

Podemos usar la estructura de datos conjuntos disjuntos (Disjoint Set Union, DSU) para escribir una implementación más rápida del algoritmo de Kruskal con complejidad temporal de alrededor de $O(M \log N)$ . Este artículo detalla ese enfoque.