6 - BUSCA EM GRAFOS

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

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

Se um grafo direcionado G = (V,E) não contém nenhum ciclo, ele induz um conjunto parcialmente ordenado (V,<) tal que para todos vértices v e w, v < w se e somente se existe um caminho de v até w no grafo G. Não é difícil ver que os vértices de tal grafo podem ser ordenados para obter uma sequência de vértices v₁, v₂, ..., v_n , onde v_i < v_j, para i < j. Essa sequência é uma ordenação topológica.

Uma maneira simples de resolver esse problema é a utilização de uma versão do algoritmo de busca em profundidade que imprime o vértice antes de retornar da chamada. Obteremos assim os vértices em ordem topológica invertida:

Para verificar que esse algoritmo funciona, é só ver o que acontece quando chega ao final de uma recursão, no momento que ele imprime o vértice. Nesse caso, ele já foi o mais longe possível a partir do vértice inicial (isso é uma característica do algoritmo de busca em profundidade). Seja x o último vértice desse caminho. Não existe vértice v tal que x < v, porque se for o caso o algoritmo continuaria a busca no mínimo até v. Portanto, de todos os próximos vértices que serão imprimidos, nenhum sucede a v na ordem, e obteremos uma ordem topológica invertida.

Como exemplo, imagine um currículo de um curso de graduação onde os prerequisitos são expressos por um grafo, como ilustrado na figura 4.

Figura 4

Imaginemos agora uma pessoa que pode se matricular somente em um curso por semestre. Nesse caso, a ordenação topológica retorna a sequência de cursos que ela deverá fazer. É fácil verificar que um resultado possível do algoritmo é a sequência C5, C8, C6, C3, C4, C1, C7, C2. Invertendo essa sequência, obtemos a ordem topológica C2, C7, C1, C4, C3, C6, C8, C5. Note que o resultado depende que qual vértice é selecionado a cada chamada recursiva da busca.

Quanto ao tempo de execução desse algoritmo, é claro que é na mesma ordem que o algoritmo genérico de busca em profundidade.

Existe um outro algoritmo para obter diretamente uma ordenação topológica de um grafo direcionado. O princípio é o seguinte. Procuramos um vértice de grau de entrada 0, isto é, um vértice que não é o ponto de chegada de nenhuma aresta. Imprimimos esse vértice, retiramos do grafo e repetimos o processo até obtenção de um conjunto vazio de vértices. Eis o algoritmo:

Utilizando esse algoritmo com o grafo ilustrado na figura 4, podemos obter a seguinte sequência: C1, C2, C3, C4, C5, C6, C7, C8. Note que como a cada etapa do algoritmo pode existir mais de um vértice de grau de entrada nulo, a resposta do algoritmo pode ser diferente. Veja por exemplo essa outra sequência que ele poderia retornar: C1, C3, C5, C2, C7, C4, C6, C8.

E muito fácil mostrar que o algoritmo funciona corretamente, pois a cada etapa selecionamos um vértice que não tem nenhum predecessor, ou se ele tem, esse predecessor já foi processado anteriormente. Quanto ao tempo de execução, ele depende da maneira de implementar o grafo. O ponto crítico é a busca do vértice de grau de entrada nulo (a remoção pode ser realizada em tempo constante). Se for usada uma matriz de adjacência, o tempo para procurar um vértice de grau de entrada nulo é em O(n²). Como isso sera repetido n vezes, o tempo total é em O(n³). Se for usada uma estrutura de adjacência, a situação é melhor se o grafo é esparse, igual senão. A cada etapa o tempo para buscar o vértice de grau nulo é no mínimo n, pois todo elemento do vetor deve ser visitado para ver se ele foi eliminado. Além disso, será preciso visitar todas as arestas do grafo. Então teremos um tempo de execução em O(n+a) a cada iteração. No total, isso dá um tempo em O(n² + na).

Assim, o algoritmo aparece menos eficiente que o outro, que está em O(n+a) = O(max(n,a)). Mas é possível transformar o algoritmo de tal maneira que ele seja na mesma ordem. É só utilizar um vetor G[1..n] que memoriza o grau de entrada de cada vértice e uma lista L que contém todos os vértices de grau de entrada nulo. Eis uma versão em O(n+a) do algoritmo:

Identificação de componentes fortemente conexos

Um grafo direcionado é fortemente conexo se existe um caminho de u até v e de v até u para qualquer par distinto de vértices u e v. Se um grafo não é fortemente conexo, podemos estar interessados em saber quais são os seus subgrafos que são fortemente conexos. Cada um desses subgrafos é chamado componente fortemente conexo.

Figura 5

Considere o grafo ilustrado na figura 5. Podemos ver que ele contém três componentes fortemente conexos: {1,2,3,4}, {6}, {5,8,9,10} e {7,11}. Existe uma maneira interessante de visualizar o grafo se consideramos cada componente como um vértice. Isso é uma representação de como ir de um componente a outro componente. Veja na figura 6 essa representação do grafo da figura 5.

Figura 6

Para identificar os componentes fortemente conexos de um grafo, é preciso primeiro modificar a busca em profundidade, para obter uma numerotação pós-ordem dos nodos da árvore que resulta da busca. Para isso, é so incrementar um contador no momento da saída de uma chamada recursiva. Supondo uma variável global posnum[1..n], eis o algoritmo modificado:

Agora, podemos apresentar o algoritmo que identifica os componentes fortemente conexos de um grafo G:

1. Realizar uma busca em profundidade em G. Consideramos que depois dessa busca, cada valor posnum[v] representa a posição do vértice v na sequência resultando de percurso pós-ordem.
2. Construir um grafo G' que é igual a G, só que a orientação de cada aresta é invertida.
3. Realizar uma busca em profundidade em G', começando com o vértice que tem o maior valor em posnum. Recomeçar o processo com os vértices não visitados se essa buscas não visitou todos. Assim por diante até que todos os vértices sejam visitados.
4. Cada árvore da floresta que resulta da etapa precedente contém todos os vértices de um componente fortemente conexo de G.

Vamos ver agora a aplicação desse algoritmo ao exemplo da figura 5. Suponhamos que a busca em profundidade corresponde à árvore ilustrada na figura 7. A figura 8 ilustra o grafo G'. Ao lado de cada vértice é indicado um valor que representa a posição desse vértice no percurso pós-ordem da árvore obtida na busca em G.

Figura 7

Figura 8

Realizando a busca em profundidade no grafo G' ilustrado na figura 8, obtemos as árvores ilustradas na figura 9. Isso corresponde ao resultado esperado.

Figura 9

Para se convencer que o algoritmo funciona, devemos provar o seguinte:

Prova da ida: Suponhamos que u e v são no mesmo componente fortemente conexo. Isso implica que existe um caminho de u até v e vice versa. Se isso vale para G, vale para G' também. Na busca efetuada em G', um dos dois vértices u e v será visitado primeiro. Supondo u esse vértice. Como existe um caminho de u até v, necessessariamente esse último será na mesma árvore, considerando que a busca em profundidade visita de maneira exaustiva todos os vertices alcançáveis a partir do vértice inicial.

Prova da volta: Seja v um vértice em uma árvore cuja raiz é r quando realizamos a busca em G', e suponhamos v r. Isso implica que existe um caminho de r até v no grafo G', e portanto de v até r no grafo G. Como r foi selecionado primeiro, sabemos que posnum[r] > posnum[v]. Consideremos agora as posições possíveis de r relativamente a v na árvore que corresponde à busca em profundidade realizada em G. Há três possibilidades:

1. r é ancestral de v.
2. r é descendente de v.
3. r não é nem ancestral nem descendente de v.

Consideremos o segundo caso. Se r é descendente de v, ele deveria ter o valor menor na ordenação pós-ordem. Já sabemos que isso não é o caso, pois posnum[r] > posnum[v]. Portanto, o segundo caso é excluido.

Suponhamos agora a terceira possibilidade. Como posnum[r] > posnum[v], o vértice r foi visitado depois de v e está à direita de v na árvore. O caminho de v até r não pode ser como ilustrado na figura 9'a, onde não existe um vértice que é ancestral dos dois. Se tivesse tal caminho, r seria descendente de v na árvore de busca. Portanto, o caminho de v até r deve subir na árvore até um vértice x que é ancestral de v e r, como ilustrado na figura 9'b. Isso supõe um vértice x tal que posnum[x] > posnum[r], o que é impossível. Isso porque não é possível que r seja selecionado antes de x para lançar a busca. Assim, r e v já seriam absorvidos na árvore de x e r não pode ser a raiz de v. Portanto, sobra somente a primeira possibilidade, que implica que existe um caminho de r até v.

Figura 9'

Em uma busca em largura a partir de um vértice v, esperamos que todos os vizinhos de v sejam visitados antes de continuar a busca mais profundamente. Contrariamente à busca em profundidade, o algoritmo de busca em largura não é recursivo. Mas pode ser comparado à versão iterativa da busca em profundidade, que usa uma pilha P:

O algoritmo de busca em largura é semelhante ao algoritmo de busca em profundida. A principal diferença é que usamos um fila F ao invés de uma filha:

Nos dois casos é preciso um programa para lançar a busca:

Aplicando o algoritmo de busca em largura ao grafo da figura 2, poderiamos obter a árvore geradora ilustrada na figura 10:

Figura 10

É muito fácil ver que o tempo de execução da busca em largura é o mesmo que o tempo de execução da busca em profundidade: O(n+a), ou O(max(n,a)). Mas se consideramos a memória, o desempenho é pior. Na busca em profundidade, somente um "ramo" da árvore é empilhada em qualquer momento. Então a pilha não conterá mais de n elementos. Na busca em largura, como todos os filhos de um nodo sãm empilhado a cada etapa, o espaço ocupado em memória tende a ser exponencial.

Um exemplo de aplicação da busca em largura é a identificação do caminho mais curto entre dois vértice. Nesse caso, o desempenho do algoritmo é melhor que os algoritmos de Dijkstra e Floyd. Outra situação onde a busca em largura pode ser usada é quando temos um grafo infinito. Nesse caso, a busca em profundidade pode entrar em um ramo sem saída.

Grafos implícitos e retrocesso cronológico

Por enquanto, vamos esquecer esse assunto...

Exercícios

Exercício 6-1: Discuta o tempo de execução do algoritmo de busca em profundidade se utilizamos uma matriz de adjacência ao invés de uma estrutura de adjacência.

Exercício 6-2: Utilize o algoritmo de busca em profundidade para identificar o componentes de um grafo não direcionado.

Exercício 6-3: Escreva uma versão iterativa do algoritmo de busca em profundidade.

Exercício 6-4: Escreva em detalhe o algoritmo de busca de articulação.

Exercício 6-5: Prove que, em um grafo G conexeo, uma aresta que não aparece numa árvore de profundidade necessariamente liga um vértice com um dos seus ancestrais na árvore.

Exercício 6-6: Prove que um vértice v em um grafo conexo é uma articulação se e somente se existe dois vértices a e b diferentes de v tais que todo caminho entre a e b passa por v.

Exercício 6-7: Prove que, em um grafo G direcionado, se (v,w) é uma aresta que não aparece na floresta resultante de uma busca em profundidade, e se v não é nem ancestral nem descendente de w, então prenum[v] > prenum[w].

Exercício 6-8: Mostre como a remoção de um vértice de grau de entrada nulo pode ser implementado em tempo constante no algoritmo Orden-Topo-Alt. Responda para os dois casos: utilização de estrutura de adjacência e utilização de matriz de adjacência.

Exercício 6-9: Mostre que o algoritmo Orden-Topo-Alt-Modif apresenta um tempo de execução em O(a+n).

Exercício 6-10: Qual é o tempo de execução do algoritmo para identifação de componentes fortemente conexos?

Figura 11

Exercício 6-11: Considere os grafos da figura 11. Qual é a ordem de visita dos vértices em uma busca em profundidade, começando pelo vértice a. Responda à mesma pergunta com os outros vértices.

Exercício 6-12: Considere os grafos da figura 11. Qual é a ordem de visita dos vértices em uma busca em largura, começando pelo vértice a. Responda à mesma pergunta com os outros vértices.

Exercício 6-13: Aplique o algoritmo de identificação de componentes fortemente conexos no grafo 11b.

Figura 12

Exercício 6-14: Aplique o algoritmo de identificação de articulações nos grafos da figura 12.

Exercício 6-15: Escreva um algoritmo em O(n) para determinar se um grafo não direcionado de n vértices contém circuitos.

Exercício 6-16: Escreva um algoritmo para determinar se é possível colorir todos os vértices de um grafo, usando somente duas cores e de tal maneira que nenhum vértice tenha a mesma cor que qualquer de seus vértices adjacentes.