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 
vértices, se quisermos selecionar o número mínimo de arestas para deixar o grafo restante conexo, selecionamos 
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
e 
, checar se eles já estão na mesma componente conexa (aqui, consideramos apenas as arestas já colocadas na árvore). - Se e 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:
Vamos, então, simular o procedimento.
 |
Primeiro, selecionamos a menor aresta. Como os vértices estão conectados, podemos usar esta aresta. |
 |
Agora, selecionamos a aresta seguinte. Como os vértices estão conectados, podemos usar esta aresta.
|
 |
Agora, selecionamos a aresta seguinte. Como os vértices estão conectados, podemos usar esta aresta.
|
 |
Agora, selecionamos a menor aresta. Note que os vértices 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 estão conectados, podemos usar esta aresta.
|
 |
Agora, selecionamos a aresta seguinte. Como os vértices estão conectados, podemos usar esta aresta.
|
Agora, já selecionamos 
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 
, basta fazer uma simples ordenação para as arestas. Para os passos 
e 
, 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // 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; | |
| } |