我指的是Skienna的书算法。
测试图是否问题G包含Hamiltonian path是NP-hard ，其中哈密尔顿路径P是访问每个顶点恰好一次的路径。 有不必是从结束顶点G中的边缘，以P的起始顶点，不像在哈密顿周期的问题。
给定一个有向非循环图G（ DAG ），得到O(n + m)时间算法来测试它是否包含一个汉弥尔顿路径。
我的方法，
我打算使用DFS和Topological sorting 。 但我不知道如何将两个概念连接解决问题。 如何才能拓扑排序来确定解决方案。
有什么建议？
你可以先拓扑排序DAG（DAG每次可拓扑排序）在O（N + M）。
一旦做到这一点，你知道，从边缘低指数的顶点去更高。 这意味着，当且仅当有连续的顶点之间，例如边缘存在一个汉弥尔顿路径
(1,2), (2,3), ..., (n-1,n).
（这是因为在哈密尔顿路径，你不能“回头”，但你必须访问所有，所以唯一的办法就是“不跳过”）
您可以检查在O（n）的这个条件。
因此，整体复杂度为O（M + N）。
我不认为通过@agassaa的说法是完全正确的。 考虑简单示例，其中有三个节点 “A”， “B”， “C”，和边缘A-> B，B-> C，A->℃。 虽然A有两个孩子和C有两个父母，A-> B-> -C形成一个哈密顿路径。 你并不需要遍历每个边缘在图中的是哈密尔顿路径。
有哈密顿圈一个DAG
