Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Algoritmos de busca

Este capítulo trata do seguinte problema básico:

Problema do Território:  Dado um vértice   r  de um grafo, determinar o território de  r.

Queremos um algoritmo que "marque", de alguma maneira, todos os vértices do território de r.   Eis um esboço de tal algoritmo:

1 2 3

marque r enquanto existe arco  (v,w)  com  v  marcado e  w  não marcado marque  w

No início de cada iteração, se um vértice v está marcado então existe caminho de r a v. No fim da última iteração, se um vértice w não está marcado então não existe caminho de r a w.  Portanto, quando o algoritmo pára, o conjunto dos vértices marcados é o território de r.

Qualquer algoritmo desse tipo é conhecido como algoritmo de busca (embora não esteja buscando nada específico); quem sabe algoritmo de varredura seria mais apropriado.

Exercícios

1. Escreva um trecho de código C que implemente, de maneira inocente e literal, o esboço de algoritmo de busca acima. Use a estrutura de dados do SGB. Para marcar vértices, use um utility field  marca:  um vértice  v  está marcado se  v–>marca  vale  1.  Por que essa implementação literal é ineficiente?  

2. O seguinte algoritmo deveria marcar todos os vértices do território do vértice  r.  O que há de errado?

   for (v = g–>vertices; v < g–>vertices+g–>n; v++) 
      v–>marca = 0;
   r–>marca = 1;
   for (v = g–>vertices; v < g–>vertices+g–>n; v++) 
      if (v–>marca == 1)  
         for (a = v–>arcs; a != NULL; a = a–>next)
            a–>tip–>marca = 1; 
   

Algoritmo genérico de busca

O esboço de algoritmo feito acima precisa ser detalhado antes que possa ser implementado de maneira eficiente. Para isso, é preciso introduzir os conceitos de vértice ativo e inativo.  Um vértice marcado é inativo se todos os arcos de seu leque de saída já foram examinados. Um vértice é ativo se já foi marcado.

Cada iteração de nosso algoritmo de busca começa com um conjunto de vértices marcados, alguns dos quais são ativos. Além disso, para cada vértice ativo v, temos o conjunto

A(v)

dos arcos que saem de v mas ainda não foram explorados. No início da primeira iteração, o vértice r é o único marcado e o único ativo; e A(v) é o leque de saída de v, para cada v. O processo iterativo consiste no seguinte:

1 2 3 4 5 6 7

enquanto existe vértice ativo faça escolha um vértice ativo  v  se A(v) não está vazio então retire um arco (v,w) de A(v) então se w não está marcado então então marque w e declare w ativo senão declare v inativo

Este é o algoritmo genérico de busca.  Ele é genérico porque tem a liberdade de escolher qualquer vértice ativo na linha 2 e tem a liberdade de escolher qualquer elemento (v,w) do conjunto A(v) na linha 4.

O conjunto de vértices ativos comanda o espetáculo. A maneira de administrar esse conjunto define a ordem em que vértices são visitados e dá origem a diferentes variantes do algoritmo genérico. Assim,

• se o conjunto de vértices ativos for administrado como uma fila, teremos uma busca "em largura" e
• se o conjunto de vértices ativos for administrado como uma pilha, teremos uma busca "em profundidade".

Há quem goste de acompanhar a execução do algoritmo colorindo os vértices: inicialmente, todos os vértices são brancos; quando um vértice é marcado ele se torna cinza (portanto, cinza é o mesmo que marcado e ativo); quando um vértice marcado deixa de ser ativo ele se torna preto (portanto, preto é o mesmo que marcado mas inativo).

Estrutura de dados e implementação

Como implementar o algoritmo genérico de busca na estrutura de dados do SGB?  Para marcar vértices, podemos usar um utility field  marca:  um vértice  v  está marcado se  v–>marca  vale  1.  A implementação do conjunto A(v) é simples:  basta associar a cada vértice  v  um ponteiro

arcocorrente

para o próximo arco, dentre os que saem de v, a ser examinado. O valor inicial de v–>arcocorrente será v–>arcs e  A(v)  será o conjunto de arcos

v–>arcocorrente,  v–>arcocorrente–>next,  v–>arcocorrente–>next–>next,  . . . , NULL.

O conjunto de vértices ativos pode ser representado por uma lista encadeada, digamos 

ativo,  ativo–>próximo,  ativo–>próximo–>próximo,  . . . , NULL,

onde próximo é um utility field. 

Predecessores em vez de marcas

Às vezes é muito útil usar ponteiros-para-vértices no lugar das marcas:  cada vértice encontrado durante a busca aponta para o seu predecessor, ou seja, para o vértice que o precedeu durante a busca.  Assim, o algoritmo calculará uma "arborescência" que "cobrirá" o território de  r .

O predecessor de cada vértice pode ser confortavelmente acomodado em um utility field, digamos  pred:  o predecessor de cada vértice w será 

w–>pred.

Podemos convencionar que  r–>pred == r  e que  x–>pred == NULL  para todo vértice  x  fora do território de r.  Assim, x é considerado marcado se e só se x–>pred != NULL.

Depois que os predecessores estiverem calculados, é fácil determinar um caminho de r a qualquer vértice w no território de r:  esse caminho é o inverso de

w,   w–>pred,   w–>pred–>pred,   w–>pred–>pred–>pred,   . . . ,   r.

A propósito, o SGB costuma escrever "backlink" no lugar de "pred"  (veja, por exemplo, a seção 14 do módulo GB_DIJK).

Exercícios

3. Escreva uma variante do algoritmo genérico de busca que defina predecessores em vez de marcas, como sugerimos acima.