Algoritmo de Kruskal para o problema MST

Esta página trata do problema das árvores geradoras de peso mínimo em grafos. Trata-se de uma generalização do problema da árvore geradora discutido no capítulo Árvores geradoras de grafos. Esse problema é mais conhecido pelas iniciais MST de minimum spanning tree. A página trata, em particular, do célebre algoritmo de Kruskal para o problema da MST.

Esta página é inspirada no capítulo 23 do livro CLRS.

a-250-node-euclidean-graph-and-its-mst-1.png

Árvores geradoras de peso mínimo

Suponha que cada aresta uv de um grafo tem um peso p[uv]. Cada peso é um número positivo, negativo, ou nulo. Vamos supor que os pesos são inteiros (embora isso não seja essencial). Diremos que p é um vetor de pesos. O peso de um sub­grafo T do grafo é a soma dos pesos das arestas de T e será denotado por p(T).

Sedgewick-Wayne/trace-of-prims-algorithm-lazy-version-x.png

Exemplo A.  A tabela abaixo atribui um peso p[a] a cada aresta a do grafo da figura. (Neste exemplo, o peso de cada aresta é proporcional ao comprimento geométrico do segmento de reta que representa a aresta na figura.)

a]  4 5 4 7 5 7 0 7 1 5 0 4 2 3 1 7 0 2 1 2 1 3 2 7 6 2 3 6 6 0 6 4
p[a35 37 28 16 32 38 17 19 26 36 29 34 40 52 58 93

O conjunto de arestas  0 7 7 1 7 5 5 4 0 2 2 3 2 6  define uma árvore geradora do grafo. O peso dessa árvore é 35 + 28 + 16 + 17 + 19 + 26 + 40 = 181. Nenhuma outra árvore geradora tem peso menor (mas isso não é óbvio).

Uma MST (= minimum spanning tree) de um grafo com vetor de pesos p é uma árvore geradora T do grafo que minimiza p(T).

Problema da MST:  Dado um grafo G com pesos inteiros arbitrários nas arestas, encontrar uma MST de G.

É claro que uma instância do problema tem solução se e somente se G é conexo, ou seja, se cada vértice de G estiver ao alcance de cada um dos demais.

Exercícios 1

  1. Mostre que uma instância do problema da MST tem solução se e somente se G é conexo.
  2. Mostre que o seguinte algoritmo guloso não resolve o problema da MST.  Seja a1, a2, … , am a sequência das arestas em ordem crescente de pesos. No início da primeira iteração, pinte um vértice de preto e os demais vértices de branco. Para i = 1, 2, … , m faça o seguinte: se uma das pontas de ai é preta e a outra ponta é branca, acrescente ai à árvore e pinte de preto a ponta que era branca.
  3. Discuta a seguinte afirmação: Para resolver o problema da MST num grafo conexo com n vértices, basta escolher as n − 1 arestas de menor peso.

O algoritmo de Kruskal

J. Kruskal descobriu (1956) um algoritmo muito eficiente para o problema da MST.  O algoritmo de Kruskal é iterativo. Cada iteração começa com uma floresta geradora F de G. A cada iteração, o algoritmo acrescenta a F uma aresta de G. O critério de escolha da nova aresta é guloso: o algoritmo escolhe uma aresta de peso mínimo dentre as que são externas à floresta. Uma aresta a é considerada externaF se satisfaz duas condições naturais e óbvias: (1) não pertence a F e (2) o grafo F + a é uma floresta. O algoritmo pode, então, ser resumido assim:

enquanto existem arestas externas,
.oo escolha uma aresta externa de peso mínimo,
.oo seja uv a aresta escolhida,
.oo troque F por F + uv.

No início da primeira iteração, a floresta F não tem aresta alguma (e o conjunto de vértices de F é V(G)).  No início da última iteração, G não tem arestas externas a F.

No fim da execução do algoritmo, a floresta F será conexa desde que o grafo G seja conexo. Sob essa hipótese, F será uma MST, como mostraremos mais abaixo.

the-web/kruskal-meyavuz.png

Exemplo B.  O vídeo Kruskal's Algorithm Animation no YouTube aplica o algoritmo de Kruskal a um grafo cujos vértices são pontos aleatórios no plano. O grafo é completo, ou seja, todo par de vértices é uma aresta. O peso de cada aresta é a distância geométrica entre suas pontas.

Sedgewick-part5-java/kruskal-fig-20-13-a.png

Exemplo C.  Considere o problema de encontrar uma MST no grafo com pesos nas arestas definido a seguir. As arestas são apresentadas em ordem crescente de peso.

53 71 76 20 07 01 43 54 74 06 46 05 
 0  1  2  3  4  5  6  7  8  9  9 11 
Sedgewick-part5-java/kruskal-fig-20-13-h.png

Veja o rastreamento da execução do algoritmo de Kruskal. Cada linha da tabela registra as arestas da floresta F e o peso p(F) da floresta no início de uma iteração.

-                       0               
53                      0
53 71                   1
53 71 76                3
53 71 76 20             6
53 71 76 20 07         10
53 71 76 20 07 43      16
53 71 76 20 07 43 74   24

A última linha dá as arestas de uma MST.

Prova da correção do algoritmo.  Vamos supor que o grafo G é conexo. Para mostrar que o algoritmo de Kruskal está correto, basta provar o seguinte invariante do processo iterativo: no início de cada iteração,

F é subgrafo de alguma MST de G. (*)

Essa proposição é obviamente verdadeira no início da primeira iteração, quando F não tem aresta alguma. Suponha agora que estamos no início de alguma iteração (exceto a última) e que F faz parte de uma MST M. Seja uv a aresta que o algoritmo escolhe nessa iteração. Precisamos provar que a floresta F + uv faz parte alguma MST.

Como uv é externaF, uma das pontas de uv está em uma componente de F e a outra ponta está em outra componente. Seja U o conjunto de vértices de uma dessas componentes.

Agora considere a relação entre uvM. Se uv é aresta de M, nada mais temos a provar. Suponha agora que uv não é aresta de M e seja C o único caminho de uv em M. Alguma aresta xy de C tem uma ponta em U e outra ponta em U. Segue daí que xy não pertence a F e F + xy  é uma floresta, donde xy é externa a F. Como xy não foi escolhida durante a iteração corrente, temos p(xy) ≥ p(uv). Observe agora que

M − xy + uv

é uma árvore geradora. O peso dessa nova árvore não é maior que o peso de M. Logo, a nova árvore geradora é uma MST. Essa nova MST contém F + uv. Era o que queríamos provar.

Exercícios 2

  1. Diga o quê o algoritmo de Kruskal faz.
  2. Qual a diferença entre provar que um algoritmo está correto e descrever os passos do algoritmo em português (o algoritmo faz isso, depois faz aquilo …, etc.)?
  3. Prove que uma aresta é externa a F se e somente se tem uma ponta em uma componente de F e a outra ponta em outra componente.
  4. É verdade que uma MST contém todas as arestas de peso mínimo de G?
  5. ★ Preencha os detalhes do esboço da prova de (*). Prove os passos da prova que não forem óbvios.
  6. Grafo desconexo.  Que acontece se o algoritmo de Kruskal for aplicado a um grafo desconexo?

Implementação do algoritmo de Kruskal

Para implementar o algoritmo de Kruskal, é preciso inventar uma maneira eficiente de decidir se uma dada aresta de G é externa a F. É claro que uma aresta é externa a F se e somente se tem uma ponta em uma componente de F e a outra ponta em outra componente. Isso sugere que o tipo abstrato de dados union-find (veja o capítulo A estrutura union-find) pode ser útil.

O algoritmo MST-Kruskal abaixo recebe um grafo conexo G com n vértices, m arestas, e um peso inteiro arbitrário p[uv] para cada aresta uv. O algoritmo devolve uma MST de G.

MST-Kruskal (G, n, m, p)
11 . arestas := Sort-Edges (G, m, p)
12 . X := { }
13 . Initialize ()
14 . para i := 1 até m
15 .ooo uv := arestas[i]
16 .ooo r := Find (u)
17 .ooo s := Find (v)
18 .ooo se rs
19 .oooooo X := X ∪ { uv }
10 .oooooo Union (r, s)
11 . devolva (V(G), X)

O algoritmo auxiliar Sort-Edges recebe um grafo G com m arestas e um peso p[uv] para cada aresta uv e devolve um vetor arestas[1 .. m] que contém todas as arestas em ordem crescente de pesos.

No início de cada iteração, X é o conjunto de arestas de uma floresta geradora, que chamaremos F. Os algoritmos auxiliares Find e Union atuam sobre as componentes de F:

Desempenho do algoritmo.  Vamos supor que as implementações de Initialize, Find e Union usam a heurística union-by-rank. Então Initialize consome Ο(n) unidades de tempo, cada execução de Find consome Ο(lg n) e cada execução de Union consome Ο(1) unidades de tempo. Com isso, o bloco de linhas 2-10 do algoritmo MST-Kruskal consome Ο(n + m lg n) unidades de tempo.

A linha 1 do algoritmo consome Ο(m lg m) unidades de tempo. Como m < n², podemos dizer que a linha 1 consome Ο(m lg n) unidades de tempo. Assim, o consumo de tempo total de MST-Kruskal está em

Ο(n + m lg n) .

Poderíamos lançar mão das implementações de Initialize, Find e Union que usam a heurística path compression (além da heurística union-by-rank). Com isso, o bloco de linhas 2-10 do algoritmo MST-Kruskal consumiria apenas Ο(n + m log* n) unidades de tempo, em termos amortizados. Mas o consumo de tempo total do algoritmo continuaria em Ο(n + m lg n) por conta da linha 1, que rearranja as arestas em ordem crescente de peso.

Exercícios 3

  1. Execute o algoritmo MST-Kruskal sobre o grafo definido pela matriz de pesos abaixo, com - representando .
      1 2 3 4 5 6 7 8
    1 - 3 - 4 5 - - -
    2 3 - 9 - 6 - - -
    3 - 9 - - 8 2 - -
    4 4 - - - 6 - 6 7
    5 5 6 8 6 - 9 - 8
    6 - - 2 - 9 - - -
    7 - - - 6 - - - 8
    8 - - - 7 8 - 8 -
  2. Mostre que algoritmo MST-Kruskal consome Ω(n + m lg n)  unidades de tempo no pior caso. Que parte do algoritmo impede uma implementação mais rápida?
  3. Escreva uma versão do algoritmo MST-Kruskal que calcule apenas o peso de uma árvore de peso mínimo. Escreva uma versão enxuta, sem variáveis e comandos supérfluos.
  4. Suponha que o peso de cada aresta pertence ao conjunto 1 .. 9. Descreva informalmente a implementação assintoticamente mais rápida que você conhece para o algoritmo de Kruskal nesse caso. Qual o consumo de tempo, em notação Ο, de sua implementação?
  5. Árvore geradora de peso máximo.  Seja MST-Z um algoritmo que resolve o problema da MST. Use esse algoritmo para resolver o seguinte problema: Dado um grafo conexo G e um vetor de pesos sobre as arestas de G, encontrar uma árvore geradora de G que tenha peso máximo.
  6. Seja G um grafo conexo e p um vetor de pesos sobre as arestas de G. Sejam a e b duas arestas de G. Encontre uma árvore geradora T de G que contenha ab e minimize a soma dos pesos das arestas que não estão em T.
  7. Grafos desconexos.  Modifique a definição de árvore geradora de modo que toda instância do problema da MST tenha solução (mesmo que o grafo seja desconexo). Escreva uma versão do algoritmo MST-Kruskal para essa versão modificada do problema.
  8. Bottleneck spanning tree. Descreva um algoritmo que resolva o seguinte problema: dado um grafo conexo com vetor de pesos p, encontrar uma árvore geradora cuja aresta mais pesada é o mais leve possível, ou seja, encontrar uma árvore geradora cujo peso seja min maxuv p[uv], sendo o mínimo tomado sobre todas as árvores geradoras e o máximo sobre todas as arestas da árvore).