Seminário sobre Busca em Grafos.................................................... Antonio Dirceu...
24
Seminário sobre Busca em Seminário sobre Busca em Grafos Grafos ........................... ........................... ......................... ......................... Antonio Dirceu Rabelo de Vasconcelos Antonio Dirceu Rabelo de Vasconcelos Filho Filho Roberta Beltrão Correia Lima Roberta Beltrão Correia Lima
Seminário sobre Busca em Grafos.................................................... Antonio Dirceu Rabelo de Vasconcelos Filho Roberta Beltrão Correia
Seminrio sobre Busca em
Grafos.................................................... Antonio
Dirceu Rabelo de Vasconcelos Filho Roberta Beltro Correia Lima
Slide 3
Busca em Grafos - Tpicos Introduo Introduo Grafos x rvores
Grafos x rvores Processo Geral Processo Geral Busca em Profundidade
Busca em Profundidade Busca em Largura Busca em Largura Grafos
No-Conexos Grafos No-Conexos Complexidade Complexidade
Slide 4
Introduo O que um grafo? O que um grafo? Qual o objetivo da
busca em grafos? Qual o objetivo da busca em grafos?
Slide 5
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 so claramente divididos em raiz, sub-rvore da esquerda
e sub-rvore da direita. Quando o grafo uma rvore o problema da
busca se torna simples, pois existe uma ordem natural para
percorr-lo, uma vez que eles so claramente divididos em raiz,
sub-rvore da esquerda e sub-rvore da direita. A BC DE F
Slide 6
Grafos x rvores Para caminhar em uma rvore temos quatro tipos
de busca: Para caminhar em uma rvore temos quatro tipos de busca:
Pre-Order (Pre-Ordem); Pre-Order (Pre-Ordem); In-Order (Central);
In-Order (Central); Pos-Order (Ps-Ordem); Pos-Order (Ps-Ordem); Por
Nvel. Por Nvel. A BC DE F
Slide 7
Grafos x rvores Pre-Order (Pre-Ordem): Pre-Order (Pre-Ordem):
1. Visita a raiz; 1. Visita a raiz; 2. Percorre a sub-rvore da
esquerda; 2. Percorre a sub-rvore da esquerda; 3. Percorre a
sub-rvore da direita. 3. Percorre a sub-rvore da direita. A BC DE
F
Slide 8
Grafos x rvores In-Order (Central): In-Order (Central): 1.
Percorre a sub-rvore da esquerda; 1. Percorre a sub-rvore da
esquerda; 2. Visita a raiz; 2. Visita a raiz; 3. Percorre a
sub-rvore da direita. 3. Percorre a sub-rvore da direita. A BC DE
F
Slide 9
Grafos x rvores Pos-Order (Ps-Ordem): Pos-Order (Ps-Ordem): 1.
Percorre a sub-rvore da esquerda; 1. Percorre a sub-rvore da
esquerda; 2. Percorre a sub-rvore da direita. 2. Percorre a
sub-rvore da direita. 3. Visita a raiz; 3. Visita a raiz; A BC DE
F
Slide 10
Grafos x rvores Por Nvel: Por Nvel: Percorre-se um nvel de cada
vez, sendo cada nvel percorrido da esquerda para a direita.
Percorre-se um nvel de cada vez, sendo cada nvel percorrido da
esquerda para a direita. A BC DE F
Slide 11
Grafos x rvores Pre-Order: A B D F E G H I K J C 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 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 Pos-Order: F D G K I
J H E B C A Por Nvel: A B C D E F G H I J K Por Nvel: A B C D E F G
H I J K Ex.:
Slide 12
Grafos x rvores Quando o grafo no tiver a propriedade de rvore
no h um referencial geral a ser considerado, ou seja, no so
definidos conceitos de esquerda, direita e nvel. Assim o processo
de busca se torna mais difcil. Quando o grafo no tiver a
propriedade de rvore no h um referencial geral a ser considerado,
ou seja, no so definidos conceitos de esquerda, direita e nvel.
Assim o processo de busca se torna mais difcil.
Slide 13
Grafos x rvores Desse modo surgem as perguntas: Como caminhar
no grafo de modo a visitar todos os vrtices e arestas, evitando,
contudo, repeties desnecessrias? Como caminhar no grafo de modo a
visitar todos os vrtices e arestas, evitando, contudo, repeties
desnecessrias? Como definir um caminhamento sistemtico no grafo, de
modo que fique determinado qual o vrtice a ser visitado na seqncia
de visitas? Como definir um caminhamento sistemtico no grafo, de
modo que fique determinado qual o vrtice a ser visitado na seqncia
de visitas?
Slide 14
Processo Geral Seja G um grafo no qual todos os vrtices esto
inicialmente desmarcados. Seja G um grafo no qual todos os vrtices
esto inicialmente desmarcados. Inicialmente, marca-se como visitado
um vrtice v escolhido arbitrariamente. Esse vrtice inicial chamado
de raiz de busca. Inicialmente, marca-se como visitado um vrtice v
escolhido arbitrariamente. Esse vrtice inicial chamado de raiz de
busca. Seleciona-se uma aresta que parte de algum vrtice j marcado
v. Marca-se ento a aresta (v,w) como explorada e o vrtice w como
visitado (caso ainda no o seja). Seleciona-se uma aresta que parte
de algum vrtice j marcado v. Marca-se ento a aresta (v,w) como
explorada e o vrtice w como visitado (caso ainda no o seja). O
processo termina quando todas as arestas de G tiverem sido
selecionadas. O processo termina quando todas as arestas de G
tiverem sido selecionadas.
Slide 15
Processo Geral Algoritmo de busca geral: Dados: grafo G (V,E)
Escolher e marcar um vrtice inicial Enquanto existir algum vrtice v
marcado e incidente a uma aresta (v,w) no explorada, faa explorar a
aresta (v,w) se w no marcado se w no marcado ento marcar w ento
marcar w A B E EE E D DD D C
Slide 16
Processo Geral Note que durante o processo de explorao de um
vrtice possvel que ele seja alcanado diversas vezes (tantas quantas
forem o nmero de arestas incidentes). Nos critrios de busca em
profundidade e busca em largura, que veremos a seguir, a escolha do
prximo vrtice torna-se nica, mas para os casos do vrtice inicial e
aresta incidente a escolha permanece arbitrria.
Slide 17
Busca em Profundidade (Depth-First Search) Dentre todos os
vrtices marcados e incidentes a alguma aresta ainda no explorada,
escolher aquele mais recentemente alcanado na busca. Dentre todos
os vrtices marcados e incidentes a alguma aresta ainda no
explorada, escolher aquele mais recentemente alcanado na busca. Um
detalhe importante que usamos o auxlio de uma pilha para guardar os
vrtices j marcados. Um detalhe importante que usamos o auxlio de
uma pilha para guardar os vrtices j marcados.
Slide 18
Busca em Profundidade (Depth-First Search) Procedimento P
(v,pai) marcar v; colocar v na pilha Q; para toda aresta (v,w) faa
se w no marcado se w no marcado entovisitar (v,w); entovisitar
(v,w); marcar (v,w) como aresta de rvore; P(w,v); senose w pai
senose w pai ento visitar (v,w); ento visitar (v,w); marcar (v,w)
como aresta de retorno; marcar (v,w) como aresta de retorno; seno
visitar (v,w); seno visitar (v,w); marcar (v,w) como aresta de
rvore; marcar (v,w) como aresta de rvore; retirar v da pilha
retirar v da pilhafim_do_procedimento 3 1 5 6 42 Ex.
Slide 19
Busca em Profundidade (Depth-First Search) O algoritmo
particiona as arestas em: u Arestas de rvore; u Arestas de Retorno.
As arestas de rvore constituem uma rvore geradora de G. As arestas
de rvore constituem uma rvore geradora de G. As arestas de retorno,
cada uma por sua vez, liga um vrtice v a um ancestral seu. As
arestas de retorno, cada uma por sua vez, liga um vrtice v a um
ancestral seu.
Slide 20
Busca em Profundidade (Depth-First Search) v1 v1 v1 v1 Ex.:
Criar duas diferentes rvores geradoras para o grafo abaixo: v 3 v 3
v 2 v 2 v5 v5 v5 v5 v 4 v 4 v 6 v 6
Slide 21
Busca em Largura (Breadth-First Search) Dentre todos os vrtices
marcados e incidentes a alguma aresta ainda no explorada, escolher
aquele menos recentemente alcanado na busca. Dentre todos os
vrtices marcados e incidentes a alguma aresta ainda no explorada,
escolher aquele menos recentemente alcanado na busca. Um detalhe
importante que usamos o auxlio de uma fila para guardar os vrtices
j marcados. Um detalhe importante que usamos o auxlio de uma fila
para guardar os vrtices j marcados.
Slide 22
Busca em Largura (Breadth-First Search) Procedimento L (v,pai)
Procedimento L (v,pai) marcar v; marcar v; colocar v na fila Q;
colocar v na fila Q; enquanto a fila Q no for vazia faa enquanto a
fila Q no for vazia faa remover o 1 vrtice w da fila; remover o 1
vrtice w da fila; para todo (w,x) faa para todo (w,x) faa se x no
marcado se x no marcado ento marque x; ento marque x; adicione
(w,x) rvore T; adicione (w,x) rvore T; coloque x na fila Q; coloque
x na fila Q; fim_do_procedimento fim_do_procedimento 3 1 5 6 42
Ex.
Slide 23
Grafos no-conexos No caso do grafo no ser conexo o algoritmo de
busca (profundidade ou largura) ter apenas uma modificao e seguir o
seguinte critrio: No caso do grafo no ser conexo o algoritmo de
busca (profundidade ou largura) ter apenas uma modificao e seguir o
seguinte critrio: Executa-se o algoritmo a partir de um vrtice v
qualquer. Se ao trmino do procedimento restar algum vrtice do grafo
G no marcado repete-se o procedimento para este vrtice. Executa-se
o algoritmo a partir de um vrtice v qualquer. Se ao trmino do
procedimento restar algum vrtice do grafo G no marcado repete-se o
procedimento para este vrtice. c f d a b e h i g Ex.:
Slide 24
Complexidade Nos dois algoritmos de busca (largura e
profundidade) observamos que cada aresta visitada exatamente duas
vezes (uma para cada vrtice). Portanto o tempo de execuo depende do
nmero de arestas. Nos dois algoritmos de busca (largura e
profundidade) observamos que cada aresta visitada exatamente duas
vezes (uma para cada vrtice). Portanto o tempo de execuo depende do
nmero de arestas. Quando o grafo no-conexo, temos que analisar os
vrtices que no esto conectados a ningum. Assim, o tempo de execuo
tambm depende do n de vrtices. Quando o grafo no-conexo, temos que
analisar os vrtices que no esto conectados a ningum. Assim, o tempo
de execuo tambm depende do n de vrtices. Concluso: Para um grafo G
(V,E) os algoritmos de busca em largura e em profundidade tem
complexidade Concluso: Para um grafo G (V,E) os algoritmos de busca
em largura e em profundidade tem complexidade O ( |V| + |E|)
