Esta p�gina � uma prepara��o para o cap�tulo 24 de CLR.
Suponha que r � um v�rtice de um grafo. Uma �rvore geradora com raiz r � um conjunto A de arestas que seja minimal com rela��o � seguinte propriedade:
para todo v�rtice v , existe um caminho de r a v em A.
A express�o "geradora" est� a� para dizer que todo v�rtice do grafo pode ser atingido em A a partir de r. A express�o "em A" significa que todas as arestas do caminho pertencem a A.
A condi��o "minimal" (ou seja, para toda aresta a em A, o conjunto A-{a} n�o tem a propriedade) na defini��o de �rvore geradora � fundamental. Uma conseq��ncia dessa condi��o � que, para cada v, existe apenas um caminho de r a v.
� claro que s� existe �rvore geradora com raiz r se o territ�rio de r � o conjunto de todos os v�rtices. Se o grafo � sim�trico, s� existe �rvore geradora, qualquer que seja r, se o grafo � conexo. Reciprocamente, se um grafo sim�trico � conexo ent�o cada um de seus v�rtices � raiz de uma �rvore geradora.
Qualquer �rvore geradora com raiz r pode ser representada no computador por um "vetor de predecessores", digamos pred. Para cada v�rtice v, pred[v] � o predecessor de v no �nico caminho que leva de r a v na �rvore. � evidente que r n�o tem predecessor. Os v�rtices que n�o podem ser alcan�ados a partir de r tamb�m n�o t�m predecessor.
O conjunto de arestas da �rvore ser� simplesmente o conjunto de todas as arestas da forma (pred[v],v) com v diferente de r.
� claro que pred � um vetor indexado por v�rtices com valores que tamb�m s�o v�rtices. Oooops! Pequena corre��o: pred[u] tamb�m pode ter o valor especial NIL, que indica aus�ncia de predecessor. (Na verdade, esse NIL � um pouco estranho. O CLR usa NIL porque ele est� imaginando uma implementa��o sofisticada em que cada v�rtice � um ponteiro. Se os seus v�rtices s�o 1, 2, . . . , n ent�o faz mais sentido usar 0 no lugar de NIL.)
Por exemplo, se r = 1 e a �rvore tem um caminho (1,2,3,4,5) ent�o pred ter� a apar�ncia indicada na figura.
| . . . | 1 | 2 | 3 | 4 | 5 | . . . |
| 0 | 1 | 2 | 3 | 4 |
Para obter um caminho m�nimo que termina em v basta construir a seq��ncia
v, predecessor de v, predecessor do predecesssor de v, etc.
at� chegar a r. Depois, � s� imprimir a seq��ncia de-tr�s-pra-frente.
Eis como extrair de pred um caminho m�nimo de s a um v�rtice v (se n�o existe caminho algum de s a v ent�o o algoritmo n�o imprima nada):
IMPRIMA-CAMINHO-REC (pred, s, v)
se v = s
ent�o imprima s
sen�o se pred[v] <> NIL
ent�o IMPRIMA-CAMINHO (pred, s, pred[v])
imprima v
Se voc� n�o se incomoda em receber o caminho de-tr�s-pra-diante ent�o pode usar a seguinte vers�o iterativa (se n�o existe caminho algum de s a v ent�o o algoritmo n�o imprima nada):
IMPRIMA-CAMINHO-IT (pred, s, v)
se pred[v] <> NIL ent�o
enquanto v <> NIL fa�a
imprima v
v := pred[v]
Problema: Dado um grafo e um v�rtice r, encontrar uma (qualquer uma) �rvore geradora com raiz r. � muito f�cil resolver o problema com um algoritmo guloso. No in�cio de cada itera��o temos duas classes de v�rtices, a classe dos v�rtices NEGROs e a classe dos BRANCOs, e uma �rvore com raiz r que "cobre" o conjunto dos v�rtices NEGROs. Cada itera��o acrescenta � �rvore alguma aresta que vai de um v�rtice NEGRO a um v�rtice BRANCO e em seguida pinta esse �ltimo v�rtice de NEGRO.
Vamos supor que os v�rtices do grafo s�o 1, 2, . . . , n. Para administrar a coisa, conv�m introduzir uma terceira cor CINZA.
1
2
3
4
5
6
7
8
9
10
11
�RVORE (n, Adj, r)
para u := 1 at� n fa�a
cor[u] := BRANCO
pred[u] := 0
cor[r] := CINZA
enquanto existe u tal que cor[u] = CINZA fa�a
para cada v em Adj[u] fa�a
se cor[v] = BRANCO ent�o
cor[v] := CINZA
pred[v] := u
cor[u] := NEGRO
devolva pred
Veja como a sa�da de nosso algoritmo � sofisticada: O algoritmo devolve um vetor pred. Se pred[v] � diferente de 0 para todo v�rtice exceto r (� justamente isso que acontece quando o grafo � conexo) ent�o o vetor pred representa uma �rvore geradora com raiz r. Se pred[v] = 0 para algum v diferente de r ent�o o grafo n�o � conexo e portanto n�o tem �rvore geradora (nesse caso, pred representa uma �rvore geradora do "peda�o" do grafo que cont�m r).
Qual o tamanho da �rvore que o algoritmo produz, supondo que o grafo � conexo? Resposta: a �rvore tem
n-1 arestas.
Prova: No fim da linha 4, a �rvore tem 0 arestas e "cobre" 1 v�rtice. A cada passagem pelo par de linhas 8-9, a �rvore ganha 1 aresta (a aresta (u,v)) e passa a "cobrir" um novo v�rtice (o v�rtice v). Conclus�o: no in�cio de cada nova execu��o do bloco de linhas 6-10 nossa �rvore tem x-1 arestas e "cobre" x.
N�o � dif�cil mostrar que toda e qualquer �rvore geradora em um grafo com n v�rtices tem n-1 arestas. De fato, gra�as � liberdade de escolha do v�rtice u na linha 5, o algoritmo �RVORE pode gerar qualquer �rvore geradora desejada.