Seminário sobre Busca em Grafos
....................................................
Antonio Dirceu Rabelo de Vasconcelos Filho
Roberta Beltrão Correia Lima
Busca em Grafos - Tópicos







Introdução
Grafos x Árvores
Processo Geral
Busca em Profundidade
Busca em Largura
Grafos Não-Conexos
Complexidade
Introdução


O que é um grafo?
Qual o objetivo da busca em
grafos?
Grafos x Árvores

Quando o grafo é uma árvore o
problema da busca se torna
simples, pois existe uma ordem
“natural” para percorrê-lo, uma
vez que eles são claramente
divididos em raiz, sub-árvore da
esquerda e sub-árvore da
direita.
A
B
D
F
C
E
Grafos x Árvores





A
Para caminhar em uma árvore
temos quatro tipos de busca:
Pre-Order (Pre-Ordem);
In-Order (Central);
Pos-Order (Pós-Ordem);
Por Nível.
B
D
F
C
E
Grafos x Árvores




A
Pre-Order (Pre-Ordem):
1º. Visita a raiz;
2º. Percorre a sub-árvore da
esquerda;
3º. Percorre a sub-árvore da
direita.
B
D
F
C
E
Grafos x Árvores




A
In-Order (Central):
1º. Percorre a sub-árvore da
esquerda;
2º. Visita a raiz;
3º. Percorre a sub-árvore da
direita.
B
D
F
C
E
Grafos x Árvores




A
Pos-Order (Pós-Ordem):
1º. Percorre a sub-árvore da
esquerda;
2º. Percorre a sub-árvore da
direita.
3º. Visita a raiz;
B
D
F
C
E
Grafos x Árvores


A
Por Nível:
B
Percorre-se um nível de cada
vez, sendo cada nível percorrido
da esquerda para a direita.
D
F
C
E
Grafos x Árvores
Ex.:




Pre-Order: A B D F E G H I K J C
In-Order: F D B G E I K H J A C
Pos-Order: F D G K I J H E B C A
Por Nível: A B C D E F G H I J K
Grafos x Árvores

Quando o grafo não tiver a
propriedade de árvore não há um
referencial geral a ser considerado,
ou seja , não são definidos
conceitos de esquerda, direita e
nível. Assim o processo de busca
se torna mais difícil.
Grafos x Árvores
Desse modo surgem as perguntas:

Como caminhar no grafo de modo a visitar todos
os vértices e arestas, evitando, contudo,
repetições desnecessárias?

Como definir um caminhamento sistemático no
grafo, de modo que fique determinado qual o
vértice a ser visitado na seqüência de visitas?
Processo Geral
 Seja
G um grafo no qual todos os vértices estão inicialmente
desmarcados.
 Inicialmente, marca-se como visitado um vértice v escolhido
arbitrariamente. Esse vértice inicial é chamado de raiz de busca.
 Seleciona-se uma aresta que parte de algum vértice já marcado
v. Marca-se então a aresta (v,w) como explorada e o vértice w
como visitado (caso ainda não o seja).
 O processo termina quando todas as arestas de G tiverem sido
selecionadas.
Processo Geral
Algoritmo de busca geral:
Dados: grafo G (V,E)
A
Escolher e marcar um vértice inicial
Enquanto existir algum vértice v marcado e incidente a
uma aresta (v,w) não explorada, faça
explorar a aresta (v,w)
se w é não marcado
então marcar w
D
C
B
E
Processo Geral
Note que durante o processo de exploração de um vértice é
possível que ele seja alcançado diversas vezes (tantas quantas
forem o número de arestas incidentes).
Nos critérios de busca em profundidade e busca em largura, que
veremos a seguir, a escolha do próximo vértice torna-se única,
mas para os casos do vértice inicial e aresta incidente a escolha
permanece arbitrária.
Busca em Profundidade
(Depth-First Search)

Dentre todos os vértices marcados e
incidentes a alguma aresta ainda não
explorada, escolher aquele mais
recentemente alcançado na busca.

Um detalhe importante é que usamos o
auxílio de uma pilha para guardar os
vértices já marcados.
Busca em Profundidade
(Depth-First Search)
Procedimento P (v,pai)
marcar v;
colocar v na pilha Q;
Ex.
para toda aresta (v,w) faça
se w é não marcado
então
visitar (v,w);
marcar (v,w) como aresta de árvore;
P(w,v);
senão
se w  pai
então
visitar (v,w);
marcar (v,w) como aresta de retorno;
senão
visitar (v,w);
marcar (v,w) como aresta de árvore;
3
retirar v da pilha
fim_do_procedimento
1
6
2
4
5
Busca em Profundidade
(Depth-First Search)
O algoritmo particiona as arestas em:
 Arestas de Árvore;
 Arestas de Retorno.

As arestas de árvore constituem uma árvore
geradora de G.

As arestas de retorno, cada uma por sua vez, liga
um vértice v a um ancestral seu.
Busca em Profundidade
(Depth-First Search)
Ex.: Criar duas diferentes árvores geradoras para o grafo abaixo:
v5
v4
v6
v3
v1
v2
Busca em Largura
(Breadth-First Search)

Dentre todos os vértices marcados e
incidentes a alguma aresta ainda não
explorada, escolher aquele menos
recentemente alcançado na busca.

Um detalhe importante é que usamos o
auxílio de uma fila para guardar os
vértices já marcados.
Busca em Largura
(Breadth-First Search)
Procedimento L (v,pai)
marcar v;
colocar v na fila Q;
enquanto a fila Q não for vazia faça
remover o 1º vértice w da fila;
para todo (w,x) faça
se x é não marcado
então
marque x;
adicione (w,x) à árvore T;
coloque x na fila Q;
fim_do_procedimento
Ex.
3
1
6
2
4
5
Grafos não-conexos

No caso do grafo não ser conexo o algoritmo de busca
(profundidade ou largura) terá apenas uma modificação e seguirá
o seguinte critério:

Executa-se o algoritmo a partir de um vértice v qualquer. Se ao
término do procedimento restar algum vértice do grafo G não
marcado repete-se o procedimento para este vértice.
Ex.:
a
e
f
c
b
d
h
g
i
Complexidade

Nos dois algoritmos de busca (largura e profundidade)
observamos que cada aresta é visitada exatamente duas vezes
(uma para cada vértice). Portanto o tempo de execução depende
do número de arestas.

Quando o grafo é não-conexo, temos que analisar os vértices que
não estão conectados a ninguém. Assim, o tempo de execução
também depende do nº de vértices.

Conclusão: Para um grafo G (V,E) os algoritmos de busca em
largura e em profundidade tem complexidade
O ( |V| + |E|)
Conclusão .....................................................