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.