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 .