Grafos com SGB | Índice de Termos

Algoritmos de busca em grafos

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

Problema do Território: Dado um vértice r de um grafo, encontrar 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:

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 parar, 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 a expressão algoritmo de varredura seria mais apropriada.

Exercícios 1

Algoritmo genérico de busca

Para que possamos implementar de maneira eficiente o esboço do algoritmo de busca exibido acima, é preciso introduzir algumas variáveis auxiliares. No começo de cada iteração do algoritmo, temos um certo conjunto de vértices marcados. Desses, alguns são considerados ativos enquanto os demais são considerados inativos. Se um vértice v está inativo então todos os seus vizinhos estão marcados. (Mas a recíproca não é verdadeira, pois podemos ter vértices ativos cujos vizinhos já estão todos marcados. Um tal vértice será declarado inativo tão logo o algoritmo constate essa condição.)

Para administrar o conjunto de vértices ativos, o algoritmo manterá, para cada vértice v, um certo subconjunto

A(v)

do leque de saída de v. Esse subconjunto tem a seguinte propriedade: se um arco (v, w) não está em A(v) então w está marcado. (Mas a recíproca não é verdadeira, pois w pode estar marcado mesmo que (v, w) ainda esteja em A(v).)

No início da primeira iteração, o vértice r é o único marcado e, para cada v, A(v) é o leque de saída de v. O algoritmo pode então ser apresentado assim:

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

O conjunto de vértices ativos comanda o espetáculo. A maneira de gerenciar 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.

O algoritmo é eficiente, pois examina cada arco do grafo no máximo uma vez durante o processo todo.

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 ativo); quando um vértice marcado deixa de ser ativo ele se torna preto (portanto, preto é o mesmo que inativo).

Estrutura de dados e implementação

Como implementar o algoritmo genérico de busca usando a estrutura de dados do SGB? Para marcar vértices, podemos usar um utility field marca: um vértice v está marcado se vmarca 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 do leque de saída de v a ser examinado. O valor inicial de varcocorrente será varcs e o valor inicial de A(v) será o conjunto de arcos

varcocorrente, varcocorrentenext, varcocorrentenextnext, … , NULL.

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

ativo, ativoprox, ativoproxprox, … , NULL,

onde prox é um utility field.

Predecessores no lugar de marcas

Às vezes é ú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 um vértice w será

wpred.

Podemos convencionar que rpred ≡ r e que xpred ≡ NULL para todo vértice x fora do território de r. Assim, x é considerado marcado se e só se xpred ≠ NULL.

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

w,  wpred,  wpredpred,  … ,  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 2