6 - BUSCA EM GRAFOS

Última revisão: 9/6/2001

Conteúdo

Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. Às vezes é preciso visitar todos os vértices de um grafos, as vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices. Consideremos por exemplo o problema do caminho mais curto. Os algoritmos apresentados para resolver esse problema fazem um percurso exaustivo de todos os vértices. Não precisa ser assim se, por exemplo, queremos o caminho mais curto até um vértice em particular. Nesse caso, assim que ele se encontra no conjunto dos vértices já visitado, não é preciso continuar o algoritmo.

Basicamente, existem duas técnica de busca em grafos: a busca em profundidade (depth-first search) e a busca em largura (breadth-first search).

Busca em profundidade

Vamos ver agora o algoritmo e algumas aplicações.

Descrição do algoritmo

Note que esse algoritmo funciona com um grafo desconexo. Se já sabemos que o grafo é conexo, podemos chamar diretamente a função Busca-Prof, escolhendo arbitrariamento um vértice inicial.

Para implementar esse algoritmo, é a estrutura de adjacência que aparece como candidata ideal. Isso porque a principal operação efetuada pelo algoritmo é a escolha de um vértice adjacente e já sabemos que nesse caso a estrutura de adjacência é a melhor opção. Supondo então que a estrutura de adjacência é utilizada para implementar a busca, podemos ver que o tempo de execução do algoritmo é em O(max(a,n)), onde a e n representam o número de arestas e de vértices, respectivamente. Como cada vértice deve ser visitado, o algoritmo necessariamente fará n chamadas do procedimento Busca-Prof, muitas delas recursivas. Em cada chamada, todos os vértices adjacentes serão testados. No total, o número de testes realizados será igual ao número de arestas. Então o tempo total gasto para as chamadas a Busca-Prof é em O(a). A esse tempo devemos acrescentar o tempo gasto no procedimento Busca: o tempo de inicialização, e o tempos para testar, para cada vértice, se ele foi marcado. No total isso dá um tempo em O(2n) = O(n). Portanto, a busca em profundidade tem um tempo de execução em O(a+n). Na verdade temos um tempos em O(max(a,n)): se o grafo tem mais arestas que vértices temos um tempo em O(a). No caso contrário, temos um tempos em O(n).

Considere agora o grafo ilustrado na figura 1a e a estrutura de adjacência ilustrada na figuras 1b que representa esse grafo.

Figura 1

Eis o traço de execuão do algoritmo com esse exemplo:

Quando o algoritmo chega ao vértice 5, não há nenhum vizinho dele que não foi visitado. Ele retorna dessa chamada para continuar a busca a partir do vértice anterior que é o vértice 4. A busca continua com o próximo vizinho de 4 que não foi visitado: o vértice 3. Como o vértice 3 não tem vizinhos que não foram visitados, o algoritmo retorna imediatamente ao vértice 4, para continuar a busca com o vértice 6, e assim por diante chegamos ao último vértice visitado que é vértice 8.

Note que à busca em profundidade corresponde uma árvore geradora. No exemplo da figura 1, obtemos a árvore geradoa ilustrada na figura 2:

Figura 2

Vamos ver agora aplicações da busca em profundidade.

Busca de articulação

Um vértice em um grafo não direcionado simples e conexo é uma articulação se sua remoção torna o grafo resultante desconexo. A identificaço de articulação pode ser importante em redes de computadores para identificar os pontos frágeis de uma rede. O algoritmo de busca em profundidade pode ser usada para identificar uma articulação. No grafo da figura 1a, o vértice 4 é uma articulação. Um grafo é dito biconexo se ele não contém nenhuma articulação.

Vamos agora explicar essencialmente os princípios do algoritmo para procurar as articulações de um grafo.

Primeiro, supomos que foi realizada uma uma busca em profundidade para obter uma árvore geradora. Essa árvore obtida será examinada para determinar a existência de articulação. Vamos ver o que podemos deduzir a partir de cada nodo n dessa árvore:

1. n é a raiz: Se n tem somente um filho, isso significa que qualquer vértice pode ser alcançado a partir desse filho. Então, tirando n do grafo não tornaria ele desconexo. Portanto, nesse caso, esse vértice não é uma articulação. Se n tem mais de um filho, isso significa que não podemos alcançar todos os vértices a partir de qualquer um dos filhos (senão o algoritmo não teria volta à raiz para recomeçar a busca com outros vizinhos). Nesse caso, obrigatoriamente devemos passar por n para ir de qualquer nodo de uma subárvore até um nodo de uma outra subárvore. Portanto, retirar n deixaria o grafo desconexo.
   
2. n é uma folha: Todo vértice que é uma folha da árvore não é uma articulação. Isso porque já sabemos que a remoção de um vértice pendente em uma árvore não a deixa desconexo.
   
3. n é um nodo interno: Retirando esse nodo, o grafo fica conexo somente se existe, para cada um das subárvores de n, uma ligação entre ele e um nodo ancestral de n.

Agora que entendemos o princípio do algoritmo, podemos explicá-lo em detalhes. Primeiro, é preciso modificar o algoritmo de busca em profundidade para que ele retorne um vetor prenum[1..n] que indica, para cada vértice do grafo, a sua ordem no percurso. Eis a versão que precisamos, supondo que prenum é uma variável global.

1. Realizar uma busca em profundidade, começando por qualquer vértice, onde para cada vértice atribuimos um número indicando sua posição na sequência de visitas. Seja T a árvore obtida e prenum[1..n] o vetor que indica para cada vértice a sua ordem na busca.
2. Agora, para cada nodo, vamos identificar um valor que corresponde à ordem do primeiro vértice visitado com o qual ele está ligado (seja diretamente por uma aresta ou seguindo um caminho na subárvore que ele domina). Para identificar esses valores, realizamos um percurso em pós-ordem da árvore T. Para cada vértice v, calculamos menor[v], que representa o mínimo entre:
   1. prenum[v]
   2. prenum[w] para cada w tal que existe uma aresta (v,w) em G que não aparece em T.
   3. menor[x] para cada filho x de v em T.
3. Agora, as articulações podem ser facilemente identificadas da seguinte maneira:
   1. A raíz de T é uma articulação se e somente se ela tem mais de um filho.
   2. Um vértice v que não é a raíz é uma articulação se e somente se v tem um filho x tal que menor[x] prenum[v]

A figura 3 ilustra a aplicação desse algoritmo com o grafo da figura 1a. Está representada a árvore geradora produzida pela busca em profundidade com, escrito em azul do lado esquerda, o ordem de visita de cada vértices. Em linha quebrada são representadas as arestas que ficam fora da árvore. Em vermelho do lado direita são indicados os valores menor[v] para cada vértice v. Podemos conferir que somente dois nodos têm um filho cujo valor menor[v] é maior ou igual à sua ordem na busca: os vértices 4 e 6 que, como podemos verificar, são as únicas articulações do grafo.

Figura 3

Vamos ver agora como o algoritmo de busca em profundidade pode ser utilizado para resolver problemas representados com grafos direcionados. Nesses casos, o algoritmo é o mesmo. Só temos que tomar cuidado com a seleção dos vértices adjacente. Num grafo direcionado, um vértice w e adjacente a um vértice v se existe uma aresta que sai de v e chega em w. Duas aplicações são apresentadas nas próximas seções.