Upload
others
View
10
Download
0
Embed Size (px)
Citation preview
BCC204 - Teoria dos Grafos
Marco Antonio M. Carvalho
(baseado nas notas de aula do prof. Haroldo Gambini Santos)Departamento de Computação
Instituto de Ciências Exatas e BiológicasUniversidade Federal de Ouro Preto
26 de agosto de 2019
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 1 / 63
Avisos
Site da disciplina:I http://www.decom.ufop.br/marco/
Lista de e-mails:I [email protected]
Para solicitar acesso:I http://groups.google.com/group/bcc204
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 2 / 63
Conteúdo
1 Busca em Grafos
2 Busca em Profundidade
3 Busca em Largura
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 3 / 63
Busca em Grafos
DefiniçãoA Busca em Grafos (ou Percurso em Grafos) é a examinação de vértices e arestasde um grafo.
O projeto de bons algoritmos para determinação de estruturas ou propriedades degrafos depende fortemente do domínio destas técnicas.
TerminologiaEm uma busca:
I Uma aresta ou vértice ainda não examinados são marcados como nãoexplorados ou não visitados;
I Inicialmente, todos os vértices e arestas são marcados como não explorados;
I Após terem sido examinados, os mesmos são marcados como explorados ouvisitados;
I Ao final, todos os vértices e arestas são marcados como explorados (no casode uma busca completa).
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 4 / 63
Busca Genérica
Entrada: Grafo G=(V, A)1 enquanto existir j ∈ V com uma aresta {j ,k} não visitada faça2 Escolha o vértice j e visite a aresta {j , k};3 se j não é marcado então4 marque j como visitado;5 fim6 se k não é marcado então7 marque k como visitado;8 fim9 fim
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 5 / 63
Como escapar?
Método do século XIX - Algoritmo de TrémauxPierre Trémaux (20 de Julho 1818 - 12 Março de 1895);I Francês arquiteto, fotógrafo e orientalista;I Autor de várias publicações científicas e etnografias;I Segunda pessoa a ganhar o Prix de Romea.
aBolsa de estudo destinada a estudantes das artes e atribuída pelo governofrancês a jovens artistas que se distinguissem na pintura, escultura earquitetura, criada em 1663 durante o reinado de Luís XIV de França.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 7 / 63
Como escapar?
Método do século XIX - Algoritmo de TrémauxO algoritmo de Trémaux requer que para encontrar a saída de um labirintoseja riscada uma linha no chão para marcar os caminhos percorridos:I Um caminho pode ser não visitado, visitado uma vez ou visitado duas
vezes;I A cada escolha de direção, é riscada uma linha no chão indicando o
caminho.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 8 / 63
Como escapar?
Método do século XIX - Algoritmo de TrémauxI Inicialmente, uma direção aleatória é escolhida;I Ao chegar em uma junção não visitada (ou seja, sem nenhuma linha),
escolha uma direção aleatória e risque o caminho;I Ao chegar em uma junção já marcada, vire-se e caminhe de volta,
marcando o caminho pela segunda vez;I Se este não for o caso, escolha o caminho com menos linhas e
marque-o novamente.I Quando finalmente chegar à saída do labirinto, os caminhos marcados
com apenas uma linha indicarão o caminho direto até o ponto inicial;I Se não houver saída, você voltará ao ponto inicial, no qual todos os
caminhos possuem duas linhas.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 9 / 63
Atravessando Labirintos
Exemplo de execução do Algoritmo de Trémaux.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 10 / 63
Atravessando Labirintos
Um labirinto. Considera-se que a circulação neste labirinto é feitamargeando alguma parede.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 11 / 63
Atravessando Labirintos
Pontos de entrada, saída e mudança de direção do labirinto.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 12 / 63
Atravessando Labirintos
Grafo no labirinto.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 13 / 63
Atravessando Labirintos
Grafo do labirinto.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 14 / 63
Atravessando Labirintos
IdéiaUma forma de encontrar a saída do labirinto sem nunca percorrer mais deuma vez o mesmo caminho consiste em realizar uma busca no grafo demodo a nunca repetir arestas, marcando-as.
A busca se inicia no vértice que representa a entrada e termina no vérticeque representa a saída.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 15 / 63
Atravessando Labirintos
Busca Genérica no grafo de exemplo (1).
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 16 / 63
Atravessando Labirintos
Busca Genérica no grafo de exemplo (2).
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 17 / 63
Buscas em Grafos
Buscas em GrafosDependendo do critério utilizado para escolha dos vértices e arestas aserem visitados, diferentes tipos de buscas são desenvolvidos a partir dabusca genérica.
Basicamente, duas buscas completas em grafos são essenciais:
I Busca em Profundidade (ou DFS – Depth-First Search); eI Busca em Largura (ou BFS – Breadth-First Search).
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 18 / 63
Busca em Profundidade - DFS
CaracterísticasA Busca em Profundidade visita todos os vértices de um grafo, usandocomo critério os vizinhos do vértice visitado mais recentemente.
Característica Principal: utiliza uma pilha explícita ou recursividade paraguiar a busca.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 19 / 63
Busca em Profundidade - DFS
Entrada: Grafo G=(V, A), vértice inicial v1 Marque o vértice v como visitado;2 enquanto existir w vizinho de v faça3 se w é marcado como não visitado então4 Visite a aresta {v , w};5 Marque w como visitado;6 BP(G ,w);//chamada recursiva da função7 fim8 senão9 se {v ,w} não foi visitada ainda então
10 Visite {v ,w};11 fim12 fim13 fim
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 20 / 63
Busca em Profundidade - DFS
Classificação de ArestasAo explorar um grafo G conexo usando a DFS, podemos categorizar asarestas:I Arestas de Árvore: Satisfazem ao primeiro se do algoritmo (linha 3),
ou seja, levam à visitação de vértices ainda não visitados;I Arestas de Retorno: Demais arestas. Formam ciclos, pois levam a
vértices já visitados.
Árvore de ProfundidadeA subárvore de G formada pelas arestas de árvore é chamada de Árvore deProfundidade de G .
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 21 / 63
DFS - Exemplo
Grafo de exemplo.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 22 / 63
DFS - Exemplo
(1) Aresta {1,2}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 23 / 63
DFS - Exemplo
(2) Aresta {2,3}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 24 / 63
DFS - Exemplo
(3) Aresta {3, 1}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 25 / 63
DFS - Exemplo
(4) Aresta {3, 4}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 26 / 63
DFS - Exemplo
(5) Aresta {4, 5}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 27 / 63
DFS - Exemplo
(6) Aresta {5, 3}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 28 / 63
DFS - Exemplo
(7) Aresta {3, 6}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 29 / 63
DFS - Exemplo
(8) Aresta {3, 7}.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 30 / 63
DFS - Exemplo
Grafo original e correspondente árvore de profundidade.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 31 / 63
DFS
ComplexidadePara cada vértice do grafo, a DFS percorre todos os seus vizinhos. Cadaaresta é visitada duas vezes.
Se representarmos o grafo por uma lista de adjacências, a DFS temcomplexidade O(n + m).
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 32 / 63
DFS-Grafos Direcionados
Atenção!A aplicação da DFS em grafos direcionados é essencialmente igual àaplicação em grafos não direcionados.
No entanto, mesmo o grafo direcionado sendo conexo, a DFS pode precisarser chamada repetidas vezes enquanto houver vértices não visitados,retornando uma floresta.
Este é o mesmo caso quando a DFS é aplicada a um GND desconexo.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 33 / 63
Busca em Profundidade - Reinício
Entrada: Grafo G=(V , A)1 enquanto existir v ∈ V não visitado faça2 BP(G , v);3 fim
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 34 / 63
Busca em Profundidade - DFS
Classificação de ArestasAo explorar um grafo G direcionado usando a DFS, podemos categorizar asarestas. Sejam o vértice v a origem da aresta e o vértice w o destino damesma:
I Arcos de Avanço: Caso w seja descendente de v na floresta;I Arcos de Retorno: Caso v seja descendente de w na floresta;I Arcos de Cruzamento: Caso w não seja descendente de v e v não seja
descendente de w .
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 35 / 63
DFS - Exemplo
Grafo de exemplo.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 36 / 63
DFS - Exemplo
Grafo original e respectiva floresta de profundidade.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 45 / 63
Busca em Largura
CaracterísticasA Busca em Largura visita todos os vértices de um grafo, usando comocritério o vértice visitado menos recentemente e cuja vizinhançaainda não foi explorada.
Característica Principal: utiliza uma fila guiar a busca.
Atuação em camadas:
I Inicialmente são considerados os vértices com distância 0 do vértice inicial;
I Na iteração 1 são visitados os vértices com distância 1; prosseguindo, demodo genérico, na iteração d será adicionada uma camada com todos osvértices com distância d do vértice inicial;
I Cada novo vértice visitado é adicionado no final de uma fila Q;
I Cada vértice da fila é removido depois que toda a vizinhança for visitada;
I A busca termina quando a fila se torna vazia.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 46 / 63
Busca em Largura - BFS
Entrada: Grafo G=(V, A), vértice inicial v1 Crie uma fila Q vazia;2 Marque v como visitado;3 Insira v em Q;4 enquanto Q 6= ∅ faça5 v ← remove elemento de Q;6 para todo vértice w vizinho de v faça7 se w é marcado como não visitado então8 Visite a aresta {v , w};9 Insira w em Q;
10 Marque w como visitado;11 fim12 senão13 se {v ,w} não foi visitada ainda então14 Visite {v ,w};15 fim16 fim17 fim18 fim
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 47 / 63
BFS - Exemplo
(1) Inclusão de 1Q = {1}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 48 / 63
BFS - Exemplo
(2) ArestaAresta{1, 2}Q = {2}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 49 / 63
BFS - Exemplo
(3) Aresta{1, 3}Q = {2, 3}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 50 / 63
BFS - Exemplo
(4) Aresta{2, 3}Q = {3}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 51 / 63
BFS - Exemplo
(5) Aresta{3, 4}Q = {4}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 52 / 63
BFS - Exemplo
(6) Aresta{3, 5}Q = {4, 5}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 53 / 63
BFS - Exemplo
(7) Aresta{3, 6}Q = {4, 5, 6}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 54 / 63
BFS - Exemplo
(8) Aresta{3, 7}Q = {4, 5, 6, 7}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 55 / 63
BFS - Exemplo
(9) Aresta{4, 5}Q = {5, 6, 7}
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 56 / 63
BFS - Exemplo
Grafo original e respectiva árvore.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 57 / 63
BFS
ComplexidadeCada vértice só entra na fila uma vez.
Inserir e remover na fila possuem complexidade constante, realizadas |V |vezes cada.
A lista de adjacências de cada vértice é examinada apenas uma vez, e asoma dos comprimentos de todas as listas é Θ(m).
Logo, se representarmos o grafo por uma lista de adjacências, a BFS temcomplexidade O(n + m).
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 58 / 63
Aplicações
Algumas aplicações incluem:I Detectar grafos desconectados;I Detectar se o grafo possui ciclos;I Encontrar componentes biconexas;I Classificar arestas;I Encontrar componentes fortemente conexas;I Flood Fill ;I Determinar o menor caminho em grafos não ponderados.
Algumas aplicações requerem que seja retornada uma lista com a ordemem que os vértices foram visitados.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 59 / 63
DFS × BFS
DFS - Busca em ProfundidadeI Incursões profundas no grafo, voltando somente quando não existem mais vértices
desconhecidos pela frente;I Marca o vértice antes de visitar toda sua vizinhança;I Uso de pilha.
BFS - Busca em Largura
I Busca progride em “largura”: certifica-se de quevizinhos próximos sejam visitados primeiro;partir de v ;
I Marca o vértice depois de visitar toda suavizinhança;
I Uso de fila.
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 60 / 63
Avisos
Verifiquem a visualização de algoritmos!
I https://visualgo.net/
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 61 / 63
Visualizações
Flood Fill 4 direçõesI https://en.wikipedia.org/wiki/File:
Recursive_Flood_Fill_4_(aka).gif
Flood Fill 8 direçõesI https://en.wikipedia.org/wiki/File:
Recursive_Flood_Fill_8_(aka).gif
Flood Fill Busca em Largura:I https://en.wikipedia.org/wiki/File:
Wfm_floodfill_animation_queue.gif
Flood Fill Busca em Profundidade:I https://en.wikipedia.org/wiki/File:
Wfm_floodfill_animation_stack.gif
Marco Antonio M. Carvalho (UFOP) BCC204 26 de agosto de 2019 62 / 63