Técnicas de Busca em Grafos

Prévia do material em texto

Prof. Marcelo Andrade Teixeira
Universidade Estácio de Sá
TEMA 4 – TÉCNICAS DE BUSCA EM GRAFOS
Prof. Marcelo Andrade Teixeira
Universidade Estácio de Sá
TÉCNICA DE BUSCA:
VISITA EM GRAFOS
 Análise de Algoritmos 3
A técnica de Busca em Grafos (ou Percurso em Grafos) é uma forma de 
examinar de vér ces e arestas de um grafo. 
É fortemente recomendado o domínio destas técnicas para a elaboração 
de bons projetos de algoritmos, não somente em grafos, como para 
outras técnicas de programação.
 Análise de Algoritmos 4
Duas técnicas são amplamente conhecidas para buscar informações da 
estrutura de um grafo:
1. Busca em Largura
2. Busca em Profundidade
4
1
2
3
5
6 7
8
9
 Análise de Algoritmos 5
Duas técnicas são amplamente conhecidas para buscar informações da 
estrutura de um grafo:
1. Busca em Largura
2. Busca em Profundidade
4
1
2
3
5
6 7
8
9
 Análise de Algoritmos 6
Algoritmo de Busca em Largura ou busca de amplitude é um 
algoritmo de busca em grafos u lizado para realizar uma busca 
ou travessia em um grafo pico.
 Análise de Algoritmos 7
ele. 
• Então, para cada um desses vér ces mais próximos, exploramos os seus 
vér ces vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
4
1
2
3
5
6 7
8
9
 Análise de Algoritmos 8
4
1
2
3
5
6 7
8
9
ele. 
• Então, para cada um desses vér ces mais próximos, exploramos os seus 
vér ces vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
 Análise de Algoritmos 9
4
1
2
3
5
6 7
8
9
ele. 
• Então, para cada um desses vér ces mais próximos, exploramos os seus 
vér ces vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
 Análise de Algoritmos 10
4
1
2
3
5
6 7
8
9
ele. 
• Então, para cada um desses vér ces mais próximos, exploramos os seus 
vér ces vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
 Análise de Algoritmos 11
4
1
2
3
5
6 7
8
9
ele. 
• Então, para cada um desses vér ces mais próximos, exploramos os seus 
vér ces vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
 12
4
1
2
3
5
6 7
8
9
ele. 
• Então, para cada um desses vér ces mais próximos, exploramos os seus 
vér ces vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
 Análise de Algoritmos 13
 47
6
1
2
5
3
4 7
9
8
conhecido em inglês por Depth-First Search 
- DFS) é um algoritmo usado para realizar 
uma busca ou travessia em um grafo.
 48
6
1
2
5
3
4 7
9
8
conhecido em inglês por Depth-First Search 
- DFS) é um algoritmo usado para realizar 
uma busca ou travessia em um grafo.
 Análise de Algoritmos 49
 Análise de Algoritmos 50
 Análise de Algoritmos 51
 Análise de Algoritmos 52
 Análise de Algoritmos 53
 Análise de Algoritmos 54
 Análise de Algoritmos 55
 Análise de Algoritmos 56
 Análise de Algoritmos 57
 Análise de Algoritmos 58
 Análise de Algoritmos 59
 Análise de Algoritmos 60
 Análise de Algoritmos 61
 Análise de Algoritmos 62
 Análise de Algoritmos 63
 Análise de Algoritmos 64
 Análise de Algoritmos 65
 Análise de Algoritmos 66
 Análise de Algoritmos 67
 Análise de Algoritmos 68
 Análise de Algoritmos 69
 Análise de Algoritmos 70
 Análise de Algoritmos 71
 Análise de Algoritmos 72
 Análise de Algoritmos 73
 74
Profundidade (com tempos de visitas e tempos de términos) dos 
seguintes grafos abaixo:
Grafo A Grafo B
Prof. Marcelo Andrade Teixeira
Universidade Estácio de Sá (UNESA)
TÉCNICA DE BUSCA:
ÁRVORES GERADORAS MÍNIMAS
 Análise de Algoritmos 76
Grafos 
Árvores
Grafos 
Ciclos
Floresta
 Análise de Algoritmos 77
 Análise de Algoritmos 78
 Análise de Algoritmos 79
• O algoritmo de Prim, que faz crescer uma árvore até que ela se 
torne geradora e,
• O algoritmo de Kruskal, que faz crescer uma floresta geradora 
até que ela se torne uma árvore. 
 Análise de Algoritmos 80
Ambos os algoritmos (kruskal e Prim) têm caráter guloso (greedy):
❑Em cada iteração do algoritmo, “abocanham” a aresta que 
parece mais promissora naquele momento sem se preocupar 
com o efeito global dessa escolha. 
❑Esses algoritmos são os protó pos da estratégia gulosa que 
 81
menor quan dade de fibra ó ca possível.
• Instalação de linhas telefônicas (ou elétricas) entre um conjunto de 
localidades u lizando a infra-estrutura das rodovias com o menor uso de 
material.
 Análise de Algoritmos 82
• O Algoritmo de PRIM, foi publicado por Robert C. Prim em 1957 e 
por E. W. Dijkstra pouco depois. 
• Escolhe-se um vér ce como raiz da busca, o algoritmo mantém 
uma árvore até que todas as arestas sejam percorridas pelo 
algoritmo.
• O algoritmo tem caráter guloso: em cada iteração, escolhe a 
aresta mais barata do corte sem se preocupar com o efeito global, 
a longo prazo, dessa escolha.
 Análise de Algoritmos 83
A Função EXTRACT-MIN mantém de 
forma eficiente o menor elemento em 
uma lista.
 Análise de Algoritmos 84
EXTRACT-MIN( )
1: 𝑚𝑖𝑛 = 𝑄.first
2: for each do
2: if d[𝑣] < d[𝑚𝑖𝑛] then
3:  
4: end if
5: end for
6: 
7: return 
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 85
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 86
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 87
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 88
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 89
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 90
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 91
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 92
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 93
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 94
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 95
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 96
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 97
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 98
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 99
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 100
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 101
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 102
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 103
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 104
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 105
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 106
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 107
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 108
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 109
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 110
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 111
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 112
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 113
Prof. Marcelo Andrade Teixeira Análise de Algoritmos 114
 Análise de Algoritmos 115
 Análise de Algoritmos 116
 Análise de Algoritmos 117
 Análise de Algoritmos 118
 Análise de Algoritmos 119
 Análise de Algoritmos 120
 Análise de Algoritmos 121
 Análise de Algoritmos 122
 Análise de Algoritmos 123
 Análise de Algoritmos 124
 Análise de Algoritmos 125
 Análise de Algoritmos 126
 Análise de Algoritmos 127
 Análise de Algoritmos 128
 Análise de Algoritmos 129
 Análise de Algoritmos 130
 Análise de Algoritmos 131
 Análise de Algoritmos 132
 Análise de Algoritmos 133
 Análise de Algoritmos 134
 Análise de Algoritmos 135
 Análise de Algoritmos 136
Considerando que o grafo tem vér ces e arestas:
• Precisamos ordenas as arestas por ordem crescente, .
• Adicionar as arestas mínimas (1 aresta inserida, dois vér ces acessados). Logo, 
.
• Complexidade final:.
 Análise de Algoritmos 137
Considerando que o grafo tem vér ces e arestas:
• Precisamos ordenas as arestas por ordem crescente, .
• Adicionar as arestas mínimas (1 aresta inserida, dois vér ces acessados). Logo, 
.
• Complexidade final: .
 Análise de Algoritmos 138
Considerando que o grafo tem vér ces e arestas:
• Precisamos ordenas as arestas por ordem crescente, .
• Adicionar as arestas mínimas (1 aresta inserida, dois vér ces acessados). Logo, 
.
• Complexidade final: .
1. Aplique o algoritmo de Prim e Kruskal nos grafos abaixo e compare os 
resultados ob dos de cada um:
 Análise de Algoritmos 139
Grafo A Grafo B
Dúvidas?
 Análise de Algoritmos 140
Bibliografia
• Algoritmos DFS e BFS: 
• Adaptado de Jayme Luiz. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC, 
1994.
• Adaptado das aulas Prof Dr. Eduardo Nakamura, Universidade Federal do Amazonas 
(ICOMP- UFAM) – AM.
• Adaptado das aulas Prof. Dr Fábio Pro , Universidade Federal Fluminense (IC-UFF) – 
Niterói, RJ.
• Adaptado das aulas Análise de Algoritmos: Prof Ms. Simone , Universidade 
Federal do Amazonas (ICOMP- UFAM - FUCAPI) – AM.
• Análise Assintó ca: 
• Cormen, Thomas H. (2009). Introduc on to Algorithms,. Massachuse s Ins tute of
Technology: MIT Press. 333 páginas.
• Adaptado: Paulo Feofiloff. Departamento de Ciência da Computação e Ins tuto de 
Matemá ca e Esta s ca da USP.
 Análise de Algoritmos 141