在具有 Python 中的邻接列表的锦标赛中找到哈密顿路径
Find a Hamiltonian Path on a tournament with adjacency lists in Python
锦标赛是一个完整的有向图，给定任意两个顶点 u 和 v，它们之间存在有向边（如果 u 赢了 v，则边从 u 到 v）。
哈密顿路径总是存在于锦标赛中。因此，给定 {u:[v,w],v:[w]} 形式的邻接列表，其中存在从 u 到 w、u 到 v 和 v 到 w 的有向边，我如何找到哈密顿路径是并按顺序打印顶点？
即使您不知道 python 或其他任何知识，算法也会非常有帮助。我考虑了一下，我想我必须从最高出度的顶点开始？然后将具有第二高度数的顶点等添加到具有最低度数的顶点。但我不明白这是一种故障安全方法，度数最高的顶点可能会被次高的顶点打败。
提前感谢您的帮助！
你可以递归地解决这个问题。假设您有 n+1 个名为 v_0 到 v_n 的顶点。 v_1 到 v_n 以及它们之间的边，用于规模为 n 的锦标赛，因此我们可以假设我们有一条包含 v_1 到 v_n 的哈密尔顿路径。根据该路径将它们重命名为 u_1 到 u_n。现在找到 u_i 使得 u_i 赢得了 v_0 并且 v_0 赢得了 u_i+1（这里你应该注意边缘节点：v_0 赢得了 u_1 或 u_n 赢得了 v_0）。找到这样的i后，整体哈密顿路径可以构造为：
u_1 , ... , u_i , v_0 , u_i+1 , ... , u_n
该算法的运行时间为 O(n^2)。这个问题存在 O(nlogn) 算法。
锦标赛是一个完整的有向图，给定任意两个顶点 u 和 v，它们之间存在有向边（如果 u 赢了 v，则边从 u 到 v）。
哈密顿路径总是存在于锦标赛中。因此，给定 {u:[v,w],v:[w]} 形式的邻接列表，其中存在从 u 到 w、u 到 v 和 v 到 w 的有向边，我如何找到哈密顿路径是并按顺序打印顶点？
即使您不知道 python 或其他任何知识，算法也会非常有帮助。我考虑了一下，我想我必须从最高出度的顶点开始？然后将具有第二高度数的顶点等添加到具有最低度数的顶点。但我不明白这是一种故障安全方法，度数最高的顶点可能会被次高的顶点打败。
提前感谢您的帮助！
你可以递归地解决这个问题。假设您有 n+1 个名为 v_0 到 v_n 的顶点。 v_1 到 v_n 以及它们之间的边，用于规模为 n 的锦标赛，因此我们可以假设我们有一条包含 v_1 到 v_n 的哈密尔顿路径。根据该路径将它们重命名为 u_1 到 u_n。现在找到 u_i 使得 u_i 赢得了 v_0 并且 v_0 赢得了 u_i+1（这里你应该注意边缘节点：v_0 赢得了 u_1 或 u_n 赢得了 v_0）。找到这样的i后，整体哈密顿路径可以构造为：
u_1 , ... , u_i , v_0 , u_i+1 , ... , u_n
该算法的运行时间为 O(n^2)。这个问题存在 O(nlogn) 算法。