Grafos Busca em Largura

Prévia do material em texto

GCC218 � Algoritmos em Grafos
Mayron César O. Moreira
Universidade Federal de Lavras
mayron.moreira@u�a.br
Mayron César O. Moreira (UFLA) GCC218 1 / 7
Conteúdo
1 Busca em Grafos
Busca Genérica
Busca em Largura
2 Referências
Mayron César O. Moreira (UFLA) GCC218 2 / 7
Motivação lúdica
Como atravessar um labirinto?
Mayron César O. Moreira (UFLA) GCC218 3 / 7
Busca Genérica
BG(i)
Marque o vértice i como explorado
while ∃j ∈ V marcado com uma aresta (j , k) não explorada
Escolha j e explore a aresta (j , k)
if k é não marcado
Marque k
Mayron César O. Moreira (UFLA) GCC218 4 / 7
Busca Genérica
BG(i)
Marque o vértice i como explorado
while ∃j ∈ V marcado com uma aresta (j , k) não explorada
Escolha j e explore a aresta (j , k)
if k é não marcado
Marque k
Mayron César O. Moreira (UFLA) GCC218 4 / 7
Busca em Largura (BFS - Breadth-First Search)
Aplicações
Algoritmos de caminhos mais curtos e obtenção de árvores geradoras.
Ideia
Visitar todos os vértices com distância k da origem, e depois expandir
sua busca para os indivíduos com distância k + 1;
Introduz o conceito de vértices Brancos, Cinzas e Pretos.
Mayron César O. Moreira (UFLA) GCC218 5 / 7
Busca em Largura (BFS - Breadth-First Search)
Nomenclatura
Branco: vértice não visitado;
Cinza: vértice descoberto pela primeira vez;
Preto: vértice que não será mais explorado.
Vejamos a implementação no JuPy!
Mayron César O. Moreira (UFLA) GCC218 6 / 7
Referências
Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and
Stein, Cli�ord (2009). Introduction to algorithms, 3rd ed, MIT press.
Goldbarg, Marco and Goldbarg, Elizabeth (2012). Grafos: Conceitos,
algoritmos e aplicações, 1ed., Elsevier.
Loureiro, Antonio Alfredo Ferreira (2020). Notas de aula (Matemática
Discreta) do professor Antonio Alfredo Ferreira Loreiro (DCC/UFMG),
https://homepages.dcc.ufmg.br/~loureiro/md.html. Último
acesso: 25 de maio de 2020.
Mayron César O. Moreira (UFLA) GCC218 7 / 7
https://homepages.dcc.ufmg.br/~loureiro/md.html
	Busca em Grafos
	Busca Genérica
	Busca em Largura
	Referências