Busca em Largura BFS em Grafos Algoritmo e Complexidade

53 Buscas em Grafos 531 Busca em Largura Dado um grafo G V E e uma origem s a busca em largura BreadthFirst Search BFS explora as arestasarcos de G a partir de s para cada vértice que pode ser atingido a partir de s É uma exploração por nível O procedimento descobre as distâncias número de arestasarcos entre s e os demais vértices atingíveis de G Pode ser aplicado para grafos orientados e nãoorientados CORMEN et al 2012 O algoritmo pode produzir uma árvore de busca em largur com raiz s Nesta árvore o caminho de s até qualquer outro vértice é um caminho mínimo em número de arestasarcos CORMEN et al 2012 O Algoritmo 19 descreve as operações realizadas em uma busca em largura Nele criamse três estruturas de dados que serão utilizadas para armazenar os resultados da busca O arranjo Cv é utilizado para determinar se um vértice v V foi visitado ou não Dv determina a distância percorrida até encontrar o vértice v V e Av determina o vértice antecessor ao v V em uma busca em largura a partir de s CORMEN et al 2012 5311 Complexidade da Busca em Largura O número de operações de enfileiramento e desenfileiramento é limitado a V vezes pois visitase no máximo V vértices Como as operações de enfileirar e desenfileirar podem ser realizadas em tempo Θ1 então para realizar estas operações demandase tempo de OV Devese considerar ainda que muitas arestasarcos incidem em vértices já visitados então incluise na complexidade de uma BFS a varredura de todas as adjacências que demandaria ΘE Dizse então que a complexidade computacional da BFS é OV E Algoritmo 19 Busca em largura Input um grafo G V E vértice de origem s V configurando todos os vértices 1 Cv false v V 2 Dv v V 3 Av null v V configurando o vértice de origem 4 Cs true 5 Ds 0 preparando fila de visitas 6 Q Fila 7 Qenqueues propagação das visitas 8 while Qempty false do 9 u Qdequeue 10 foreach v Nu do 11 if Cv false then 12 Cv true 13 Dv Du 1 14 Av u 15 Qenqueuev 16 return D A 5312 Propriedades e Provas Caminhos Mínimos A busca em largura garante a descoberta dos caminhos mínimos em um grafo nãoponderados G V E de um vértice de origem s V para todos os demais atingíveis Para demonstrar isso Cormen et al 2012 examina algumas propriedades importantes a seguir Considere a distância de um caminho mínimo δs v de s a v como o número mínimo de arestasarcos necessários para percorrer esse caminho Lema 531 Seja G V E um grafo orientado ou nãoorientado e seja s V um vértice arbitrário então δs v δs u 1 para qualquer arestaarco u v E Prova Se u pode ser atingido a partir de s então o mesmo ocorre com v Desse modo o caminho mínimo de s para v não pode ser mais longo do que o caminho de s para u seguido pela arestaarco u v e a desigualdade vale Se u não pode ser alcançado por s então δs u e a desigualdade é válida Lema 532 Seja G V E um grafo orientado ou nãoorientado e suponha que G tenha sido submetido ao algoritmo BFS Algoritmo 19 partindo de um dado vértice de origem s V Ao parar o algoritmo BFS satisfará Dv δs v v V Prova Utilizase a indução em relação ao número de operações de enfileiramento enqueue A hipótese indutiva é Dv δs v v V A base da indução é a situação imediatamente após s ser enfileirado na linha 7 do Algoritmo 19 A hipótese indutiva se mantém válida nesse momento porque Ds 0 δs s e Dv δs v v V s Para o passo da indução considere um vértice v nãovisitado Cv false que é descoberto depois do último desempinhamento Consideramos que o vértice desempunhado é u V A hipótese da indução implica que Du δs u Pela atribuição da linha 13 e pelo Lema 531 obtemse Dv Du 1 δs u 1 δs v 58 Então o vértice v é enfileirado e nunca será enfileirado novamente porque ele também é marcado como visitado e as operações entre as linhas 12 e 15 são apenas executadas para vértices nãovisitados Desse modo o valor de Dv nunca muda novamente e a hipótese de indução é mantida Lema 533 Suponha que durante a execução do algoritmo de busca em largura Algoritmo 19 em um grafo G V E a fila Q contenha os vértices v1 v2 vr onde v1 é o início da fila e vr é o final da fila Então Dvr Dv1 1 e Dvi Dvi1 para todo i 1 2 r 1 Prova A prova é realizada por indução relacionada ao número de operações de fila Para a base da indução imediatamente antes do laço de repetição antes da linha 8 têmse apenas o vértice s na fila O lema se mantém nessa condição Para o passo da indução devese provar que o lema se mantém para depois do desenfileiramento quanto do enfileiramento de um vértice Se o início v1 é desenfileirado Lema 532 Seja G V E um grafo orientado ou nãoorientado e suponha que G tenha sido submetido ao algoritmo BFS Algoritmo 19 partindo de um dado vértice de origem s V Ao parar o algoritmo BFS satisfará Dv δs v v V Prova Utilizase a indução em relação ao número de operações de enfileiramento enqueue A hipótese indutiva é Dv δs v v V A base da indução é a situação imediatamente após s ser enfileirado na linha 7 do Algoritmo 19 A hipótese indutiva se mantém válida nesse momento porque Ds 0 δs s e Dv δs v v V s Para o passo da indução considere um vértice v nãovisitado Cv false que é descoberto depois do último desempinhamento Consideramos que o vértice desempunhado é u V A hipótese da indução implica que Du δs u Pela atribuição da linha 13 e pelo Lema 531 obtemse Dv Du 1 δs u 1 δs v 58 Então o vértice v é enfileirado e nunca será enfileirado novamente porque ele também é marcado como visitado e as operações entre as linhas 12 e 15 são apenas executadas para vértices nãovisitados Desse modo o valor de Dv nunca muda novamente e a hipótese de indução é mantida Lema 533 Suponha que durante a execução do algoritmo de busca em largura Algoritmo 19 em um grafo G V E a fila Q contenha os vértices v1 v2 vr onde v1 é o início da fila e vr é o final da fila Então Dvr Dv1 1 e Dvi Dvi1 para todo i 1 2 r 1 Prova A prova é realizada por indução relacionada ao número de operações de fila Para a base da indução imediatamente antes do laço de repetição antes da linha 8 têmse apenas o vértice s na fila O lema se mantém nessa condição Para o passo da indução devese provar que o lema se mantém para depois do desenfileiramento quanto do enfileiramento de um vértice Se o início v1 é desenfileirado Considere o momento que o algoritmo opta por desenfileirar o vértice 𝑢 de 𝑄 Nesse momento o vértice 𝑣 pode ter sido nãovisitado visitado e está na fila ou visitado e já foi removido da fila O restante da prova trabalha em cada um desses casos Se 𝑣 é nãovisitado 𝐶𝑣 false então a operação na linha 13 define 𝐷𝑣 𝐷𝑢 1 contradizendo o que é dito na Equação 59 Se 𝑣 já foi visitado 𝐶𝑣 true e foi removido da fila pelo Corolário 534 têmse 𝐷𝑣 𝐷𝑢 que também contradiz o que é dito na Equação 59 Se 𝑣 já foi visitado e permanece na fila quando 𝑣 fora enfileirado 𝑤 era o vértice antecessor imediato no caminho até 𝑣 logo 𝐷𝑣 𝐷𝑤 1 Considere também que 𝑤 já foi desenfileirado Porém pelo Corolário 534 𝐷𝑤 𝐷𝑢 então temos 𝐷𝑣 𝐷𝑤 1 𝐷𝑢 1 contradizendo a Equação 59 Árvores em Largura O algoritmo de busca em largura Algoritmo 19 criar uma árvore de busca em largura à medida que efetua busca no grafo 𝐺 𝑉𝐸 Também chamada de subgrafo dos predecessores uma árvore de busca em lagura pode ser definida como 𝐺𝜋 𝑉𝜋𝐸𝜋 na qual 𝑉𝜋 𝑣 𝑉 𝐴𝑣 null 𝑠 e 𝐸𝜋 𝐴𝑣𝜋 𝑣 𝑣 𝑉𝜋 𝑠 4 532 Busca em Profundidade A busca em profundidade DepthFirst Search DFS realiza a visita a vértices cada vez mais profundosdistantes de um vértice de origem 𝑠 até que todos os vértices sejam visitados Partese a busca do vértice mais recentemente descoberto do qual ainda saem arestas inexploradas Depois que todas as arestas foram visitadas no mesmo caminho a busca retorna pelo mesmo caminho para passar por arestas inexploradas Quando não houver mais arestas inexploradas a busca em profundidade pára CORMEN et al 2012 5 O Algoritmo 20 apresenta um pseudocódigo para a busca em profundidade Note que no lugar de usar uma fila como na busca em largura vide Algoritmo 19 utilizase uma pilha Os arranjos 𝐶𝑣 𝑇𝑣 e 𝐴𝑣 𝑣 𝑉 são respectivamente o arranjo de marcação de visitados do tempo de visita e do vértice antecessor à visita Algoritmo 20 Busca em profundidade Input um grafo 𝐺 𝑉 𝐸 vértice de origem 𝑠 𝑉 configurando todos os vértices 1 𝐶𝑣 false 𝑣 𝑉 2 𝑇𝑣 𝑣 𝑉 3 𝐴𝑣 null 𝑣 𝑉 configurando o vértice de origem 4 𝐶𝑠 true 5 tempo 0 preparando fila de visitas 6 𝑆 Pilha 7 Spush𝑠 propagação das visitas 8 while Sempty false do 9 tempo tempo 1 10 𝑢 Spop 11 𝑇𝑢 tempo 12 foreach 𝑣 N𝑢 do 13 if 𝐶𝑣 false then 14 𝐶𝑣 true 15 𝐴𝑣 𝑢 16 Spush𝑣 17 return 𝐶𝑇 𝐴 Cormen et al 2012 afirma que é mais comum realizar a busca em profundidade de várias fontes Desse modo seu livro reporta um algoritmo que sempre que um subgrafo conexo é completamente buscado partese de um outro vértice de origem nãovisitado ainda um vértice não atingível por 𝑠 5321 Complexidade da Busca em Profundidade Da mesma maneira que a complexidade da busca em largura a busca em profundidade possui complexidade 𝑂𝑉 𝐸 As operações da pilha resultariam tempo 𝑂𝑉 Muitos arestasarcos incidem em vértices já visitados então incluise na complexidade de uma DFS a varredura de todas as adjacências que demandaria ΘE 533 Aplicações de Buscas em Profundidade 5331 Componentes Fortemente Conexas Um grafo conexo é aquele no qual há um caminho entre todos os pares de vértices É dita uma componente fortemente conexa de um grafo dirigido nãoponderado G V A é um conjunto máximo de vértices C V tal que para todo o par de vértices u v em C têmse u v e v u Um algoritmo para identificar as Componentes Fortemente Conexas é relatado por Cormen et al 2012 e apresentado aqui no Algoritmo 21 Nele utilizase duas vezes a busca em profundidade sugerida também por Cormen et al 2012 Algoritmos 22 DFS e 23 DFSVisit Primeiramente fazse a busca em largura para descobrir os caminhos de todos os vértices para todos os outros Depois percorrese os mesmos caminhos em um grafo transposto GT As árvores representadas como os antecessores em AT trarão a resposta cada árvore é uma componente fortemente conexa Algoritmo 21 Algoritmo de ComponentesFortementeConexas Input um grafo dirigido não ponderado G V A Chamar a DFS do Algoritmo 22 para computar os tempos de término para cada vértice 1 C T A F DFSG Criar grafo transposto de G chamado de GT 2 AT 3 foreach u v A do 4 AT AT v u Invertese todos os arcos para GT 5 GT V AT Chamar a DFS do Algoritmo 22 alterado para que ele execute o laço da linha 6 selecionando vértices em ordem decrescente de F 6 CT TT AT FT DFSadaptadoGT dar saída de cada árvore na floresta em profundidade em AT como uma componente fortemente conexa 7 return AT Algoritmo 22 DFS de Cormen et al 2012 Input um grafo dirigido não ponderado G V E Configurando todos os vértices 1 Cv false v V 2 Tv v V 3 Fv v V 4 Av null v V configurando o tempo de início 5 tempo 0 6 foreach u V do 7 if Cu false then DFSVisit é especificado no Algoritmo 23 8 DFSVisitG u C T A F tempo 9 return C T A F Algoritmo 23 DFSVisit de Cormen et al 2012 Input um grafo G V E vértice de origem v V e os vetores C T A e F e uma variável tempo ℤ 1 Cv true 2 tempo tempo 1 3 Tv tempo 4 foreach u Nv do 5 if Cu false then 6 Au v 7 DFSVisitG u C T A F tempo 8 tempo tempo 1 9 Fv tempo Complexidade do Algoritmo de Componentes Fortemente Conexas A complexidade de tempo computacional do Algoritmo 21 é dependente da complexidade de tempo do algoritmo DFS de Cormen et al 2012 Algoritmos 22 DFS e 23 DFSVisit Para o algoritmo DFS as instruções das linhas 1 a 4 demandam uma quantidade de instruções igual a ΘV O laço entre as linhas 6 a 8 é executado por um número de iterações dependente do número de vértices ΘV O procedimento DFSVisit é invocado apenas uma vez para cada vértice graças ao vetor de visitados C Como nesse procedimento as adjacências de cada vértice são visitadas há também uma dependência do número de arcos saíntes em cada vértice Logo a complexidade computacional do Algoritmo 22 e consequentemente a do algoritmo de Componentes Fortemente Conexas é ΘV E Corretude do Algoritmo de Componentes Fortemente Conexas Propriedades de Buscas em Profundidade Teorema 536 Em qualquer busca em profundidade em um grafo dirigido ou não G V E para quaisquer dois vértices u e v exatamente uma das três condições é válida Os intervalos Tu Fu e Tv Fv são completamente disjuntos e nem u nem v é descendente do outro na floresta de profundidade O intervalo Tu Fu está contido inteiramente dentro do intervalo Tv Fv e u é um descendente de v em uma árvore de profundidade O intervalo Tv Fv está contido inteiramente dentro do intervalo Tu Fu e v é um descendente de u em uma árvore de profundidade Prova A prova começará com o caso de Tu Tv Para isso consideramos dois subcasos Tv Fu ou não O primeiro subcaso ocorre quando Tv Fu portanto v foi descoberto quando Cu true ou seja v foi descoberto mais recentemente que u o que implica que v é descendente de u Ao findar a busca de u linha 9 do Algoritmo 23 todas as arestas de u foram exploradas e consequentemente Tv Fv está completamente contido no intervalo Tu Fu Ainda considerando Tu Tv mas no subcaso de Fu Tv devido a Tw Fu para todo w V Tu Fu Tv Fv assim os intervalos Tu Fu e Tv Fv são disjuntos Como os intervalos são disjuntos nenhum vértice foi descoberto enquanto o outro ainda não havia findado linha 9 do Algoritmo 23 então nenhum é descendente do outro O caso de Tv Tu é semelhante com papéis de u e v invertidos no argumento anterior Corolário 537 O vértice v é um descendente adequado do vértice u na floresta em profundidade para um grafo dirigido ou não G V E sse Tu Tv Fv Fu Prova Imediata pelo Teorema 536 Teorema 538 Em uma floresta em profundidade de um grafo dirigido ou não G V E o vértice v é um descendente do vértice u sse no momento Tu em que uma busca descobre u há um caminho de u a v inteiramente de vértices w marcados com Cw false Prova Se v u então o caminho de u a v não possui vértices além dele mesmo Agora supõese que v seja um descendente próprio de u que ainda tem Cv false quando se define o valor de Tu Pelo Corolário 537 Tu Tv e portanto Cv false no tempo Tu Visto que v pode ser descendente de u todos os vértices w num caminho simples de u até v tem Cw false Agora supõese que haja um caminho de vértices w marcados com Cw false no caminho de u a v no tempo Tu mas v não se torna descendente de u na árvore de profundidade Sem prejuízo considerase que todo o vértice exceto v ao longo do caminho se torne um descendente de u Seja w o predecessor de v no caminho de modo que w seja um descendente de u Pelo Corolário 537 Fw Fu Como v tem que ser descoberto depois de u ser descoberto mas antes de w ser terminado têmse Tu Tv Fw Fu Então o Teorema 536 implica que o intervalo Tv Fv está contido no intervalo Tu Fu Pelo Corolário 537 v deve ser descendente de u Propriedades de Componentes Fortemente Conexas Para as propriedades abaixo considere que dS minvSTv fS maxvSFv Lema 539 Considerando C e C componentes fortemente conexas distintas em um grafo dirigido G V A seja u v C e u v C e suponha que G tenha um caminho u u Então G não pode conter um caminho v v Prova Se G possui um caminho v v então contém os caminhos u u v e v v u em G Assim u e v podem ser visitados um a partir do outro o que contradiz a hipótese de que C e C são componentes fortemente conexas distintas Lema 5310 Sejam C e C componentes fortemente conexas distintas no grafo dirigido G V A Suponha que haja um arco u v A na qual u C e v C Então fC fC Prova Considerase dois casos dependendo qual das componentes fortemente conexas C ou C têm o primeiro vértice descoberto na busca em profundidade Se dC dC seja x o primeiro vértice descoberto em C No tempo Tx todos os vértices em C e C são não visitados Cv false para todo v C C Podese afirmar então que há um caminho em x a w para qualquer w C por causa do arco u v A então x u v w Pelo Teorema 538 todos os vértices em C e C se tornam descendentes de x ma árvore de profundidade Pelo Corolário 537 x tem o tempo de término mais recente que qualquer um de seus descendentes portanto Fx fC fC Se dC dC seja y o primeiro vértice descoberto em C No tempo Ty todos os vértices w em C têm Cw false e G contém um caminho de y a cada vértice em C formado apenas por vértices z com Cz false Pelo Teorema 538 todos os vértices em C se tornam descendentes de y na árvore de profundidade Pelo Teorema 538 Fy FC No tempo Ty todos os vértices w em C têm Cw false Como existe um arco u v de C a C o Lema 539 implica que não pode haver um caminho de C a C Consequentemente nenhum vértice em C pode ser visitado por y Portanto no tempo Fy todos os vértices w em C ainda tem Cw false Assim para qualquer vértice em w C têmse Fw Fy o que implica que fC fC Corolário 5311 Considerando C e C componentes fortemente conexas distintas no grafo dirigido G V A suponha que haja um arco u v AT na qual u C e v C Então fC fC Prova Como u v AT têmse v u A Visto que as componentes fortemente conexas em GT são as mesmas o Lema 5310 implica que fC fC Teorema 5312 O Algoritmo 21 de ComponentesFortementeConexas encontra corretamente as componentes fortemente conexas de um grafo dirigido G V A dado como sua entrada Prova A prova é realizada por indução em relação ao número de árvores de busca encontradas na busca em profundidade de GT na linha 6 Cada árvore forma uma componente fortemente conexa A hipótese da indução é que as primeiras k árvores produzidas na linha 6 são componentes fortemente conexas A base da indução quando k 0 é trivial No passo da indução supõese que cada uma das k primeiras árvores de profundidade produzidas na linha 6 é uma componente fortemente conexa e consideramos a k1ésima árvore produzida Seja u a raiz dessa árvore e supondo que u esteja na componente fortemente conexa C Como resultado do modo que se escolhe a raiz da árvore na linha 6 Fu fC fC para qualquer componente fortemente conexa C exceto C que ainda tenha de ser visitada Pela hipótese de indução no momento da busca de u na árvore de profundidade todos os vértices w em C tem Cw false Então pelo Teorema 538 todos os outros vértices de C são descendentes de u nessa árvore de profundidade Além disso pela hipótese de indução e pelo Corolário 5311 qualquer arco em GT que saem de C devem ir até componentes fortemente conexas que já foram visitadas Assim nenhum vértice em uma componente fortemente conexa exceto C será um descendente de u durante a busca em profundidade de GT Portanto os vértices da árvore de busca em profundidade em GT enraizada em u formam exatamente uma componente fortemente conexa o que conclui o passo de indução e a prova 5332 Ordenação Topológica A ordenação topológica no contexto de grafos recebe um grafo acíclico dirigido G V A e ordena linearmente todos os vértices tal que se existe um arco u v A então u aparece antes de v na ordenação O algoritmo de Ordenação Topológica tem como base uma busca em largura com a adição de uma lista O para inserir os vértices como pode ser visto no Algoritmo 25 Os vértices são inseridos sempre no início da lista O logo que o algoritmo termina de visitálo linha 10 do Algoritmo 25 Algoritmo 24 DFS para Ordenação Topológica Input um grafo dirigido não ponderado G V A Configurando todos os vértices 1 Cv false v V 2 Tv v V 3 Fv v V configurando o tempo de início 4 tempo 0 Criando lista com os vértices ordenados topologicamente 5 O 6 foreach u V do 7 if Cu false then DFSVisitOT é especificado no Algoritmo 25 8 DFSVisitOTG u C T F tempo O 9 return O Algoritmo 25 DFSVisitOT Input um grafo G V E vértice de origem v V e os vetores C T e F e uma variável tempo Z uma lista O 1 Cv true 2 tempo tempo 1 3 Tv tempo 4 foreach u Nv do 5 if Cu false then 6 DFSVisitOTG u C T F tempo O 7 tempo tempo 1 8 Fv tempo Adiciona o vértice v no início da lista O 9 O v O Complexidade da Ordenação Topológica Como a inserção no início de uma lista demanda tempo O1 a complexidade de tempo da Ordenação Topológica de um grafo acíclico é dependente da Busca em Profundidade Logo a complexidade da Ordenação Topológica é OVA 0 Corretude da Ordenação Topológica Lema 5313 Um grafo dirigido G V A é acíclico sse uma busca em profundidade de G não produz nenhum arco de retorno Prova Supondo que uma busca em profundidade produza um arco de retorno u v Então o vértice v é um ascendente ancestral do vértice u na floresta em profundidade Assim G contém um caminho de v a u e o arco u v completa o ciclo Supondo que G contenha um ciclo c mostrouse que uma busca em profundidade de G produz um arco de retorno Seja v o primeiro vértice a ser descoberto em c e seja u v o arco precedente em c No tempo Tv os vértices em c formam um caminho de vértices w com Cw false de v a u Pelo Teorema 538 o vértice u se torna um descendente de v na floresta em profundidade Então u v é um arco de retorno Teorema 5314 O Algoritmo 24 produz uma ordenação topológica de um grafo dirigido acíclico G V A dado como entrada Prova Supondo que o algoritmo seja executado sobre um determinado grafo dirigido acíclico G V A para determinar os tempos de término para seus vértices É suficiente mostrar que para qualquer par de vértices distintos u v V se G contém um arco de u a v então Fv Fu Considere qualquer arco u v explorado no algoritmo Quando esse arco é explorado v ainda não foi visitado por DFSVisitOT já que v é ascendente ancestral de u e u v é um arco de retorno o que contradiz o Lema 5313 Portanto v já deve ter Cv false ou já foi visitado Se v tem Cv false ele se torna um descendente de u e Fv Fu Se v já foi visitado Fv já foi definido então Fv Fu Assim para qualquer arco u v A têmse Fv Fu