Árvore Geradora Mínima: Kruskal com Disjoint Set Union

Para uma explicação do problema do MST e do algoritmo de Kruskal, consulte primeiro o artigo sobre o algoritmo de Kruskal.

Neste artigo, consideraremos a estrutura de dados "Disjoint Set Union" para implementar o algoritmo de Kruskal, o que permitirá que o algoritmo atinja a complexidade de tempo $O(M \log N)$.

Descrição

Assim como na versão simples do algoritmo de Kruskal, ordenamos todas as arestas do grafo em ordem não decrescente de pesos. Em seguida, cada vértice é colocado em sua própria árvore (ou seja, seu conjunto) por meio de chamadas da função make_set - serão necessários um total de $O(N)$. e para cada aresta determinamos se as extremidades pertencem a árvores diferentes (com duas chamadas find_set com $O(1)$ cada). Finalmente, precisamos realizar a união das duas árvores (sets), na qual a função do DSU union_sets será chamada - também em $O(1)$. Portanto, obtemos a complexidade do tempo total de $O(M \log N + N + M)$ = $O(M \log N)$.

Implementação

Aqui está uma implementação do algoritmo de Kruskal com "union by rank".

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);
    }
}

Nota: como a MST conterá exatamente $N-1$ arestas, podemos interromper o loop "for" quando encontrarmos essa quantidade.