Teoria dos Grafos - Aula 6 - Busca por Largura e Profundidade

Prévia do material em texto

Busca solar grafos viso resolver o proteoma de como
explorar um grafo
Fixado um vértice C do grafo como definir um caminhamento
sistemático no grafo de modo quefique determinado o próximovértice
a ser visitado na sequência de visitas
Emparticular como caminhar no grafo de modo a
visitar TODOS vértices e arestas evitando repetiçõesdesnecessáriasde visitas a um mesmo vértice de arestas
Fora isso podemos criar um recurso adicional
que correspondem a um conjunto de até n marcas
se tiver um grafo de n vértices Cada marca é
associada a um vértice de grafo e registra
se o vértice foi ou não visitado
O 5
ex 1 E O O
2 F
7
3 E O s 2
o 04 f
s f 0 O4
6 f 3
7 F
s
e F 0 O
Z F
7
3 F O z
si o4 v visitei o vértice 4
s f 0 O4
6 f 3
7 F
O S
e F 0 O
Z F
7
3 F O z
r J 04 Y
s f 0 O4
6 f 3
visitei ovértice7dpsdo 4
Ideia de um algoritmo de doca geral
Seja um grafo anexo E i
Inicialize uma lista que corresponde a se um
vértice foi visitado ou não no início nenhum foi
então todos ficam False
Marca um vértice arbitrário ou da minha
convenienciacomo nó raiz ou seja a partir dele vou
explorar o grafo
No passo geral seleciona se algum vértice v
que já foi visitada e seja incidente a alguma
aresta v w ainda não selecionada
A aresta Iv w é selecionada e o vértice W
é marcada como visitado
O processo termina quando TODAS as
arestas de G tiverem sido selecionadas Esse
tipo de caminhamento é chamado Busca
sobre o grafo G
Algoritmo Busca Geral
Entrada Grafo GU E
desmarca todos os vértices
escolhe e marca um vértice inicial
enquanto existealgum vértice vmarcado e incidente
a uma aresta us não explorada faça
escolher o vértice v e exploradow
se W não foi visitado então
marca w
O que muda de método em método de busca
é COMO ESCOLHER O VÉRTICE v
BUSCA EM PROFUNDIDADE
dentre todos os vértices marcados eaincidentesa alguma aresta ainda não explorada
escolher aquele MAIS RECENTEMENTE alcançad
na busca
Algoritmo Busca Em Profundidade 0C mt n
Dados G V E conexo V né raiz
marca v
coloca v na pilha Q
para w e Alv faça
se w não é mancada então
visita v w
Pew
se não
se we Q e 4W não sãoconsecutivas em dente
visita Iv w
retirar v de a
BUSCA EM LARGURA
dentre todos os vértices marcados eincidentesa alguma aresta ainda não exploradaescolhaAquele MENOS RECENTEMENTE alcançado
na busca