Mam na myśli książkę Skienny o algorytmach.

Problem testowania czy wykresG zawiera aHamiltonian path jestNP-hard, gdzie ścieżka HamiltonaP to ścieżka, która odwiedza każdy wierzchołek dokładnie raz. Nie musi być krawędzi G od wierzchołka końcowego do wierzchołka początkowego P, w przeciwieństwie do problemu cyklu Hamiltona.

Biorąc pod uwagę ukierunkowany wykres acykliczny G (DAG), daćO(n + m) algorytm czasu do sprawdzenia, czy zawiera ścieżkę Hamiltona.

Moje podejście,

Mam zamiar użyćDFS iTopological sorting. Ale nie wiedziałem, jak połączyć te dwie koncepcje w rozwiązaniu problemu. W jaki sposób można użyć sortowania topologicznego do ustalenia rozwiązania.

Jakieś sugestie?