我指的是Skienna的算法书。
测试图是否G
包含 a的问题Hamiltonian path
是NP-hard
,其中哈密顿路径P
是对每个顶点仅访问一次的路径。与哈密顿循环问题不同,G 中从 P 的结束顶点到起始顶点不必有一条边。
给定一个有向无环图 G( · DAG
),给出一个O(n + m)
时间算法来测试它是否包含哈密顿路径。
我的做法,
我打算使用DFS
和Topological sorting
。但是我不知道如何在解决问题时将这两个概念联系起来。如何使用拓扑排序来确定解决方案。
有什么建议么?