在DAG中寻找哈密顿路径的算法 [英] Algorithm for finding a Hamiltonian Path in a DAG
本文介绍了在DAG中寻找哈密顿路径的算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我指的是斯凯耶纳关于算法的书。
测试图G
是否包含Hamiltonian path
的问题是NP-hard
,其中哈密尔顿路径P
是指恰好访问每个顶点一次的路径。与哈密尔顿循环问题不同,G中从P的结束顶点到起始顶点不一定要有一条边。
给定一个有向无圈图G(DAG
),给出一个O(n + m)
时间算法来测试它是否包含哈密顿路。
我的方法
我计划使用DFS
和Topological sorting
。但我不知道在解决问题时如何将这两个概念联系起来。如何使用拓扑排序来确定解决方案。
有什么建议吗?
推荐答案
您可以首先在O(n+m)中对DAG进行拓扑排序(每个DAG都可以进行拓扑排序)。
一旦完成,您就知道边从较低的索引顶点到较高的索引顶点。 这意味着当且仅当连续顶点之间有边时,才存在哈密顿路径,例如
(1,2), (2,3), ..., (n-1,n).
(这是因为在哈密尔顿路径中,你不能"返回",但你必须访问所有,所以唯一的方法是"不跳过")
您可以在O(N)中检查此条件。
因此,总体复杂度为O(m+n)。
这篇关于在DAG中寻找哈密顿路径的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文