Seminário sobre Busca em Grafos.................................................... Antonio Dirceu...
Preview:
Citation preview
- Slide 1
- Slide 2
- 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|)
- Slide 25
-
Concluso.....................................................