Arborescências
Os algoritmos de busca sugerem o seguinte conceito, que pode ser entendido
como uma generalização do conceito de caminho simples. Uma arborescência é uma
sequência da forma
(v[0], a[1], v[1], a[2], v[2], ..., a[k], v[k]),
onde v[0], ..., v[k] são vértices distintos dois a dois, a[1], ..., a[k]
são arcos distintos dois a dois, e, para cada j, a[j] é um arco da forma (v[i],
v[j], com i < j).
Para cada j, dizemos que a ponta inicial de a[j] é o predecessor (pai) do
vértice v[j]. O primeiro vértice da sequência, v[0], é a raiz da arborescência. O
número de j é o índice ou posição do vértice v[j] na arborescência.
Para qualquer vértice w de uma arborescência, alguma sequência da
arborescência é um caminho simples que começa na raiz v[0] da arborescência e vai até
w: trata-se da sequência (v[0], ..., pppw, ppw, pw, w), onde pw é o
predecessor de w, ppw é o predecessor de pw, etc.
Uma arborescência é um dígrafo em que:
Não existem vértices com grau de entrada1 maior que 1,
Existe exatamente um vértice com grau de entrada 0,
Cada um dos vértices é término de um caminho com origem no único vértice que
tem grau de entrada nulo.
O único vértice com grau de entrada nulo é a raiz da arborescência. Todos os
vértices diferentes da raiz têm grau de entrada igual a 1.
Arborescências são conhecidas por vários outros sinônimos: árvore radicada
(rooted tree), árvore enraizada, árvore dirigida (directed tree), árvore de busca (search
tree).
Exemplo 1: o conjunto de arcos abaixo define uma arborescência com raiz 0.
0–1 1–2 1–3 3–4 3–5 0–6 6–7 6–8 6–9 0–10 10–11
Exemplo 2: digamos que os vértices do grafo são 0, 1, 2, 3, 4, 5, 6, 7, 8 e os arcos são a,
b, c, d, e, f, g, h, i, j.
Ponta inicial 0 0 2 6 6 6 1 1 3 8
a b c d e f g h i j
Arco
0 2 6 0 2 4 3 3 7 5
Ponta final
A sequencia (6, d, 0, f, 4, b, 2) é uma arborescência com raiz 6. O predecessor
do vértice 2 é o vértice 0. O índice de 2 é 3 e o índice de seu predecessor é 1.
O caminho que vai de 6 a 2 na arborescência é (6, d, 0, b, 2).
1
O grau de entrada (indegree) de um vértice w num dígrafo é o número de arcos que têm ponta final w.
1
Para todo vértice v de uma arborescência, existe um e apenas um caminho
simples que começa na raiz e termina em v.
Toda arborescência com v vértices tem exatamente v–1 arcos.
Todo vértice w de uma arborescência, exceto a raiz, tem um pai. Trata-se do
único vértice v tal que v-w é um arco.
Para qualquer vértice v de uma arborescência, cada vértice adjacente a v é um
filho de v. Vértice sem filhos são chamados folha (leaves) ou vértices externos (external
nodes).
Em uma arborescência, um vértice v é ancestral de um vértice w se o único
caminho que vai da raiz até w passa por v. Nessas mesmas condições, diz-se que w é um
descendente de v. Todo vértice é descendente da raiz.
Um ancestral próprio de um vértice w é qualquer ancestral de w exceto o próprio
w. Um descendente próprio de um vértice v é qualquer descendente de v que seja
diferente de v.
Para qualquer vértice v da arborescência, seja D(v) o conjunto de todos os
descendentes de v. O conjunto de todos os arcos que tem ambas as pontas em D(v)
define uma arborescência com raiz v. Dizemos que esta é a subarborescência com raiz.
Representação de arborescências
Para representar uma arborescência basta registrar o predecessor de cada vértice.
v[0] e os vértices fora da arborescência não têm predecessor. O predecessor de cada
vértice pode ser confortavelmente acomodado em um utility field, digamos pred,
assim:
v[j]->pred
é o predecessor de v[j]. Podemos convencionar que v[0]->pred vale v[0]. Para
todo w fora da arborescência, w->pred vale NULL.
Varredura em preordem
Uma varredura em preordem de uma arborescência é uma maneira sistemática
de visitar os vértices da arborescência.
Uma descrição recursiva da varredura em preordem:
1. Visite a raiz,
2. Para cada filho v da raiz, faça uma varredura em preordem da subarborescência com
raiz v.
Quando a busca em profundidade é aplicada a uma arborescência com raiz 0 ela
faz uma varredura em preordem:
static int conta, pre[maxV];
A função preordem recebe uma arborescência G com raiz r e visita os vértices
de G em preordem. A ordem em que os vértices são visitados é registradas no vetor
pre.
void preordem(Grafo G, Vertice r){
conta = 0;
visitaR(G, r);
}
void visitaR(Grafo G, Vertice v){
link p;
2
pre[v] = conta++;
for (p = G->adj[v]; p != NULL; p = p->prox)
visitaR(G, p->w);
}
Vetor de pais
O vetor de pais de uma arborescência é um vetor (parent), tal que, para cada
vértice w distinto da raiz, parent[w] é o pais de w.
Exemplo: eis o vetor de pais da arborescência do exemplo 1.
v 0 1 2 3 4 5 6 7 8 9 10 11
parent[v] 0 0 1 1 3 3 0 6 6 6 0
10
Dado o vetor de pais, parent, de uma arborescência, é fácil determinar o
caminho que leva da raiz a um dado vértice: basta inverter a sequência impressa pelo
seguinte fragmento de código:
Vertice x;
for (x = v; parent[x] != x; x = parent[x])
printf("%d-", x);
printf("%d", x);
Exercícios
1. Quantos arcos tem uma arborescência com t vértices?
2. Escreva uma função que decida se um dado grafo é ou não uma arborescência. Em
caso afirmativo, a função deve devolver a raiz da arborescência. Em caso negativo, a
função deve devolver -1.
3. Escreva uma função que construa uma arborescência aleatória com V vértices. Cada
vértice deve ter no máximo f filhos.
4. Visite os vértices da arborescência abaixo em preordem.
0–1 1–2 1–3 3–4 3–5 0–6 6–7 6–8 6–9 0–10 10–11
Registre a ordem em que os vértices são visitados num vetor pré indexado pelos
vértices.
5. Considere a arborescência descrita abaixo.
0–1 1–2 1–3 0–4 4–5 4–6
Qual a raiz?
Considere a seguinte numeração dos vértices:
v 0 1 2 3 4 5 6 7
pre[v] 0 1 2 4 3 4 5 6
Essa numeração corresponde a uma varredura em preordem?
6. Defina varredura em pós-ordem de uma arborescência. Escreva uma função que
execute a varredura de uma arborescência em pós-ordem.
3