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.
Esta p�gina � um resumo do cap�tulo 24 (somente algoritmo de Prim) de CLR.
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.
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).
� 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.
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.
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,
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)).
Repita para o algoritmo
�RVORE-DE-PRIM-COM-FILA-DE-V�RTICES.
D� especial aten��o � implementa��o da linha 13.