Motivation

O DFS explora um grafo comprometendo-se com um caminho e seguindo-o o mais longe possível, depois retrocedendo (backtracking) até o último vértice com um vizinho não explorado.

Por que aprender DFS?

• Fundamental: ele serve de base para detecção de ciclos, ordenação topológica, componentes conectados e muitos outros algoritmos.
• Simples e barato: ele executa em tempo O(V + E) usando uma pilha (ou recursão) e um marcador de visitado.
• Versátil: a mesma travessia responde a perguntas como "esses dois vértices estão conectados?" e "quantas partes separadas o grafo possui?"

Para manter os resultados previsíveis, sempre visitamos os vizinhos de um vértice em ordem crescente.