Percurso em profundidade

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ça6 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.