Estou me referindo ao livro de Skienna sobre algoritmos.

O problema de testar se um gráficoG contém umHamiltonian path éNP-hard, onde um caminho hamiltonianoP é um caminho que visita cada vértice exatamente uma vez. Não tem que haver uma borda em G do vértice final ao vértice inicial de P, ao contrário do problema do ciclo hamiltoniano.

Dado um gráfico acíclico dirigido G (DAG), dê umaO(n + m) algoritmo de tempo para testar se contém ou não um caminho hamiltoniano.

Minha abordagem,

Estou planejando usarDFS eTopological sorting. Mas eu não sabia como conectar os dois conceitos na solução do problema. Como um tipo topológico pode ser usado para determinar a solução.

Alguma sugestão?