Aula 17: Grafos V – MST (Árvore Geradora Mínima) – Noic
Browse: Home / Informática / Curso Noic de Informática / Aula 17: Grafos V – MST (Árvore Geradora Mínima)
Aula 17: Grafos V - MST (Árvore Geradora Mínima)
"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 e ainda não
estão conectados, podemos usar esta
Agora, selecionamos a aresta seguinte.
Agora, selecionamos a menor aresta.
Note que os vértices e já
estão conectados. Logo, se colocarmos
esta aresta, formaremos um ciclo.
Portanto, não podemos utilizá-la.
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:
Isto deve ter sido o suficiente para entender o algoritmo de Kruskal. Tente agora resolver os problemas a seguir para se acostumar com o algoritmo.