Busca em profundidade

 

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 searchdfs).

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.

Algoritmo de busca em profundidade

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 PCria-Pilha (r)
15 o enquanto  P  não estiver vazia faça
16 oooo uCopia-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 PCria-Pilha (r)
15 o enquanto  P  não estiver vazia faça
16 oooo uCopia-Topo-da-Pilha (P)
17 oooo vPróximo (Adj[u])
18 oooo se  vnil
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,

  1. um vértice x está na pilha se e somente se cor[x] é cinza;
  2. a sequência de vértices na pilha (começando na base e terminando no topo) é um caminho com origem r;
  3. todo vértice preto é término de um passeio que começa em r;
  4. todo arco com ponta inicial preta tem ponta final preta ou cinza;
  5. r é cinza ou preto.

Exercícios

  1. Aplique o algoritmo Busca-em-Profundidade ao exemplo discutido na página Busca em Largura
  2. Escreva uma versão de Busca-em-Profundidade para digrafos representados por uma matriz de adjacência.  Faça uma implementação apropriada das operações que correspondem à função Próximo (linha 7 do algoritmo).  (Sugestão: para cada linha da matriz, armazene o índice da "posição corrente" na linha.) 

Detalhes de implementação

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  (uCopia-Topo-da-Pilha(P))  é implementada por

  oooo uP[t]

A linha 11  (Coloca-na-Pilha(v,P))  é implementada por

  oooooooooo então  então  tt+1
  oooooooooo então  então  P[t] ← v

A linha 13  (Tira-da-Pilha(P))  é implementada por

  ooooooo então  tt−1

A sequência de vértices (P[1],…,P[t]) é um caminho.  Portanto, a pilha P[1..n] jamais sofre overflow.

Consumo de tempo

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,

  1. examina um arco (linhas 9-11)   ou
  2. pinta de preto um vértice originalmente cinza (linhas 12-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.

Exercícios

  1. Seja m a matriz de adjacência de um digrafo com vértices 1,…,n.  Escreva um algoritmo que faça uma busca em profundidade no digrafo todo. Escreva duas versões: uma iterativa e uma recursiva. Mostre que o consumo de tempo de qualquer das versões é Ο(n²).

Versão recursiva da busca em profundidade

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

Exercícios

  1. Faça uma análise do consumo de tempo da versão recursiva de Busca-em-Profundidade discutido na seção "Versão recursiva".  Faça uma análise precisa do consumo de tempo da rotina recursiva Busca-Profund-R

Busca em profundidade completa

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.)

Exercícios

  1. [CLR 23.3-8, CLRS 22.3-10] Suponha que um vértice w não é sorvedouro nem fonte. Mostre que é possível executar o algoritmo Busca-em-Profundidade-Completa de modo que no momento da execução da linha 5 com w no papel de r todos os vizinhos de w seja pretos.

Pós-ordem e pré-ordem

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] ← tt+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] ← tt+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.

Exercícios

  1. Escreva uma versão iterativa da rotina Busca-Pré-Pós-R
  2. Enumere os vértices do digrafo da figura 1 em pós-ordem.
  3. Quais das seguintes enumerações dos vértices da figura 1 estã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

  4. Escreva em pré-ordem os vértices do digrafo da figura 1.
  5. Enumere os vértices do digrafo da figura 2 em pós-ordem.
  6. Enumere em pós-ordem os vértices dos digrafos das figuras 12.

Figura 1:    a tree

Figura 2:    Copiado de http://webmathematics.net/


Valid HTML 4.01 Strict Valid CSS!