Aula 17: Grafos V - MST (Árvore Geradora Mínima)

0 Flares Facebook 0 0 Flares ×

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:

MST 1

 

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:

MST 2 MST 3

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 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:

  1. Liste todas as arestas em qualquer ordem.
  2. 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).
  3. 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):

MST 4

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.

MST 5  

 

Primeiro, selecionamos a menor aresta.

Como os vértices 1 e 5 ainda não

estão conectados, podemos usar esta

aresta.

MST 7  

 

Agora, selecionamos a aresta seguinte.

Como os vértices 1 e 2 ainda não

estão conectados, podemos usar esta

aresta.

 

MST 8  

 

Agora, selecionamos a aresta seguinte.

Como os vértices 2 e 3 ainda não

estão conectados, podemos usar esta

aresta.

 

MST 9  

 

Agora, selecionamos a menor aresta.

Note que os vértices 3 e 5

estão conectados. Logo, se colocarmos

esta aresta, formaremos um ciclo.

Portanto, não podemos utilizá-la.

MST 10  

 

Agora, selecionamos a aresta seguinte.

Como os vértices 4 e 5 ainda não

estão conectados, podemos usar esta

aresta.

 

MST 11  

 

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:

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.

Problema 1 - Frete da Família Silva

Problema 2 - Reduzindo Detalhes em um Mapa

Problema 3 - Copa do Mundo

Problema 4 - Estradas Escuras

Problema 5 - Itinerário do Papai Noel


As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: