Análise de Algoritmos | Aulas | Dicionário | Índice

Busca em profundidade

Esta página descreve o algoritmo de busca em profundidade (= depth-first search = DFS). O algoritmo visita todos os vértices de um digrafo numa determinada ordem, que chamaremos pré-ordem ou ordem DFS. Essa ordem dos vértices ajuda entender a estrutura do digrafo e é muito útil, por exemplo, para encontrar os ciclos e as componentes fortes do digrafo.

Esta página é inspirada na seção 3 do capítulo 22 do CLRS.

Algoritmo de busca em profundidade

O algoritmo de busca em profundidade varre (= scans) um digrafo e visita todos seus vértices e todos seus arcos. À medida que varre o digrafo, o algoritmo pinta cada vértice de cinza e depois de preto. Quando descobre um novo vértice, o algoritmo pinta o vértice de cinza; quando termina de visitar todos os vizinhos do vértice, o algoritmo pinta o vértice de preto. Os vértices cinza são considerados ativos e os pretos são considerados mortos.

É mais simples escrever o código do algoritmo em estilo recursivo. Como não é possível varrer o digrafo todo de uma só vez, a camada externa do algoritmo é um driver que invoca várias vezes o algoritmo recursivo propriamente dito. Cada invocação é uma etapa da busca.

O algoritmo recebe um digrafo G representado por um vetor Adj de listas de adjacência.

A rotina recursiva DFS-r (o sufixo r é a inicial de recursivo) tem acesso a um vetor cor que atribui um rótulo branco, cinza ou preto a cada vértice do digrafo. A rotina recebe um vértice branco r e

determina o conjunto, digamos X, de todos os vértices que pertencem a caminhos que começam em v e só usam vértices brancos.

Antes de parar, a rotina altera o vetor cor de modo que todos os vértices em X fiquem pretos.

(Os vetores Adj e cor são tratados como variáveis globais.) Na linha 9, a rotina DFS-r é aplicada ao digrafo original G. Isso pode criar a impressão de que a instância do problema que a rotina deve resolver na linha 9 tem o mesmo tamanho da instância original. Com isso, pode parecer que a recursão nunca termina (isto é, que a rotina entra em loop). Ocorre que o tamanho de uma instância não é medido pelo tamanho do digrafo mas pelo número de vértices brancos. Como um vértice cinza ou preto jamais fica branco, o tamanho de uma instância nunca aumenta. Além disso, v é branco quando DFS-r (G,&8201;v) é invocada e logo fica cinza. Assim, o tamanho da nova instância na linha 9 é menor que o tamanho da instância original. Isso garante que a recursão é finita.

Ao final da execução do algoritmo Busca-em-Profundidade, todos os vértices do digrafo estarão pretos.

Desempenho

Qual o consumo de tempo de Busca-em-Profundidade? É fácil constatar que o consumo de tempo de todas as execuções de todas as linhas exceto a linha 5 é Ο(n), sendo n o número de vértices de G. Agora considere a linha 5, que invoca a rotina DFS-r. O consumo de tempo dessa rotina, como o de qualquer algoritmo recursivo, pode ser descrito por uma recorrência. Infelizmente, a recorrência é um tanto complexa. Vamos estimar então, de uma só vez e de maneira um tanto informal, o tempo total de todas as execuções de DFS-r.

Para cada vértice v, a rotina DFS-r é invocada apenas uma vez com argumento v. (De fato, v é branco antes da chamada e torna-se cinza logo em seguida.) A execução da rotina com argumento v examina, diretamente, todos os arcos que saem de v e apenas esses. (O exame dos outros arcos acontece nas invocações de DFS-r na linha 9.) Portanto, na união de todas as execuções de DFS-r, cada arco do digrafo é examinado uma única uma vez. Como o exame de cada arco consome uma quantidade de tempo que não depende do tamanho do digrafo, o tempo total gasto nas execuções de DFS-r é Ο(m), sendo m o número de arcos do digrafo.

Concluímos assim que o algoritmo Busca-em-Profundidade consome

Ο(n + m)

unidades de tempo. Como n + m é o tamanho do digrafo, o algoritmo é linear.

Floresta da busca DFS

Cada vez que um novo vértice w é descoberto durante a busca DFS, é útil anotar o vértice v a partir do qual w foi descoberto. Para isso, basta usar um vetor de vértices, digamos pai, indexado pelos vértices e fazer pai[w] := v. Diremos que pai é um vetor de pais (= parent array = array of predecessors) da busca.

Eis a versão apropriada de DFS-r:

O sub­digrafo de G formado por todos os arcos vw tais que v = pai[w] é uma floresta radicada. Diremos que essa é a floresta DFS da busca. Os vértices r nas várias execuções da linha 5 (onde começa cada nova etapa da busca) são as raízes da floresta. A floresta DFS é um sub­digrafo gerador do digrafo G.

  0      2 
 / \     | 
1   4    3 
     \     
      5    

Arcos de avanço, de retorno, e cruzados.  Suponha que F é uma floresta DFS de um digrafo G. Em relação a F, cada arco vw de G é de um dos seguintes tipos:

1. de floresta, se vw pertence a F;
2. de avanço (= forward), se v é ancestral de w em F mas não pai de w;
3. de retorno (= back), se v é descendente de w em F;
4. cruzado (= cross), se v é não é ancestral nem descendente de w.

Essa classificação dos arcos é importante para entender o digrafo. Ela é usada por muitos algoritmos para diversos problemas.

Pós-ordem e pré-ordem

No início desta página referimo-nos vagamente à permutação em pré-ordem dos vértices do digrafo. Esta seção define o conceito de maneira mais precisa.

A permutação dos vértices em pré-ordem (= pre-order) é definida pela ordem em que os vértices ficam cinzentos durante uma busca em profundidade. A permutação em pós-ordem (= post-order) é definida pela ordem em que os vértices ficam pretos. É claro que essas permutações dependem da ordem em que os vértices são examinados na linha 3 de Busca-em-Profundidade e na linha 7 de DFS-r.

O seguinte algoritmo faz uma busca em profundidade num digrafo e atribui dois números (= timestamps a cada vértice w:  o número pré[w] é o momento em que o vértice fica cinza (ou seja, o momento em que é descoberto) e o número pós[w] é o momento em que o vértice fica preto (ou seja, o momento em que morre). O algoritmo usa uma variável t como cronômetro:

Eis a versão apropriada de DFS-r:

Observe que pre[v] < pós[v] para cada vértice v. O vértice está ativo, ou vivo, durante o intervalo (pré[v], pós[v]). Ao final intervalo, v morre. Qualquer outro vértice que seja descoberto durante o intervalo certamente morre antes do fim do intervalo. Portanto, os intervalos de todos os vértices são encaixados.

A ordem crescente dos números pré dá a permutação dos vértices em pré-ordem. (Ou seja, a permutação (v₁, v₂, … , v_n) dos vértices está em pré-ordem se pré[v₁] < pré[v₂] < ⋯ <6 pré[v_n].) Da mesma forma, a ordem crescente dos números pós dá a permutação dos vértices em pós-ordem.

    0          2   
   0/7        8/11 
  /   \        |   
 1     4       3   
1/2   3/6     9/10 
         \         
          5        
         4/5       

Os vetores pré e pós permitem decidir facilmente se um dado arco é de avanço, de retorno, ou cruzado. Como os intervalos de vida dos vértices são encaixados, um arco vw é

• de avanço se e somente se pré[v] < pré[w] < pós[w] < pós[v],
• de retorno se e somente se pré[w] < pré[v] < pós[v] < pós[w],
• cruzado se e somente se pré[w] < pós[w] < pré[v] < pós[v].

(Em outras palavras, vw é de avanço se o intervalo de v contém o intervalo de w, de retorno se o intervalo de v está contido no intervalo de w, e cruzado se o intervalo de v é disjunto do intervalo de w e anterior a ele.) Isso pode ser resumido assim: um arco vw é

• de avanço se e somente se pré[v] < pré[w] e pós[v] > pós[w],
• de retorno se e somente se pré[v] < pré[w] e pós[v] < pós[w],
• cruzado se e somente se pré[v] > pré[w] e pós[v] > pós[w].