锦标赛是一个完整的有向图，给定任意两个顶点 u 和 v，它们之间存在一条有向边（如果 u 赢了 v，那么边是从 u 到 v）。
汉密尔顿路径总是存在于锦标赛中。因此，给定 {u:[v,w],v:[w]} 形式的邻接表，其中存在从 u 到 w、u 到 v 和 v 到 w 的有向边，我如何找到哈密顿路径是并按顺序打印顶点？
即使您不了解 python 或其他任何东西，算法也会很有帮助。我已经考虑过了，我想我必须从最高出度的顶点开始？然后添加度数第二高的顶点等，直到度数最低的顶点。但我不明白这是一种故障安全方法，最高程度的顶点可能会被第二高的顶点击败。
感谢您提前提供任何帮助！
你可以递归地解决这个问题。假设您有名为的n+1顶点。to和它们之间的边对于大小为 n 的锦标赛，所以我们可以假设我们有一条包含to的哈密顿路径。根据该路径将它们重命名为. 现在找到已经赢得并且已经赢得的这样的（这里你应该注意边缘节点：已经赢得或已经赢得）。在找到这样的 之后，整个哈密顿路径可以构造为：v_0v_nv_1v_nv_1v_nu_1u_nu_iu_iv_0v_0u_i+1v_0u_1u_nv_0i
u_1 , ... , u_i , v_0 , u_i+1 , ... , u_n
该算法的运行时间为 O(n^2)。这个问题存在 O(nlogn) 算法。