在有向无环图中寻找哈密顿路径的算法

Question

我正在参考斯基纳（Skienna）的算法书。

测试一个图 G 是否包含一条哈密顿路径是一个NP难题，其中哈密顿路径 P 是经过每个顶点一次的路径。与哈密顿回路问题不同，G 中不必从 P 的结束顶点到起始顶点有一条边。

给定一个有向无环图 G (DAG)，设计一个 O(n + m) 时间复杂度的算法来检测它是否包含哈密顿路径。

我的方法是使用 深度优先搜索(DFS) 和 拓扑排序。但我不知道如何将这两个概念连接起来解决问题。如何使用拓扑排序来确定解决方案。

有建议吗？

- user2302617

Answer 1

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

一旦完成拓扑排序，你就会知道边从较低索引顶点指向较高的顶点。这意味着存在汉密尔顿路径当且仅当相邻顶点之间有边相连，例如：

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

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

你可以在O(n)时间内检查这个条件。

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

- Petar Ivanov

---

但是您假设图是连通的，难道不可能对具有不连通部分的图进行拓扑排序吗？ - shinzou

我并不假设图是连通的。如果图不连通，那么就没有哈密顿回路，这个算法会检测出来，因为至少一个相邻顶点不连通（否则图就是连通的）。 - Petar Ivanov

同时考虑哈密顿回路、欧拉路径和欧拉回路怎么样？ - Kiran Baktha

我正在尝试解决这个问题，并想出了以下解决方案：

1. 对有向无环图进行拓扑排序。
2. 从有向无环图中的一个源组件开始运行深度优先搜索（DFS）。
3. 如果DFS树中最大的前序号等于|V|，则存在这样一条路径。

这样说清楚了吗？我对图还是相当新手... - Turambar

Answer 2

我也尝试解决和楼主一样的问题，但是我使用了深度优先搜索（DFS）并计算了出度为0且入度为0的顶点的数量。

1. 有向无环图（DAG）至少有一个入度为0的顶点。
2. 有向无环图（DAG）至少有一个出度为0的顶点。
3. 如果有向无环图（DAG）存在哈密顿路径，那么必须恰好有一个入度为0的顶点和一个出度为0的顶点。

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

- baccano01