Figura 1:
Esta página volta a tratar do problema de encontrar o território de um vértice em um digrafo. Ela introduz uma versão especializada do algoritmo Território, conhecida como busca em profundidade (= depth-first search = dfs).
Nossa versão do algoritmo de busca em profundidade nada mais faz que pintar de preto todos os vértices do território de um vértice. Mas, diferentemente do algoritmo Território, ela visita os vértices numa certa ordem específica, que chamaremos "ordem de busca em profundidade".
Embora a ordem em que os vértices são visitados seja irrelevante para o mero mapeamento do território de um vértice, ela é essencial se desejamos determinar outras propriedades dos vértices além da pertinência ao território. Por exemplo, a ordem de busca em profundidade é muito útil para encontrar ciclos e componentes fortes eficientemente. O algoritmo de busca em profundidade discutido abaixo será usado como modelo para algoritmos dedicados a vários outros problemas.
Esta página é inspirada na seção 3 do capítulo 22 do CLRS. Veja também o verbete Depth-first search na Wikipedia.
O algoritmo Território tem um caráter "genérico": a ordem em que os vértices saem da lista manipulada pelo algoritmo é irrelevante. Já no algoritmo de busca em profundidade, a lista de vértices é administrada como uma pilha: o vértice que sai da lista é sempre o que foi colocado lá mais recentemente. Entretanto, se trocarmos "Lista" por "Pilha" mecanicamente no código de Território, não teremos o efeito desejado; as alterações do código precisam ser feitas de maneira mais sutil.
Eis uma versão preliminar do algoritmo de busca em profundidade. O algoritmo recebe um vértice r e pinta de preto todos os vértices do território de r. O código supõe que os vértices do digrafo são 1, 2, … , n e que os arcos são representados pelo vetor Adj[1..n] de listas de adjacência.
| 11 o para u ← 1 até n faça |
| 12 oooo cor[u] ← branco |
| 13 o cor[r] ← cinza |
| 14 o P ← Cria-Pilha (r) |
| 15 o enquanto P não estiver vazia faça |
| 16 oooo u ← Copia-Topo-da-Pilha (P) |
| 17 oooo se Adj[u] contém v tal que cor[v] = branco |
| 10 ooooooo então cor[v] ← cinza |
| 11 ooooooo então Coloca-na-Pilha (v, P) |
| 12 ooooooo senão cor[u] ← preto |
| 13 ooooooo senão Tira-da-Pilha (P) |
| 14 o devolva cor[1..n] |
[A numeração das linhas é descontínua porque quero manter, tanto quanto possível, a numeração da versão final do algoritmo, a ser discutida abaixo.] O comando Cria-Pilha(r) cria uma pilha com um único elemento igual a r. O comando Copia-Topo-da-Pilha(P) devolve o vértice que está topo da pilha P mas não remove o vértice da pilha. O comando Coloca-na-Pilha(v,P) insere o vértice v no topo da pilha P. O comando Tira-da-Pilha(P) remove o vértice que está no topo da pilha P.
À medida que penetra no digrafo a partir de r, nosso algoritmo constrói um caminho. Os vértices do caminho são pintados de cinza e armazenados na pilha. Na linha 12, o algoritmo já examinou todo o território de u e registra esse fato pintando u de preto.
Se a linha 7 do algoritmo for implementada literalmente, a lista Adj[u] será toda re-examinada a cada execução da linha, o que é muito ineficiente. Vamos supor, então, que dispomos de uma função Próximo para manipular a lista Adj[u]. Cada invocação dessa função devolve o próximo vértice da lista Adj[u], de tal forma que uma sucessão de invocações da função devolve cada vértice de Adj[u] uma e uma só vez. Se a lista tem g vértices, a g+1-ésima invocação de Próximo devolverá nil. A ordem em que Próximo extrai os elementos de Adj[u] é irrelevante. Podemos agora escrever a versão definitiva do algoritmo:
| Busca-em-Profundidade (n, Adj, r) |
| 11 o para u ← 1 até n faça |
| 12 oooo cor[u] ← branco |
| 13 o cor[r] ← cinza |
| 14 o P ← Cria-Pilha (r) |
| 15 o enquanto P não estiver vazia faça |
| 16 oooo u ← Copia-Topo-da-Pilha (P) |
| 17 oooo v ← Próximo (Adj[u]) |
| 18 oooo se v ≠ nil |
| 19 ooooooo então se cor[v] = branco |
| 10 ooooooo então ooo então cor[v] ← cinza |
| 11 ooooooo então ooo então Coloca-na-Pilha (v, P) |
| 12 ooooooo senão cor[u] ← preto |
| 13 ooooooo senão Tira-da-Pilha (P) |
| 14 o devolva cor[1..n] |
Para entender o funcionamento do algoritmo, basta observar que, no início de cada repetição do bloco de linha 6-13,
A pilha do algoritmo Busca-em-Profundidade pode ser implementada em um vetor P[1..n]. Uma variável t pode ser usada como índice do topo da pilha. A linha 4 (Cria-Pilha(r)) é então representada por
| o t ← 1 |
| o P[1] ← r |
A linha 5 (enquanto P não vazia faça) é implementada por
| o enquanto t > 0 faça |
A linha 6 (u ← Copia-Topo-da-Pilha(P)) é implementada por
| oooo u ← P[t] |
A linha 11 (Coloca-na-Pilha(v,P)) é implementada por
| oooooooooo então então t ← t+1 |
| oooooooooo então então P[t] ← v |
A linha 13 (Tira-da-Pilha(P)) é implementada por
| ooooooo então t ← t−1 |
A sequência de vértices (P[1],…,P[t]) é um caminho. Portanto, a pilha P[1..n] jamais sofre overflow.
Podemos supor que cada invocação de Próximo, Cria-Pilha, Copia-Topo-da-Pilha, Coloca-na-Pilha e Tira-da-Pilha consome tempo constante (ou seja, uma quantidade de tempo que não depende do tamanho do digrafo).
O bloco de linhas 1-4 consome tempo Ο(n). Agora considere o processo iterativo nas linhas 5-13 do algoritmo Busca-em-Profundidade. Cada execução bloco de linhas 6-13,
Uma execução de qualquer das duas alternativas consome tempo constante. Como um vértice preto jamais volta a ser cinza, o consumo total das ocorrências de (b) ao longo da execução do algoritmo Busca-em-Profundidade é Ο(n).
Agora considere o consumo total das ocorrências de (a). Ao longo da execução do algoritmo, cada arco do digrafo é examinado no máximo uma vez (a definição de Próximo garante isso). Portanto, o consumo total de todas as ocorrências de (a) é Ο(m), sendo m o número de arcos.
Assim, o consumo de tempo do algoritmo Busca-em-Profundidade é
Ο(m+n) .
Portanto, o algoritmo é linear.
O código de Busca-em-Profundidade fica mais simples se for escrito em estilo recursivo. A pilha de vértices passa a ser administrada pelo mecanismo de recursão, e assim torna-se invisível. A função Próximo também fica invisível.
É preciso escrever um pequeno "driver", que se incumbe de invocar o algoritmo recursivo propriamente dito:
| Busca-em-Profundidade (n, Adj, r) |
| 1 o para u ← 1 até n faça |
| 2 oooo cor[u] ← branco |
| 3 o Busca-Profund-R (r, cor) |
| 4 o devolva cor[1..n] |
A rotina Busca-Profund-R recebe um vetor cor que atribui branco, cinza ou preto a cada vértice do digrafo. Recebe também um vértice branco u. A rotina calcula o conjunto, digamos X, de todos os vértices que pertencem a passeios que começam em u e só usam vértices brancos. Finalmente, a rotina altera o vetor cor de modo que todos os vértices em X fiquem pretos.
| Busca-Profund-R (u, cor) |
| 1 o cor[u] ← cinza |
| 2 o para cada v em Adj[u] faça |
| 3 oooo se cor[v] = branco |
| 4 ooooooo então Busca-Profund-R (v, cor) |
| 5 o cor[u] ← preto |
Em muitas aplicações (veja, por exemplo, o problema de decidir se um digrafo é acíclico), o algoritmo Busca-Profund-R é aplicado a sucessivos territórios do digrafo, até que todos os vértices sejam visitados:
| Busca-em-Profundidade-Completa (n, Adj) |
| 1 o para u ← 1 até n faça |
| 2 oooo cor[u] ← branco |
| 3 o para r ← 1 até n faça |
| 4 oooo se cor[r] = branco |
| 5 ooooooo então Busca-Profund-R (r, cor) |
| 6 o devolva cor[1..n] |
Ao fim da execução desse algoritmo, todos os vértices são pretos. (Não tenho controle sobre a escolha dos argumentos de Busca-Profund-R, mas isso não importa para muitas aplicações.)
Uma enumeração dos vértices de um digrafo é uma sequência em que cada vértice aparece uma e uma só vez. No início desta página referimo-nos, vagamente, à enumeração dos vértices "em ordem de busca em profundidade". Na verdade, existem duas tais enumerações: a enumeração em pós-ordem e a enumeração em pré-ordem.
A enumeração em pós-ordem é definida pela ordem em que os vértices ficam pretos na busca em profundidade. A enumeração em pré-ordem é definida pela ordem em que os vértices ficam cinza.
O algoritmo abaixo faz uma busca em profundidade num digrafo e atribui dois números a cada vértice v: o número pré[v] é o momento em que o vértice fica cinza (ou seja, o momento em que é descoberto) e o número pós[v] é o momento em que o vértice fica preto (ou seja, o momento em que "morre").
| Pré-e-Pós-Ordem (n, Adj) |
| 1 o para u ← 1 até n faça |
| 2 oooo cor[u] ← branco |
| 3 o t ← 0 |
| 4 o para r ← 1 até n faça |
| 5 oooo se cor[r] = branco |
| 6 ooooooo então Busca-Pré-Pós-R (r) |
| 7 o devolva cor[1..n] |
| Busca-Pré-Pós-R (u) |
| 11 o cor[u] ← cinza |
| 12 o pré[u] ← t ← t+1 |
| 13 o para cada v em Adj[u] faça |
| 14 oooo se cor[v] = branco |
| 15 ooooooo então Busca-Pré-Pós-R (v) |
| 16 o cor[u] ← preto |
| 17 o pós[u] ← t ← t+1 |
(Compare Pré-e-Pós-Ordem com Busca-em-Profundidade-Completa e Busca-Pré-Pós-R com Busca-Profund-R.) Se os vértices forem colocados em ordem crescente de pré, teremos uma enumeração em pré-ordem. Se forem colocados em ordem crescente de pós, teremos uma enumeração em pós-ordem.
e k l f b g h i c j d a
h i g c k l f e b j d a
k l f j d e b g h i c a
Figura 1:
Figura 2:
