Algoritmos para Grafos, via Sedgewick | Índice remissivo
(Esta página corresponde aproximadamente à seção 18.4 (Properties of DFS Forests) do capítulo 18 (Graph Search) e à seção 19.2 (Anatomy of DFS in digraphs) do livro de Sedgewick.)
Examine, uma vez mais, a função DIGRAPHdfs (e a função dfsR) que implementam a busca em profundidade. O arco v-w que dfsR percorre para visitar um vértice w pela primeira vez é conhecido como arco de arborescência (= tree arc). Na versão de dfsR para matriz de adjacência, por exemplo, um arco de arborescência é qualquer arco v-w imediatamente antes da linha "dfsR(G,w)".
Suponha, por um momento, que todo vértice de nosso digrafo G pode ser atingido a partir do vértice 0, ou seja, que todo vértice é término de um caminho que começa em 0. (Esse é o caso, por exemplo, se G é um grafo conexo.) Então, ao fim da execução de DIGRAPHdfs, o conjunto dos arcos de arborescência define uma arborescência com raiz 0. Dizemos que essa é a arborescência de busca em profundidade (= DFS tree) gerada por DIGRAPHdfs.
Se algum vértice de nosso digrafo G não pode ser alcançado a partir do vértice 0, o conjunto dos arcos de arborescência define várias arborescências, disjuntas uma da outra. Dizemos que esse conjunto de arborescências é a floresta de busca em profundidade (= DFS forest) gerada por DIGRAPHdfs. É claro que a floresta de busca em profundidade contém todos os vértices de G.
[A expressão "arborescência de busca" não é usual. É mais comum dizer "árvore de busca". Mas no presente texto a palavra "árvore" é reservada para um conceito ligeiramente diferente. A expressão "floresta de busca" é duplamente infeliz: ela entra em choque com "arborescência de busca" e com o conceito usual de "floresta". Infelizmente, não sei como evitar isso.]
A função abaixo registra a floresta de busca em profundidade num vetor de pais parent . A função é quase idêntica a DIGRAPHdfs:
#define maxV 1000 static int conta, lbl[maxV]; static Vertex parent[maxV];/* A função DIGRAPHdfs visita todos os vértices e todos os arcos do digrafo G "em ordem DFS". A função registra a ordem em que os vértices são visitados no vetor lbl[x] e registra a floresta de busca no vetor parent. (Código inspirado no programa 18.3, p.87, de Sedgewick.) */
void DIGRAPHdfs (Digraph G) { Vertex v; conta = 0; for (v = 0; v < G->V; v++) lbl[v] = -1; for (v = 0; v < G->V; v++) if (lbl[v] == -1) { parent[v] = v; dfsR(G, v); } }/* Código para vetor de listas de adjacência. */
void dfsR (Digraph G, Vertex v) { link p; lbl[v] = conta++; for (p = G->adj[v]; p != NULL; p = p->next) if (lbl[p->w] == -1) { parent[p->w] = v; dfsR(G, p->w); } }
A relação entre a floresta de busca em profundidade e os arcos do digrafo que não estão na floresta pode ser em parte descrita pelo vetor lbl:
(Mas as recíprocas não são verdadeiras. É preciso acrescentar a numeração em pós-ordem à numeração registrada no vetor lbl para classificar os arcos.)
No caso de digrafos simétricos, a classificação dos arcos é bem mais simples, pois não há arcos cruzados:
Propriedade da DFS em Digrafos Simétricos: Depois de uma busca em profundidade num digrafo simétrico, todo arco que não pertence à floresta de busca é um arco de retorno ou um arco descendente.
Essa propriedade garante que depois de uma busca em profundidade num digrafo simétrico, todo arco v-w tal que parent[w] é diferente de v e parent[v] é diferente de w pode ser assim classificado:
(Este exemplo é cópia da figura 18.10, p.94, de Sedgewick.) Considere o grafo definido pelas arestas abaixo. Represente o grafo por sua matriz de adjacência.
0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5
Agora submeta o grafo à função DIGRAPHdfs. Eis as classificação dos arcos do grafo imposta pela busca em profundidade:
0-2 arborescência
2-0 pai
2-6 arborescência
6-2 pai
6-4 arborescência
4-3 arborescência
3-4 pai
3-5 arborescência
5-0 retorno
5-3 pai
5-4 retorno
4-5 descendente
4-6 pai
4-7 arborescência
7-0 retorno
7-1 arborescência
1-7 pai
7-4 pai
0-5 descendente
0-7 descendente
0-2 0-5 1-2 3-4 4-5 3-5
e exiba um "trace" da execução da função no formato do exemplo acima. (Suponha que o grafo é representado por sua matriz de adjacência.) Exiba também o estado do vetor lbl depois de cada alteração de algum componente. Faça também um desenho da floresta de busca em profundidade.
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
Suponha que o grafo é representado por uma matriz de adjacência.