MAC0338   Análise de Algoritmos

Página preparada por Paulo Feofiloff para a disciplina MAC 338 Análise de Algoritmos, versão 1999.
O endereço original desta página é http://www.ime.usp.br/~pf/mac338/aulas/MST.htm.

Árvores geradoras de peso mínimo em grafos simétricos

Esta página é um resumo do capítulo 24 (somente algoritmo de Prim) de CLR.

Árvores de peso mínimo

Imagine que cada aresta (u,v) de um grafo simétrico tem um peso numérico w(u,v). Como nosso grafo é simétrico, temos w(u,v)= w(v,u). Ademais, o peso de cada aresta pode ser positivo, negativo ou nulo.

Onde esses pesos ficam armazenados? Você pode imaginar que w é um algoritmo que recebe u e v e devolve w(u,v). Também pode imaginar que os valores de w ficam dentro das listas de adjacência: na lista Adj[u], junto com a célula que contém um vértice v fica também o número w(u,v).

PROBLEMA: Dado um grafo simétrico, um vértice r, e uma função w que atribui um peso a cada aresta, encontrar uma árvore geradora com raiz r que tenha peso mínimo.

(O peso de uma árvore é a soma dos pesos de suas arestas.) Se o grafo não é conexo então o problema não tem solução. Caso contrário, o problema tem solução qualquer que seja r; e todas essas soluções têm o mesmo peso. Mais especificamente: se existe uma árvore geradora com raiz r e peso P então, para qualquer vértice s, existe uma árvore geradora de peso P e raiz s.

Exercícios

1. Suponha dado um grafo simétrico com pesos nas arestas. Suponha que um vetor de predecessores pred representa uma árvore geradora de peso P. Escreva um algoritmo que receba pred e um vértice s e devolva o vetor de predecessores de uma árvore geradora com raiz s e peso P.
   
   
2. Suponha dada uma árvore geradora de peso mínimo num grafo simétrico. Digamos que a árvore tem raiz r. Seja v um vértice qualquer e seja C o caminho de r a v na árvore. É verdade que todo caminho de r a v no grafo tem peso maior ou igual ao peso de C?
   
   
3. Qual a diferença entre uma árvore geradora de peso mínimo e uma árvore de caminhos mínimos? Dê exemplos.
   
   
4. Mostre que a seguinte idéia não produz uma árvore geradora de peso mínimo.  Para cada vértice u faça o seguinte: escolha, dentre as arestas que saem de u, uma que tenha peso mínimo.
   
   
5. Mostre que a seguinte variante do algoritmo de Prim não funciona:
   1. Coloque o conjunto de arestas em ordem crescente de peso.
   2. No início da primeira iteração, o vértice r é NEGRO e os demais vértices são BRANCOs. No início das iterações subseqüentes, alguns vértices são NEGROs enquanto outros são BRANCOs.
   3. Cada iteração escolhe a próxima aresta, digamos (u,v), na ordem crescente de pesos. Se u é NEGRO e v é BRANCO então acrescente (u,v) à árvore e faça v NEGRO. Caso contrário, descarta (u,v).
   
   
   

Algoritmo de Prim: versão 1

Eis um algoritmo guloso que resolve o problema da árvore geradora de peso mínimo. No início de cada iteração temos dois tipos de vértices, os NEGROs e os BRANCOs, e uma árvore com raiz r que "cobre" o conjunto dos vértices NEGROs. Cada iteração acrescenta à árvore a aresta mais leve dentre as que ligam um vértice NEGRO a um vértice BRANCO.

Eis uma implementação inocente e ineficiente da idéia. Suporemos que os vértices do grafo são 1, 2, . . . . , n.

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18

ÁRVORE-DE-PRIM-VERSÃO-INOCENTE (n, Adj, w, r)   para u := 1 até n faça     cor[u] := BRANCA     pred[u] := 0   u := 0   v := r   repita     cor[v] := NEGRA     pred[v] := u     minw := INFINITO     para i := 1 até n faça       se cor[i] = NEGRA então         para cada j em Adj[i] faça           se cor[j] = BRANCA  e  w(i,j) < minw  então             minw := w(i,j)             u := i             v := j   até que minw = INFINITO   devolva pred

A implementação pode não ser das melhores, mas a saída é sofisticada. O algoritmo devolve um vetor pred;  se pred[v] = 0 para algum v distinto de r então o grafo não tem árvore geradora alguma;  senão, pred representa uma árvore geradora de peso mínimo com raiz r.

Esta versão é deselegante e ineficiente: consome Omega(nm) unidades de tempo, onde m é o número de arestas do grafo (= metade da soma dos comprimentos de todas as listas de adjacência).

Por que o algoritmo está correto?

É claro que o algoritmo ÁRVORE-DE-PRIM-VERSÃO-1 produz uma árvore geradora com raiz r (supondo que o grafo seja conexo). Resta saber se nossa estratégia gulosa garante que a árvore tem peso mínimo.

Vamos dar nomes às coisas. No início de cada iteração, seja A o conjunto das arestas da forma (pred[x],x) tais que x é diferente de r e cor[x] = NEGRO. O conjunto A é a parte pronta da árvore que o algoritmo está construindo. É preciso mostrar que, no início de cada iteração,

A  faz parte de uma árvore geradora de peso mínimo.

Eis um esboço da demonstração. Suponha que, no início de uma iteração, A faz parte de uma árvore geradora T de peso mínimo. Durante esta iteração, a aresta (u,v) será acrescentada a A. Se esta nova aresta já está em T não é preciso se preocupar com nada. Mas suponha que esta nova aresta não está em T; que fazer? É preciso mostrar que existe uma aresta (x,y) em T-A tal que

T - (x,y) + (u,v)

é uma árvore geradora de mesmo peso que T. Como encontrar a aresta (x,y)? Resposta: (x,y) é uma aresta com cor[x] = NEGRO e cor[y] = BRANCO que pertence ao único caminho em T que liga u a v. (Isso está tecnicamente um tanto errado, mas não tenho paciência de acertar as minúcias técnicas.) Tanto (x,y) quanto (u,v) têm ponta inicial NEGRA e ponta final BRANCA; portanto

w(u,v)   <=   w(x,y)

porque esse foi o critério de escolha de (u,v). Logo, T - (x,y) + (u,v) é uma árvore tão mínima quanto T.

Algoritmo de Prim: versão 2

Nossa segunda versão usa uma "fila" de arestas, digamos Q, organizada com base no peso w. Cada aresta é representada como um par ordenado de vértices. Os detalhes de implementação da fila ficam por conta da imaginação do leitor, mas tudo se passa como se as arestas estivessem na fila sempre em ordem crescente de w.

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

ÁRVORE-DE-PRIM-COM-FILA-DE-ARESTAS (n, Adj, w, r)   para u := 1 até n faça     cor[u] := BRANCA     pred[u] := 0   Q := CRIE-FILA-VAZIA()   cor[r] := NEGRO   para cada x em Adj[r] faça     INSIRA-NA-FILA (Q,(r,x))   enquanto Q não está vazia faça     (u,v) := RETIRE-MÍNIMO (Q)     se cor[v] = BRANCA então       cor[v] := NEGRO       pred[v] := u       para cada x em Adj[v] faça         se cor[x] = BRANCA então           INSIRA-NA-FILA (Q,(v,x))   devolva pred

No início de cada iteração, Q contém todas as arestas com ponta inicial NEGRA e ponta final BRANCA (o loop nas linhas 13-15 garante isso). Além disso, Q pode conter algumas arestas que têm ambas as pontas NEGRAs; eu poderia retira-las de Q a cda iteração, mas isso daria muito trabalho pois dá trabalho eliminar um elemento de Q.

O sub-algoritmo RETIRE-MÍNIMO retira de Q uma aresta (u,v) tal que w(u,v) é mínimo. O sub-algoritmo INSIRA-NA-FILA simplesmente insere uma nova aresta na fila.

Se a fila de prioridades for bem implementada (um heap, por exemplo), o consumo de tempo dessa versão será O(n log(m) + m log(m)), onde m é o número de arestas do grafo.

Algoritmo de Prim: versão 3

Finalmente, eis a versão mais eficiente e sofisticada do algoritmo de Prim. Ela usa uma "fila" de vértices, com prioridade ditada por uma chave a ser discutida em seguida.

No início de cada iteração temos dois tipos de vértices, os NEGROs e os BRANCOs, e uma árvore com raiz r que "cobre" o conjunto dos vértices NEGROs. Há também arestas da árvore ligando vértices NEGROs a vértices BRANCOs, mas essas arestas são provisórias. Cada iteração acrescenta à árvore a aresta mais leve dentre as que ligam um vértice NEGRO a um vértice BRANCO.

Vamos supor que os vértices do grafo são 1, 2, . . . , n. 

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

ÁRVORE-DE-PRIM-COM-FILA-DE-VÉRTICES (n, Adj, w, r)   para u := 1 até n faça     cor[u] := BRANCO     chave[u] := INFINITO     pred[u] := 0   Q := CRIE-FILA-VAZIA ()   para u := 1 até n faça     INSIRA (Q,v)   chave[r] := 0   enquanto Q não está vazia faça     u := RETIRE-MÍNIMO (Q)     para cada v em Adj[u] faça       se cor[v] = BRANCO  e  w(u,v) < chave[v] então         chave[v] := w(u,v)         pred[v] := u     cor[u] := NEGRO   devolva pred

O comando CRIE-FILA-VAZIA cria uma "fila" vazia com prioridades ditadas por chave. Os detalhes de implementação da fila ficam por conta do leitor, mas tudo se passa como se os vértices estivessem nessa fila sempre em ordem crescente da chave. O comando RETIRE-MÍNIMO (Q) retira de Q um vértice com chave mínima. A alteração do valor de chave[v] na linha 13 pode afetar a estrutura da fila; isso deve ser levado em conta quando a fila for implementada pra valer.

No início de cada iteração,

1. cor[x] = BRANCO se e só se x está em Q ;
2. para cada vértice BRANCO x temos chave[x] = w(pred[x],x) ;
3. para cada vértice BRANCO x, a aresta (pred[x],x) é uma aresta de peso mínimo dentre todas as arestas que começam bum vértice NEGRO e terminam em x.

Eficiência da versão 3

Suponha que a fila Q é implementada como um heap (veja também a árvore de Huffman). Qual a eficiência do ÁRVORE-DE-PRIM?

As linhas 5-7, que criam a fila de vértices, consomem O(n). O loop das linhas 9-15 é executado n vezes. Cada execução da linha 10 consome O(log(n)). A soma de todas as execuções da linha 10 será O(n log(n)).

O número total de execuções do bloco de linhas 12-14 ao longo da execução do algoritmo é O(m), onde m é o número de arestas do grafo. Cada execução da linha 13 consome O(log(n)) (poderá consumir bem mais se for mal implementada).

Conclusão final: o algoritmo é O((n+m) log(n)).

Exercícios

5. Escreva uma implementação mais detalhada do algoritmo ÁRVORE-DE-PRIM-COM-FILA-DE-ARESTAS. Implemente Q como um heap.

   Repita para o algoritmo ÁRVORE-DE-PRIM-COM-FILA-DE-VÉRTICES. Dê especial atenção à implementação da linha 13.
   
   

6. [MUITO BOM PARA SENTIR AS LIMITAÇÕES DA GULA]   Suponha que G é um grafo não necessariamente simétrico. Seja r um vértice do grafo. Para cada aresta (u,v), seja w(u,v) o peso da aresta. Escreva um algoritmo para resolver o seguinte problema: determinar uma árvore de peso mínimo dentre as que têm raiz r.