Grafos busca em profudidade

O estudo utilizando apenas este material n˜o ´ suficiente para o entendimento do a e conte´do. Recomendamos a leitura das u referˆncias no final deste material e a e resoluc˜o (por parte do aluno) de todos os ¸a exerc´ ıcios indicados.

Grafos
Busca em profundidade

Conte´do u
Introduc˜o ¸a Exemplo de execuc˜o ¸a Procedimento dfs An´lise do tempo de execuc˜o do dfs a ¸a Floresta primeiro na profundidade Propriedades Exerc´ ıcios Referˆncias e

Introduc˜o ¸a

Procurar “mais fundo” no grafo sempre que poss´ ıvel As arestas s˜o exploradas a partir do v´rtices v mais a e recentemente descoberto que ainda tem arestas inexploradas saindo dele Quando todas as arestas de v s˜o exploradas, a busca regressa a para explorar as arestas que deixam o v´rtice a partir do qual e v foi descoberto Este processo continua at´ que todos os v´rtices acess´ e e ıveis a partir da origem tenham sidos descobertos Se restarem v´rtices n˜o descobertos, a busca se repetir´ para e a a estes v´rtices e

4 / 34

Introduc˜o ¸a

Durante a execuc˜o do algoritmo, diversos atributos s˜o ¸a a definidos para os v´rtices e Quando um v´rtice v ´ descoberto a partir de um v´rtice u, o e e e campo predecessor v .π = u ´ definido e Cada v´rtice ´ inicialmente branco, o v´rtice ´ marcado de e e e e cinza quando ´ descoberto e marcado de preto quando ´ e e terminado (sua lista de adjacˆncias ´ completamente e e examinada) Cada v´rtice tem dois carimbos de tempo v .d (quando o e v´rtice ´ descoberto) e v .f (quando o v´rtice ´ terminado) e e e e

5 / 34

Exemplo de execuc˜o ¸a

6 / 34

Exemplo de execuc˜o ¸a

7 / 34

Exemplo de execuc˜o ¸a

8 / 34

Exemplo de execuc˜o ¸a

9 / 34

Exemplo de execuc˜o ¸a

10 / 34

Exemplo de execuc˜o ¸a

11 / 34

Exemplo de execuc˜o ¸a

12 / 34

Exemplo de execuc˜o ¸a

13 / 34

Exemplo de execuc˜o ¸a

14 / 34

Exemplo de execuc˜o ¸a

15 / 34

Exemplo de execuc˜o ¸a

16 / 34

Exemplo de execuc˜o ¸a

17 /