use*_*617 26 algorithm hamiltonian-cycle directed-acyclic-graphs graph-algorithm
我指的是Skienna的算法书.
测试图是否G包含a的问题Hamiltonian path是NP-hard,哈密顿路径P是一个只访问每个顶点一次的路径.与汉密尔顿循环问题不同,从结束顶点到P的起始顶点不一定有G的边缘.
给定有向非循环图G(DAG),给出O(n + m)时间算法来测试它是否包含哈密顿路径.
我的方法,
我打算用DFS和Topological sorting.但我不知道如何将这两个概念联系起来解决问题.如何使用拓扑排序来确定解决方案.
有什么建议？
Pet*_*nov 45
您可以首先在O(n + m)中拓扑排序DAG(每个DAG可以进行拓扑排序).
完成此操作后,您就会知道边缘从较低的索引顶点到较高的索引顶点.这意味着当且仅当连续顶点之间存在边缘时才存在哈密顿路径,例如
(1,2), (2,3), ..., (n-1,n).
(这是因为在哈密尔顿路径中你不能"回去"然后你必须访问所有,所以唯一的方法是"不要跳过")
你可以在O(n)中检查这个条件.
因此,总体复杂度为O(m + n).
| 归档时间： |
|
| 查看次数： |
22803 次 |
| 最近记录： |