Árbol de expansión mínima (MST) - Kruskal con Union-Find / conjuntos disjuntos (DSU)

Para una explicación del problema del MST y del algoritmo de Kruskal, ver primero el artículo principal sobre el algoritmo de Kruskal.

En este artículo consideraremos la estructura de datos “Union-Find / conjuntos disjuntos (DSU)” para implementar el algoritmo de Kruskal, lo que permitirá que el algoritmo alcance la complejidad temporal de $O(M \log N)$.

Descripción

Igual que en la versión simple del algoritmo de Kruskal, ordenamos todas las aristas del grafo en orden no decreciente de pesos. Luego ponemos cada vértice en su propio árbol (es decir, su conjunto) mediante llamadas a la función make_set; esto tomará un total de $O(N)$. Iteramos por todas las aristas (en orden) y para cada arista determinamos si los extremos pertenecen a árboles distintos (con dos llamadas a find_set en $O(1)$ cada una). Por último, hay que realizar la unión de los dos árboles (conjuntos), para lo cual se llamará a la función union_sets del DSU, también en $O(1)$. Así obtenemos la complejidad temporal total de $O(M \log N + N + M)$ = $O(M \log N)$.

Implementación

Aquí hay una implementación del algoritmo de Kruskal con unión por rango.

vector<int> parent, rank;
 
void make_set(int v) {
    parent[v] = v;
    rank[v] = 0;
}
 
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
 
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
    }
}
 
struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};
 
int n;
vector<Edge> edges;
 
int cost = 0;
vector<Edge> result;
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++)
    make_set(i);
 
sort(edges.begin(), edges.end());
 
for (Edge e : edges) {
    if (find_set(e.u) != find_set(e.v)) {
        cost += e.weight;
        result.push_back(e);
        union_sets(e.u, e.v);
    }
}

Nótese: como el MST contendrá exactamente $N-1$ aristas, podemos detener el bucle for en cuanto hayamos encontrado esa cantidad.

Problemas de práctica

Ver el artículo principal sobre el algoritmo de Kruskal para la lista de problemas de práctica sobre este tema.