Árvore Geradora Mínima - algoritmo de Kruskal

Dado um grafo não direcionado e com pesos. Queremos encontrar uma subárvore desse grafo na qual conecta todos os vértices (uma árvore geradora) com o menor peso (ou seja, a soma dos pesos de todas as arestas é mínima) de todas as árvores geradoras possíveis. A árvore geradora é chamada então de árvore geradora mínima.

Na imagem da esquerda, você pode ver um grafo não direcionado e com pesos, na imagem da direita, a árvore geradora mínima correspondente.

Random graph MST of this graph

Este artigo discutirá alguns fatos importantes associados às árvores geradoras mínimas(mst's) e, em seguida, fornecerá a implementação mais simples do algoritmo de Kruskal para encontrar a árvore geradora mínima.

Propriedades

Algoritmo de Kruskal

Este algoritmo foi descrito por Joseph Bernard Kruskal, Jr. em 1956.

O algoritmo de Kruskal inicialmente isola todos os nós do grafo uns dos outros, para formar uma floresta de árvores de nós individuais, e então gradualmente mesclar essas árvores, combinando em cada iteração qualquer duas árvores com alguma aresta do grafo original. Antes da execução do algoritmo, todas as arestas são ordenadas pelos pesos (ordem decrescente). Em seguida, começa o processo de unificação: pegando todas as arestas da primeira até a última (ordenadas), e se as extremidades das aresta atuais pertencerem a subárvores diferentes, essas subárvores são combinadas, e a aresta é adicionada à resposta. Depois de iterar sobre todas as arestas, todos os vértices pertencerão à mesma subárvore e obteremos a resposta.

Implementação

O código a seguir implementa diretamente o algoritmo descrito acima e tem complexidade de tempo $O(M \log M + N^2)$. Ordenar arestas requer $O(M \log N)$ (o mesmo que $O(M \log M)$) operações. As informações sobre a subárvore à qual um vértice pertence são mantidas com a ajuda de uma array tree_id[] - para cada vértice v, tree_id[v] armazena o número da árvore à qual v pertence. Para cada aresta, se ela pertence às extremidades de diferentes árvores, pode ser determinada em $O(1)$. Finalmente, a união das duas árvores é realizada em $O(N)$ por uma simples passagem pela array tree_id[]. Dado que o número total de operações de mesclagem é $N-1$, obtemos o comportamento assintó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;
        }
    }
}

Prova

Por que o algoritmo de Kruskal nos fornece o resultado correto?

Se o grafo original era conexo, o grafo resultante também será conexo/conectado. Porque, caso contrário, haveria dois componentes que poderiam ser conexos com pelo menos uma aresta. No entanto, isso seria impossível pois Kruskal teria escolhido uma dessas arestas e os índices(ids) dos componentes são diferentes. Além disso, o grafo resultante não contém ciclos, pois proibimos isso explicitamente no algoritmo. Portanto, o algoritmo gera uma árvore geradora.

Então, por que esse algoritmo nos fornece uma árvore geradora mínima?

Podemos mostrar a proposta: "se $F$ é um conjunto de arestas escolhido pelo algoritmo em qualquer estágio do algoritmo, existe uma MST que contém todas as arestas de $F$" usando indução.

A proposta é verdadeira no início, o conjunto vazio é um subconjunto de qualquer MST.

Agora, vamos supor que $F$ é um algum conjunto de arestas definida em qualquer estágio do algoritmo, $T$ é uma MST contendo $F$ e $e$ é a nova aresta que queremos adicionar usando Kruskal.

Se $e$ gera um ciclo, não o adicionamos e, portanto, a proposta ainda é verdadeira após esta etapa.

No caso em que $T$ já contenha $e$, a proposta também será verdadeira após esta etapa.

No caso em que $T$ não contenha a aresta $e$, então $T + e$ conterá um ciclo $C$. Esse ciclo conterá pelo menos uma aresta $f$, que não está emn $F$. O conjunto de arestas $T - f + e$ também será uma árvore geradora. Observe que o peso de $f$ não pode ser menor que o peso de $e$, porque, caso contrário, Kruskal teria escolhido $f$ anteriormente. Ele também não pode ter um peso maior, pois isso tornaria o peso total de $T - f + e$ menor que o peso total de $T$, o que é impossível, já que $T$ já é um MST. Isso significa que o peso de $e$ deve ser igual ao peso de $f$. Portanto, $T - f + e$ também é uma MST, e contém todas as arestas de $F + e$. Então, após a etapa, a proposta ainda é cumprida.

Isso prova a proposta. O que significa que, após iterar em todas as arestas, o conjunto de arestas resultante será conectado e estará contido em uma MST, o que significa que ele já deve ser uma MST.

Implementação aprimorada

Podemos usar a estrutura de dados Disjoint Set Union (DSU) para escrever uma implementação mais rápida do algoritmo de Kruskal com a complexidade do tempo em cerca de $O(M \log N)$.

Problemas