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:
| // | |
| // reino_de_succa.cpp | |
| // | |
| // Created by Lucca Siaudzionis on 08/06/15. | |
| // | |
| // Reino de Succa – Noic | |
| #include <cstdio> | |
| #include <algorithm> | |
| using namespace std; | |
| struct t_aresta{ | |
| int dis; | |
| int x, y; | |
| }; | |
| bool comp(t_aresta a, t_aresta b){ return a.dis < b.dis; } | |
| //——————– | |
| #define MAXN 50500 | |
| #define MAXM 200200 | |
| int n, m; // número de vértices e arestas | |
| t_aresta aresta[MAXM]; | |
| // para o union find | |
| int pai[MAXN]; | |
| int peso[MAXN]; | |
| // a árvore | |
| t_aresta mst[MAXM]; | |
| //——————– | |
| // funções do union find | |
| int find(int x){ | |
| if(pai[x] == x) return x; | |
| return pai[x] = find(pai[x]); | |
| } | |
| void join(int a, int b){ | |
| a = find(a); | |
| b = find(b); | |
| if(peso[a] < peso[b]) pai[a] = b; | |
| else if(peso[b] < peso[a]) pai[b] = a; | |
| else{ | |
| pai[a] = b; | |
| peso[b]++; | |
| } | |
| } | |
| int main(){ | |
| // ler a entrada | |
| scanf("%d %d", &n, &m); | |
| for(int i = 1;i <= m;i++) | |
| scanf("%d %d %d", &aresta[i].x, &aresta[i].y, &aresta[i].dis); | |
| // inicializar os pais para o union-find | |
| for(int i = 1;i <= n;i++) pai[i] = i; | |
| // ordenar as arestas | |
| sort(aresta+1, aresta+m+1, comp); | |
| int size = 0; | |
| for(int i = 1;i <= m;i++){ | |
| if( find(aresta[i].x) != find(aresta[i].y) ){ // se estiverem em componentes distintas | |
| join(aresta[i].x, aresta[i].y); | |
| mst[++size] = aresta[i]; | |
| } | |
| } | |
| // imprimir a MST | |
| for(int i = 1;i < n;i++) printf("%d %d %d\n", mst[i].x, mst[i].y, mst[i].dis); | |
| return 0; | |
| } |








