在 DAG 中查找哈密顿路径的算法

Question

我指的是斯基纳的算法书。

测试图

G

是否包含

Hamiltonian path

的问题是

NP-hard

，其中哈密顿路径

P

是访问每个顶点一次的路径。与哈密顿循环问题不同，G 中从 P 的结束顶点到起始顶点不一定有边。

给定一个有向无环图 G (

DAG

)，给出一个

O(n + m)

时间算法来测试它是否包含哈密顿路径。

我的方法，

我打算使用

DFS

和

Topological sorting

。但我不知道如何连接这两个概念来解决问题。如何使用拓扑排序来确定解决方案。

有什么建议吗？

Answer 1

可以先对 DAG 进行拓扑排序（每个 DAG 都可以进行拓扑排序），时间复杂度为 O(n+m)。

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

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

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

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

因此，整体复杂度为 O(m+n)。

Answer 2

我也尝试解决与op相同的问题，但是通过使用DFS并计算出度为0和入度为0的顶点。

1. DAG 至少有一个入度等于 0 的顶点。
2. DAG 至少有一个出度等于 0 的顶点。
3. DAG 中存在哈密顿路径当且仅当恰好存在一个入度等于 0 的顶点和一个出度等于 1 的顶点。

时间复杂度应该是O(n+m)，因为使用了DFS，其他操作都是O(1)，虽然它使用了额外的数据结构，比如数组来跟踪每个节点的出度和入度计数，但是空间复杂度仍然是 O(n)，这与跟踪访问顶点的数组相同。