图论：在竞赛图中找到获胜者的算法（如果有）

Question

图论：在竞赛图中找到获胜者的算法（如果有）

6

在锦标赛图中，如何找到是否存在一位玩家支配了所有其他玩家？这样的算法的运行时间是多少？

基本上，我需要找到一个元素，从该元素出发，沿着出链的路径可以到达所有其他元素。

澄清：如果'a'击败了'b'，'b'又打败了'c'，那么'a'就支配了'c'。基本上，如果'a'直接或间接地击败了'c'，它就支配了'c'。也可能存在'a'和'b'互相间接支配的情况，这就是为什么胜者可能存在也可能不存在的原因。还可能有多个获胜者。

锦标赛图是一个有向图，其中每个元素都与其余元素之一具有有向边。因此，有n*(n-1)/2个有向边，其中n是顶点（玩家）的数量。锦标赛图维基百科文章

- dc95

那么“赢家”是指统治了最多玩家的人？ - Thomas Jungblut

@ThomasJungblut 胜利者是那个支配了所有选手的人。我想找出比赛中是否有这样的选手；如果有，他是谁。 - dc95

所以，如果从A到B有一条边，表示A战胜了B，那么你可以简单地计算出从A指向外部的链接数量，并检查它是否等于顶点数|V|-1。我有遗漏什么吗？ - Thomas Jungblut

@ThomasJungblut A也可以间接地支配B。比如，A打败了C，C打败了D，而D又打败了B。基本上，我想找到一个元素，通过它的出链路径可以到达所有其他元素。我会更新问题。 - dc95

明白了，感谢澄清。 - Thomas Jungblut

在这种情况下，我认为您可以先计算图的强连通分量（即凝聚体，我们将其称为 G）。如果 G 中只有 1 个入度为 0 的顶点，并且它由原始（未浓缩）图中的单个顶点组成，则该顶点是支配其他顶点的顶点。算法的顺序是查找凝聚体的顺序（可以在 O(V+E) 的时间内计算出来）。在一般情况下，如果 G 中只有 1 个入度为 0 的顶点，则您可以从该顶点到达原始图中的所有其他顶点。 - ale64bit

3个回答

2

一种方法是针对每个顶点，以该顶点为根进行深度优先搜索图。对于每次深度优先搜索，您都需要检查是否已访问了所有其他顶点。如果是，则与该顶点对应的玩家支配图中的所有玩家。如果您熟悉C ++，我可以在此处编写程序。时间复杂度约为O（N ^ 3）。您需要更快的算法吗？其中N是顶点数。

- Bogdan Pop

这样不会使复杂度变成O(N^3)吗？DFS的运行时间已经是O(V+E) = O(N^2 + N) = O(N^2)了。如果你对所有元素都这样做，那就变成了O(N^3)。我希望得到一个O(N^2)的解决方案。 - dc95

1

如果有一个玩家主宰了其他所有玩家，那么图中存在恰好一个没有入边的顶点v。从v开始进行深度优先搜索。如果可以到达每个其他顶点，则v是主导顶点。

编辑1：正如kaktusito建议的那样，在应用DFS之前，我们可以压缩图形。

编辑2：看起来没有必要明确计算所有连接的组件，应用压缩，构造DAG并找到主导顶点。相反，这里有一个更简单的解决方案：

首先在图上执行DFS并找到具有最高完成时间的节点v。如果图有获胜者，则v必须是其中之一。否则，将会有另一个顶点u，使得v可以从u到达，并且u具有较晚的完成时间。现在，要查找其他获胜者，请在转置图中查找所有可从v到达的节点，使用从v开始的DFS或BFS。此算法的复杂度仍为O（V + E），但实现（和常数）要简单得多。

- krjampani

你不需要为所有元素都这样做。因为你想找到那个已经支配了其他所有人的玩家，所以你只需要查看入度为0的顶点。此外，如果存在多个这样的顶点，则我们知道没有一个玩家完全支配了其他所有人。因此，如果有解存在，应该恰好有一个顶点v，它的入度为0，并且从它可以到达每个其他顶点。因此，我们只需要从v开始进行一次DFS即可。 - krjampani

1

假设A打败B，B打败C，C打败A。在这种情况下，它们三个都不具有入度为0，但是它们三个都是赢家，因为从任何一个元素都可以到达其他两个元素。我认为你所说的只有在图的凝聚后才会成立。凝聚后，图将是无环的。 - dc95

由于我认为在那种情况下不会有获胜者，所以我曲解了问题。你是正确的，我们需要在压缩后的图上运行DFS算法。 - krjampani

我在实现压缩算法方面遇到了问题。你能给我一些相关资源吗？ - dc95

请查看Kosaraju算法以查找强连通分量：http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm。一旦您找到这些分量，您必须将它们缩成单个顶点以获得DAG。 - krjampani

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ale64bit · Accepted Answer

我们称原始图为T，其中包含N个顶点和M条边。首先计算T的强连通分量，并将其称为G。每个G的顶点v代表T中的多个顶点。此外，你可以从任何一个顶点到达另一个顶点，G是一个DAG。因此，如果G中只有一个入度为0的顶点（称之为v0），那么这意味着你可以从v0中的一个顶点开始访问原始图中的任何顶点。如果v0对应于T中的单个顶点，则它已经是你要查找的顶点了。该算法的复杂度为O(N+M)。