8/2/2019 Busca Em Profundidade

1/28

Clique para editar o estilo do subttulomestre

4/28/12

Universidade Federal de UberlndiaMestrado em Inteligncia Artificial

Busca em Profundidade

DFS

Autor: Danilo Ziza Alves

Orientador: Prof. Dr. Carlos Lopes

Uberlndia, 15 de maro de 201211

8/2/2019 Busca Em Profundidade

2/28

4/28/12

Busca em Profundidade(Depth-First Search DFS)

O algoritmo DFS realiza umabusca que progride atravs da

expanso do primeiro n (raiz) ese aprofunda cada vez mais, atque o alvo seja encontrado, ou at

que se depare com um n folha,da a busca retrocede (backtrack)e recomea no prximo n.

22

8/2/2019 Busca Em Profundidade

3/28

4/28/12 33

8/2/2019 Busca Em Profundidade

4/28

4/28/12 44

8/2/2019 Busca Em Profundidade

5/28

4/28/12 55

8/2/2019 Busca Em Profundidade

6/28

4/28/12 66

8/2/2019 Busca Em Profundidade

7/28

4/28/12 77

8/2/2019 Busca Em Profundidade

8/28

4/28/12 88

8/2/2019 Busca Em Profundidade

9/28

4/28/12 99

8/2/2019 Busca Em Profundidade

10/28

4/28/12 1010

8/2/2019 Busca Em Profundidade

11/28

4/28/12 1111

8/2/2019 Busca Em Profundidade

12/28

4/28/12 1212

8/2/2019 Busca Em Profundidade

13/28

4/28/12 1313

8/2/2019 Busca Em Profundidade

14/28

8/2/2019 Busca Em Profundidade

15/28

4/28/12 1515

8/2/2019 Busca Em Profundidade

16/28

4/28/12 1616

8/2/2019 Busca Em Profundidade

17/28

4/28/12 1717

8/2/2019 Busca Em Profundidade

18/28

4/28/12 1818

Estrutura do N

8/2/2019 Busca Em Profundidade

19/28

4/28/12 1919

Empilha e Desempilha

8/2/2019 Busca Em Profundidade

20/28

4/28/12 2020

Exemplo

8/2/2019 Busca Em Profundidade

21/28

4/28/12 2121

Exemplo

8/2/2019 Busca Em Profundidade

22/28

4/28/12 2222

Executando

8/2/2019 Busca Em Profundidade

23/28

4/28/12 2323

Mtodo de Busca

8/2/2019 Busca Em Profundidade

24/28

4/28/12 2424

Resultado

8/2/2019 Busca Em Profundidade

25/28

4/28/12

Resultado

Caminho Percorrido

A B D E C F

Alvo F encontrado

2525

8/2/2019 Busca Em Profundidade

26/28

4/28/12

Propriedades

Efeito Backtrack: O algoritmoretrocede um nvel quando atingeum n folha ou quando todos o nsfilhos j foram analisados.

Formao de uma pilha sendoque no topo da pilha estar oelemento mais profundo.

2626

8/2/2019 Busca Em Profundidade

27/28

4/28/12

Aplicaes

Busca de articulao: Um vrticeem um grafo no direcionadosimples e conexo umaarticulao se sua remoo torna ografo resultante desconexo.

Importante, por exemplo, paraidentificar os pontos frgeis deuma rede de com utadores. 2727

8/2/2019 Busca Em Profundidade

28/28

4/28/12 28

Aplicaes