Percurso em profundidade

Page 1

Percurso em profundidade Definição: (Depth-first search) Traça um caminho a partir de um nó inicial procurando o caminho mais longo possível a partir do mesmo(Figura 1). Esse caminho é gerado com a construção de um vetor de predecessores.

Algoritmo: Utilizamos um algoritimo similar ao utilizado no percurso em largura. Basta trocarmos a estrutura de dados para uma PILHA e tratarmos o estado na mesma dentro do algoritmo.

2 C(u) ← +∞, cor(u) ← branco, e P(u) ← nil.

3 Se u = u1 então

4 C(u) ← 0, empilha u em Q, e cor(u) ← cinza.

5 Enquanto Q 6= ∅ faça

6 Desempilha u de Q e cor(u) ← preto.

7 Para todo v ∈ A(u), tal que cor(v) != preto faça:

8 P(v) ← u e C(v) ← C(u) + 1.

9 Se cor(u) = branco, então empilha v em Q e

cor(v) ← cinza.