Slides_Buscas_Profundidade e Largura

Prévia do material em texto

Teoria dos Grafos
Prof. Sérgio Monteiro
Busca em Profundidade
� A busca em profundidade (do inglês depth-first 
search - DFS) é um algoritmo para caminhar no 
grafo; 
� Seu núcleo se concentra em buscar, sempre que 
possível, o mais fundo no grafo;
� As arestas são exploradas a partir do vértice v 
mais recentemente descoberto que ainda possui 
arestas não exploradas saindo dele
Teoria dos Grafos 2
Busca em Profundidade
�Quando todas arestas adjacentes a v 
tiverem sido exploradas, a busca “anda 
para trás” (do inglês backtracking) para 
explorar vértices do qual v foi descoberto; 
�O processo continua até que sejam 
descobertos todos os vértices que são 
alcançáveis a partir do vértice original; 
Teoria dos Grafos 3
Busca em Profundidade
�Se todos os vértices já foram 
descobertos, então é o fim;
�Caso contrário o processo continua a 
partir de um novo vértice de origem 
ainda não descoberto (grafos 
desconexos). 
Teoria dos Grafos 4
Teoria dos Grafos 5
Busca em Profundidade
Teoria dos Grafos 6
Busca em Profundidade
Busca em Largura
�Dados um G = (V, E) e um vértice de origem 
s, a busca em largura explora 
sistematicamente as arestas de G até 
descobrir cada vértice acessível a partir 
de s
�O algoritmo calcula a distância (menor 
numero de arestas) desde s até todos os 
vértices acessíveis a partir de s
Teoria dos Grafos 7
Busca em Largura
�O algoritmo produz uma árvore primeiro 
em extensão 
�Descobre todos os vértices de distância 
k de s antes de descobrir quaisquer 
vértices de distância k + 1
Teoria dos Grafos 8
Teoria dos Grafos 9
Busca em Largura
Teoria dos Grafos 10
Busca em Largura
Teoria dos Grafos 11
Busca em Largura
Teoria dos Grafos 12
Busca em Largura
Teoria dos Grafos 13
Busca em Largura
Teoria dos Grafos 14
Busca em Largura
Teoria dos Grafos 15
Busca em Largura
Teoria dos Grafos 16
Busca em Largura
Teoria dos Grafos 17
Busca em Largura
Introdução Teoria da Complexidade 18
Bibliografia Recomendada
• CORMEN, T. H. et al. Algoritmos: teoria
e prática. 3 ed. Rio de Janeiro: Elsevier,
2012.