根据玩家对决结果建立排行榜
Build top-list from player-player duel result
我有一个玩家之间的决斗列表。数据由2个用户ID组成，第一个为获胜者。
我如何构建此列表的图表以找到最佳球员？
此外，我如何决定什么是最好的？
也许玩家应该根据击败的对手数量和这些对手的排名（递归）进行排名。
我之前曾尝试使用 PageRank 算法来做到这一点，但它并没有很好地解释损失（即排名应该从损失中下降）。
例如：
1 won against 3
1 won against 4
1 won against 5
2 won against 1
这个列表应该把 2 放在首位，因为它打败了 1。
这提出了一个问题——应该要求与高等级的人决斗。
那些没有与特定等级以上的玩家决斗的人应该被告知这样做，以便进入榜单。
将玩家 X 击败玩家 Y 定义为存在顶点 X 和 Y 并且存在 从 Y 到 X 的边。
然后，在处理完所有游戏信息后，你可以运行 DFS在图上，在某个数组A中记录你无法遍历的节点更深。
由于您没有指定给定的图是树，同时考虑到边是有向的，不能保证从任何节点开始的 DFS 都会收敛到单个根，所以您需要保留某种类型的节点列表，这些节点 击败 其他节点。
完成初始遍历后，反转所有边，并且 运行 森林中每棵树的 DFS 是您的图形，每棵树的根是 A 中的一个元素。当您遍历树时以A[i]为根，在每个节点中记录其所在的深度，相对于根节点A[i].
然后，根据您对 top 玩家的定义，您可以遍历 A 中的根并尽可能深入该定义，挑选您遇到的每个元素。如果您需要的最终列表实际上应该对 A 中不同根的节点后代进行排序，您可以使用深度作为比较标准对将包含列表的最终结构进行排序。除了我提到的最终排序之外，到目前为止我们所做的都是 DFS，这种方法是 O(V+E)，V 是顶点数，E 是边数.如果考虑到不同树中元素的排序，那么总体复杂度为 O((V+E) + VlogV).
如果您愿意牺牲更多的性能，那么您可以将 A 中的根连接到全局根 R（即，将节点 R 添加到图中，将 R 的边添加到每个 A[i]）并且运行 Dijkstra 算法，首先访问深度较小的节点，然后根据您对 top 的定义，基本上将每个访问过的节点附加到您的列表中，直到您认为列表足够大为止球员.
请注意，如果图中有循环，则此解决方案不起作用，无论您是使用 DFS 还是 Dijkstra 进行最终遍历。但是，它可以通过使用具有正权重的边来适应具有多个匹配项的玩家。从 X 到 Y 的权重为 k 的边将指示 X 击败 Y 的次数，您在使用 DFS 遍历期间更新节点深度时将考虑到这一点。
我有一个玩家之间的决斗列表。数据由2个用户ID组成，第一个为获胜者。
我如何构建此列表的图表以找到最佳球员？
此外，我如何决定什么是最好的？ 也许玩家应该根据击败的对手数量和这些对手的排名（递归）进行排名。 我之前曾尝试使用 PageRank 算法来做到这一点，但它并没有很好地解释损失（即排名应该从损失中下降）。
例如：
1 won against 3
1 won against 4
1 won against 5
2 won against 1
这个列表应该把 2 放在首位，因为它打败了 1。
这提出了一个问题——应该要求与高等级的人决斗。 那些没有与特定等级以上的玩家决斗的人应该被告知这样做，以便进入榜单。
将玩家 X 击败玩家 Y 定义为存在顶点 X 和 Y 并且存在 从 Y 到 X 的边。
然后，在处理完所有游戏信息后，你可以运行 DFS在图上，在某个数组A中记录你无法遍历的节点更深。 由于您没有指定给定的图是树，同时考虑到边是有向的，不能保证从任何节点开始的 DFS 都会收敛到单个根，所以您需要保留某种类型的节点列表，这些节点 击败 其他节点。
完成初始遍历后，反转所有边，并且 运行 森林中每棵树的 DFS 是您的图形，每棵树的根是 A 中的一个元素。当您遍历树时以A[i]为根，在每个节点中记录其所在的深度，相对于根节点A[i].
然后，根据您对 top 玩家的定义，您可以遍历 A 中的根并尽可能深入该定义，挑选您遇到的每个元素。如果您需要的最终列表实际上应该对 A 中不同根的节点后代进行排序，您可以使用深度作为比较标准对将包含列表的最终结构进行排序。除了我提到的最终排序之外，到目前为止我们所做的都是 DFS，这种方法是 O(V+E)，V 是顶点数，E 是边数.如果考虑到不同树中元素的排序，那么总体复杂度为 O((V+E) + VlogV).
如果您愿意牺牲更多的性能，那么您可以将 A 中的根连接到全局根 R（即，将节点 R 添加到图中，将 R 的边添加到每个 A[i]）并且运行 Dijkstra 算法，首先访问深度较小的节点，然后根据您对 top 的定义，基本上将每个访问过的节点附加到您的列表中，直到您认为列表足够大为止球员.
请注意，如果图中有循环，则此解决方案不起作用，无论您是使用 DFS 还是 Dijkstra 进行最终遍历。但是，它可以通过使用具有正权重的边来适应具有多个匹配项的玩家。从 X 到 Y 的权重为 k 的边将指示 X 击败 Y 的次数，您在使用 DFS 遍历期间更新节点深度时将考虑到这一点。