Aula por Lucca Siaudzionis
“O cientista Succa Liaudzionis foi contratado para pavimentar algumas estradas de um reino. Cada estrada possui um determinado custo para ser pavimentada. Devido a péssima administração estatal, Succa está com pouco dinheiro disponível para poder pavimentar as cidades. Sabendo disso, ele decidiu pavimentar apenas o necessário para que todas as cidades do reino estejam conectadas de maneira direta ou indireta. Sabendo de seus conhecimentos de programação, Succa pediu a sua ajuda para resolver o problema”
Primeiramente, note que se Succa for selecionar um número mínimo de arestas, o grafo resultante será uma árvore (pois qualquer aresta acrescentada posteriormente ligaria dois vértices já conectados). O problema então é um problema clássico: dado um grafo, achar sua árvore geradora mínima.
Olhe o seguinte grafo:
Ele possui $$6$$ vértices, se quisermos selecionar o número mínimo de arestas para deixar o grafo restante conexo, selecionamos $$6 – 1 = 5$$ arestas. Há várias maneiras de fazer isso, duas delas são:
 |
 |
Vemos que as duas usam o mesmo número de arestas, mas a soma dos pesos das arestas da árvore da direita é consideravelmente menor. A árvore da direita é uma árvore geradora mínima. Podem existir várias árvores mínimas para um grafo, mas, obviamente, a soma do peso de suas arestas será igual.
Há dois algoritmos muito conhecidos para resolver este tipo de problema: Algoritmo de Kruskal e Algoritmo de Prim. Vamos aqui abordar o algoritmo de Kruskal.
Primeiramente, vamos tentar ver como construir uma árvore geradora (não necessariamente mínima). Um método simples de se pensar (e ver o porquê de funcionar) é este, que considera a árvore sendo construída aos poucos:
- Liste todas as arestas em qualquer ordem.
- Cada aresta liga dois vértices $$x$$ e $$y$$, checar se eles já estão na mesma componente conexa (aqui, consideramos apenas as arestas já colocadas na árvore).
- Se $$x$$ e $$y$$ estão na mesma componente, ignoramos a aresta e continuamos o procedimento (se a usássemos, formaríamos um ciclo). Se estiverem em componentes distintas, colocamos a aresta na árvore e continuamos o procedimento.
A única diferença deste algoritmo (que gera uma árvore qualquer) para o algoritmo de Kruskal é o primeiro passo. No algoritmo de Kruskal, as arestas são listadas em ordem crescente de tamanho, fazendo, assim, um algoritmo guloso para montar a árvore geradora mínima.
Vamos simular o algoritmo de Kruskal para o mesmo grafo acima (agora com os vértices enumerados):
As arestas, listadas por ordem crescente de tamanho, são:
$$!(1, \ 5), \ (1, \ 2), \ (2, \ 3), \ (3, \ 5), \ (4, \ 5), \ (5, \ 6), \ (1, \ 6), \ (2, \ 5), \ (3, \ 4)$$
Vamos, então, simular o procedimento.
 |
Primeiro, selecionamos a menor aresta. Como os vértices $$1$$ e $$5$$ ainda não estão conectados, podemos usar esta aresta. |
 |
Agora, selecionamos a aresta seguinte. Como os vértices $$1$$ e $$2$$ ainda não estão conectados, podemos usar esta aresta.
|
 |
Agora, selecionamos a aresta seguinte. Como os vértices $$2$$ e $$3$$ ainda não estão conectados, podemos usar esta aresta.
|
 |
Agora, selecionamos a menor aresta. Note que os vértices $$3$$ e $$5$$ já estão conectados. Logo, se colocarmos esta aresta, formaremos um ciclo. Portanto, não podemos utilizá-la. |
 |
Agora, selecionamos a aresta seguinte. Como os vértices $$4$$ e $$5$$ ainda não estão conectados, podemos usar esta aresta.
|
 |
Agora, selecionamos a aresta seguinte. Como os vértices $$5$$ e $$6$$ ainda não estão conectados, podemos usar esta aresta.
|
Agora, já selecionamos $$5$$ arestas para a árvore, portanto, a árvore já está concluída. Note que esta MST é diferente da MST mostrada no começo da aula, mas as duas possuem o mesmo peso total de arestas.
Agora, vamos pensar em como fazer o código do algoritmo. Para fazer o passo $$1$$, basta fazer uma simples ordenação para as arestas. Para os passos $$2$$ e $$3$$, o recomendado é usar Union-Find para saber, de maneira rápida, se dois vértices estão numa mesma componente.
O código, em C++, fica assim:
https://gist.github.com/luccasiau/94b229cde5313cd8b7fc