35

我指的是Skienna的算法书。

测试图是否G包含 a的问题Hamiltonian pathNP-hard,其中哈密顿路径P是对每个顶点仅访问一次的路径。与哈密顿循环问题不同,G 中从 P 的结束顶点到起始顶点不必有一条边。

给定一个有向无环图 G( · DAG),给出一个O(n + m)时间算法来测试它是否包含哈密顿路径。

我的做法,

我打算使用DFSTopological sorting。但是我不知道如何在解决问题时将这两个概念联系起来。如何使用拓扑排序来确定解决方案。

有什么建议么?

4

1 回答 1

58

您可以首先在 O(n+m) 中对 DAG 进行拓扑排序(每个 DAG 都可以进行拓扑排序)。

完成此操作后,您就知道边从较低的索引顶点到较高的索引顶点。这意味着当且仅当连续顶点之间存在边时,才存在哈密顿路径,例如

(1,2), (2,3), ..., (n-1,n).

(这是因为在哈密顿路径中你不能“返回”但你必须访问所有,所以唯一的方法是“不跳过”)

您可以在 O(n) 中检查此条件。

因此,总体复杂度为 O(m+n)。

于 2013-04-20T20:31:50.623 回答