Estrutura de Dados - Profundidade Primeiro Traversal

O algoritmo Depth First Search (DFS) percorre um gráfico em um movimento em profundidade e usa uma pilha para lembrar de obter o próximo vértice para iniciar uma pesquisa, quando um beco sem saída ocorre em qualquer iteração.

Como no exemplo dado acima, o algoritmo DFS atravessa de S para A para D para G para E para B primeiro, então para F e por último para C. Ele emprega as seguintes regras.

• Rule 1- Visite o vértice não visitado adjacente. Marque como visitado. Mostre-o. Empurre-o em uma pilha.

• Rule 2- Se nenhum vértice adjacente for encontrado, abra um vértice da pilha. (Irá aparecer todos os vértices da pilha, que não têm vértices adjacentes.)

• Rule 3 - Repita a Regra 1 e a Regra 2 até que a pilha esteja vazia.

Degrau	Travessia	Descrição
1		Inicialize a pilha.
2		Marca Sconforme visitado e colocá-lo na pilha. Explore qualquer nó adjacente não visitado deS. Temos três nós e podemos escolher qualquer um deles. Para este exemplo, tomaremos o nó em ordem alfabética.
3		Marca Aconforme visitado e colocá-lo na pilha. Explore qualquer nó adjacente não visitado de A. AmbosS e D são adjacentes a A mas estamos preocupados apenas com nós não visitados.
4		Visita De marcá-lo como visitado e colocá-lo na pilha. Aqui temosB e C nós, que são adjacentes a De ambos não são visitados. No entanto, devemos escolher novamente em ordem alfabética.
5		Nós escolhemos B, marque-o como visitado e coloque-o na pilha. AquiBnão tem nenhum nó adjacente não visitado. Então, nós popB da pilha.
6		Verificamos o topo da pilha para retornar ao nó anterior e verificamos se há algum nó não visitado. Aqui encontramosD para estar no topo da pilha.
7		Apenas o nó adjacente não visitado é de D é Cagora. Então nós visitamosC, marque-o como visitado e coloque-o na pilha.

Como Cnão tem nenhum nó adjacente não visitado, portanto, continuamos aumentando a pilha até encontrar um nó que possui um nó adjacente não visitado. Nesse caso, não há nenhum e continuamos exibindo até que a pilha esteja vazia.

Para saber mais sobre a implementação deste algoritmo na linguagem de programação C, clique aqui .