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
[email protected]
© 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.
2
4
0
Vértices já
visitados
1
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:
0
2
4
6
1
2
0
5
3
3
1
6
Início
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
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 algoritmo a busca inicia a partir de um nó
raiz e percorre cada caminho de forma a ir o mais
longe possível antes de passar para outro
caminho.
O caminho percorrido por esta busca forma uma
árvore profunda.
Pode ser implementada com recursão (pilha).
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
A
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
B
A
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
E
A
B
D
F
E
G
C
A
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
D
A
E
D
F
E
G
C
B
A
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
G
A
D
D
F
E
G
C
E
B
B
A
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
F
A
G
D
F
E
G
C
D
E
B
B
A
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
G
A
D
D
F
E
G
C
E
B
B
A
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
D
A
E
D
F
E
G
C
B
A
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
C
A
D
D
F
E
G
C
E
B
B
A
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
D
A
E
D
F
E
G
C
B
A
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
E
A
B
D
F
E
G
C
A
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
B
A
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
A
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Pilha
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
Caminho percorrido
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Profundidade
void dfs(int inicio) {
dfsRec(inicio);
}
void dfsRec(int v) {
if (mark[v])
return;
Chamada recursiva para o vértice inicial
Se o vértice já foi visitado, retorna
mark[v] = true;
Marca o vértice como visitado
NoLista temp = adj[v].inicio;
while (temp != null) {
Lista de adjacências é percorrida
dfsRec(temp.vertice);
Busca recursiva no vizinho
temp = temp.next;
Visita o próximo vizinho
}
}
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
Outra forma de percorrer um grafo é através da
busca em largura (também chamada de busca por
nível).
Esse tipo de busca visita primeiro todos os nós
próximos da raiz da busca antes de visitar os mais
distantes.
A árvore gerada pelo caminho percorrido é uma
árvore larga (pouco profunda, mas com muitos
filhos por nó).
Pode ser implementada com ajuda de uma fila.
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
A
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
B
C
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
C
E
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
E
D
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
D
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
F
G
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
G
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
A
D
F
E
G
C
B
Fila
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
Caminho percorrido
A
D
F
E
G
C
B
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados
Busca em Largura
void bfs(int inicio) {
fila.inserir(inicio); mark[inicio] = true;
while (!fila.vazia()) {
int v = fila.remover();
NoLista temp = adj[v].inicio;
while (temp != null) {
int w = temp.vertice;
if (!mark[w]) {
fila.inserir(w);
mark[w] = true;
}
temp = temp.next;
}
}
}
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados