算法在DAG中寻找一个Hamilton路 [英] Algorithm for finding a Hamilton Path in a DAG

问题描述

我指的是Skienna图书的算法。

I am referring to Skienna's Book on Algorithms.

测试的问题图表是否包含汉弥尔顿路径是 NP-硬，其中汉弥尔顿路径 P 是访问每个顶点恰好一次的路径。有不必是G中从结束顶点的边缘到P的起始顶点，不像在汉密尔顿的周期问题

The problem of testing whether a graph G contains a Hamiltonian path is NP-hard, where a Hamiltonian path P is a path that visits each vertex exactly once. There does not have to be an edge in G from the ending vertex to the starting vertex of P , unlike in the Hamiltonian cycle problem.

由于有向无环图G（ DAG ），举一个 O（N + M）时间算法测试是否包含了哈密尔顿路径。

Given a directed acyclic graph G (DAG), give an O(n + m) time algorithm to test whether or not it contains a Hamiltonian path.

我的做法，

我打算使用 DFS 和拓扑排序。但我不知道如何连接解决问题的两个概念。如何能拓扑排序可以用于确定该溶液中。

I am planning to use DFS and Topological sorting. But I didn't know how to connect the two concepts in solving the problem. How can a topological sort be used to determine the solution.

有什么建议？

推荐答案

您可以先拓扑排序DAG（每个DAG可拓扑排序）在O（N + M）。

You can first topologically sort the DAG (every DAG can be topologically sorted) in O(n+m).

一旦做到这一点，你知道，边缘由低指数的顶点去更高。 这意味着，当且仅当有连续的​​顶点，例如，边缘之间存在一个汉弥尔顿路径

Once this is done, you know that edge go from lower index vertices to higher. This means that there exists a Hamiltonian path if and only if there are edge between consecutive vertices, e.g.

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

（这是因为在哈密尔顿路径，你不能回头，但你要访问的所有，所以唯一的办法就是不跳）

(This is because in a Hamiltonian path you can't "go back" and yet you have to visit all, so the only way is to "not skip")

您可以检查此条件为O（n）。

You can check this condition in O(n).

因此​​，总的复杂度为O（M + N）。

Thus, the overall complexity is O(m+n).

这篇关于算法在DAG中寻找一个Hamilton路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！