BuscaGrafos

Busca em Grafos
IF672 - Algoritmos e Estruturas de Dados
CIn - UFPE
Adriana Libório Fernandes Lins
Arthur Cavalcanti Alem
Átila Valgueiro Malta Moreira
Flavio Juvenal da Silva Júnior
Gustavo Cauê Silva Botelho
Matheus Bispo Arrais de Souza

Murilo Raphael de Souza Lira
Rafael Alberto Gomes Pereira Lima
Rafael Brandão Lobo
Rafael Loureiro de Carvalho
Tiago Carneiro Pessoa Canto
Vinicius Miranda Cesar

[e-mail]
© Copyright 2008
2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Busca em Grafos
Escolhendo um vértice inicial, é possível visitar os vértices seguindo uma determinada ordem.

0
Vértices já visitados 2

1

4
3

Aresta escolhida A cada iteração, escolhemos uma aresta que parte de um vértice já visitado.
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Busca em Grafos
A cada passo, os vértices são divididos em três grupos: 2
0

5
7

3
1

6
4

Vértices já escolhidos Vértices candidatos © Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Vértices não visitados Busca em Grafos
Quando uma aresta é escolhida, os vértices podem mudar de grupo:
2
0

5
7

3
1

6
4

Vértices já escolhidos Vértices candidatos © Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Vértices não visitados Busca em Grafos
Utilizando as arestas escolhidas na ordem da busca, é possível montar uma árvore de busca:
2

0

4
6
0

5

3
1

1
3

6
Início

© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

2
4

5

Busca em Grafos
As buscas mais comuns são:
• Busca em Profundidade (Depth-First Search)
Escolhe arestas que partem do vértice mais recente

• Busca em Largura (Breadth-First Search)
Escolhe arestas que partem do vértice mais antigo

• Buscas Gulosas (Greedy Search)
Escolhe arestas com menor custo, menor caminho, ...

© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Busca em Profundidade
Nesse