我指的是Skienna的算法书.
测试图是否G包含a的问题Hamiltonian path是NP-hard,哈密顿路径P是一个只访问每个顶点一次的路径.与汉密尔顿循环问题不同,从结束顶点到P的起始顶点不一定有G的边缘.
给定有向非循环图G(DAG),给出O(n + m)时间算法来测试它是否包含哈密顿路径.
我的方法,
我打算用DFS和Topological sorting.但我不知道如何将这两个概念联系起来解决问题.如何使用拓扑排序来确定解决方案.
有什么建议？
algorithm hamiltonian-cycle directed-acyclic-graphs graph-algorithm