Aula 04 Busca em Grafos

Busca em Grafos
Teoria dos Grafos
Introduo
Os objetivos da busca so:

determinar quais vrtices so alcanveis atravs de um vrtice inicial... Se um determinado objeto est presente no grafo...
Busca em Grafos
Prof. Humberto Brando humberto@unifal-mg.edu.br aula disponvel no site: http://www.dcc.ufmg.br/~humberto/
Universidade Federal de Alfenas Departamento de Cincias Exatas verso da aula: 0.1
Aplicaes???
Busca em Grafos
Aplicaes:
Compiladores; Resoluo de problemas p (xadrez, ( por p exemplo); p ) Roteamento de Veculos; Funo localizar arquivo no sistema operacional; Deteco de deadlocks.
Busca em Grafos
Adaptaes nos algoritmos de busca nos permitem construir algoritmos para os problemas de:
rvore Geradora Mnima (AGM); Caminho Mnimo; Componentes Fortemente Conectados; Ordenao Topolgica.
Busca em Grafos
Algoritmos clssicos de Busca: Busca em Largura; Busca B em Profundidade; P f did d Backtracking; Backtracking com backjumping;
Busca em Profundidade
A busca em profundidade (do ingls depth-first search DFS) um algoritmo para caminhar no grafo; Seu ncleo se concentra em buscar, sempre que possvel, o mais fundo no grafo. grafo As arestas so exploradas a partir do vrtice v mais recentemente descoberto que ainda possui arestas no exploradas saindo dele.
Quando todas arestas adjacentes a v tiverem sido exploradas, a busca anda para trs (do ingls backtrack) para explorar vrtices do qual v foi descoberto; O processo continua at que sejam descobertos todos os vrtices que so alcanveis a partir do vrtice original; Se todos os vrtices j foram descobertos, ento o fim. Caso contrrio o processo continua a partir de um novo vrtice de origem ainda no descoberto (grafos desconexos).
Legenda para algoritmo:
Vrtice Branco Ainda no visitado... Vrtice cinza Visitado, mas seus adjacentes ainda no foram todos visitados; Vrtice preto Visitado, e seus adjacentes j foram todos visitados.
DFS (G ) 1 para cada vrtice u V [G ] 2 cor[u ] BRANCO 3 tempo 0 4 para cada vrtice u V [G ]
5 6 se cor[u ] = BRANCO DFS VISIT (u ) DFS VISIT (u ) 1 cor[u ] CINZA 2 tempo tempo + 1 3 d [u ] tempo 4 para cada d vrtice v Adj Ad (u ) 5 6 se cor[v] = BRANCO DFS VISIT (v)
7 cor[u ] PRETO 8 f [u ] tempo (tempo + 1)
Legenda
Dado um Grafo, temos uma lista de todos os vrtices:
d: marcador do instante que o vrtice c foi encontrado; f: marcador do instante que os fecho transitivo do vrtice c foi totalmente visitado.
ltima ao: Vrtice c encontrado
ltima ao: Vrtice g encontrado
Contador = 1
Contador = 2
ltima ao: Vrtice f encontrado
ltima ao: Vrtice f finalizado
Contador = 3
Contador = 4
ltima ao: Vrtice h encontrado
ltima ao: Vrtice h finalizado
Contador = 5
Contador = 6
ltima ao: Vrtice g finalizado
ltima ao: Vrtice d encontrado
Contador = 7
Contador = 8
ltima ao: Vrtice d finalizado
ltima ao: Vrtice c finalizado
Contador = 9
Contador = 10
ltima ao: Capturando o prximo vrtice da lista de vrtices disponveis no grafo
ltima ao: Vrtice a encontrado
Contador = 10
Contador = 11
ltima ao: Vrtice b encontrado
ltima ao: Vrtice e encontrado
Contador = 12
Contador = 13
ltima ao: Vrtice e finalizado
ltima ao: Vrtice b finalizado
Contador = 14
Contador = 15
ltima ao: Vrtice a finalizado
ltima ao: Capturando os prximos vrtices disponveis. Ser verificado que todos foram visitados pela busca!!!
Contador = 16
Contador = 16
Se voc fosse implementar busca em profundidades, qual representao computacional escolheria?
Matriz de Adjacncia; Matriz de Incidncia; Lista de Adjacncia;
Estes slides esto disponveis no endereo: http://www.dcc.ufmg.br/~humberto/ Bibliografia recomendada para esta aula:
Algoritmos Teoria e Prtica, Traduo da 2 edio. Thomas H. Cormen, Charles E. E Leiserson, Leiserson Ronald L. L Rivest, Rivest Clifford Stein. Stein 2002, 2002 936 pp. pp Editora Campus/Elsevier, ISBN 8535209263.
Por qu?

Aula 04 Busca em Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

Aula 04 Busca em Grafos

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula 04 Busca em Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

Busca em Grafos

Teoria dos Grafos

Os objetivos da busca so:

7 cor[u ] PRETO 8 f [u ] tempo (tempo + 1)

Você também pode gostar