我指的是Skienna的算法书。
测试图形是否G包含a的问题Hamiltonian path是NP- hard，其中汉密尔顿路径P是只访问每个顶点一次的路径。与哈密顿循环问题不同，从终点P到起点P不必在G中有边。
G
Hamiltonian path
NP- hard
P
给定有向无环图G（DAG），请给出一个O(n + m)时间算法来测试其是否包含哈密顿路径。
DAG
O(n + m)
我的方法
我打算使用DFS和Topological sorting。但是我不知道如何将两个概念联系起来解决问题。如何使用拓扑排序来确定解决方案。
DFS
Topological sorting
有什么建议？
您可以先对DAG进行拓扑排序（每个DAG可以进行拓扑排序），形式为O（n + m）。
完成此操作后，您将知道边缘从较低的索引顶点变为较高的顶点。这意味着当且仅当连续顶点之间存在边时，才存在哈密顿路径，例如
(1,2), (2,3), ..., (n-1,n).
（这是因为在哈密顿式道路上，您不能“返回”，但您必须参观全部，因此唯一的方法是“不跳过”）
您可以在O（n）中检查此条件。
因此，总体复杂度为O（m + n）。
