在有向图中查找所有根节点

Question

我需要找到一种在O(n+m)时间内寻找有向图中所有根的算法。

我已经有了一种寻找单个根的算法：

1. 在V中的某个v上运行DFS(v)。如果结果是一个生成树，则v是一个根。否则，结果是一组树，然后： 2. 在最后一棵树的根上运行DFS(u)。如果结果是一个生成树，则u是一个根。否则，图中没有根。

现在，如果我想找到所有的根，最好的方法是仅在最后一棵树上的不同顶点上运行上述算法n次吗？假设我找到一个根，如果还存在其他根，则它必须在最后一棵树上，那么如果我继续运行上述算法直到收到“没有根存在”或者遍历所有顶点，那么复杂度是否为O(n+m)？

谢谢！

- amitooshacham

---

查找拓扑排序。但是你的问题似乎没有什么意义。术语“根”只适用于根节点。我猜你需要所有没有入边的顶点？ - Ivaylo Strandjev

假设您已经正确找到了根节点，那么您可以找到具有指向该根节点的有向路径的顶点。所有这些顶点都应该是根节点本身。或者您可以反转所有边的方向，并从找到的根节点进行DFS或BFS。遇到的所有顶点都应该是根节点本身。 - Abhishek Bansal

正如我所说的，如果你反转所有边的方向并从根节点进行DFS或BFS，则可以获得所有新的根节点。 - Abhishek Bansal

是的，反转所有边的时间复杂度为O(n)，其中n是边的数量。 - Abhishek Bansal

如果 E >> V，则 O(V+E) ~ O(E)（我们的解决方案），如果 V >> E，则 O(V+E) > O(E)，这意味着我们的解决方案已经实现了更好的复杂度。@amitooshacham - Abhishek Bansal

Answer 1

两种方法：

1. 反转图并计算DFS-loop()，注意没有出边的顶点（就像Abhishek所说的那样）。

2. 更有效率的方法 - 在图上运行DFS-loop()，并使用真假表跟踪没有入边的顶点。

在最坏情况下，方法1需要两倍的时间。

- Vikram Bhat

---

你能详细说明一下第二种方法吗？ - Abhishek Bansal

但是根据 OP 的定义，一个根节点也可以有入边。实际上，如果存在一个没有任何入边的节点，则该节点是树的唯一根节点，因为它不能从任何其他“可能的根节点”遍历到。 - Abhishek Bansal

图中可能存在多个根节点，它们没有任何入边。 - Vikram Bhat

如果你认为根节点可以有入边，那么它就是没有入边的强连通分量的一部分。因此，我们使用Kasaraju算法来将图缩小到一个可以使用2.>的图上进行操作。 - Vikram Bhat

Answer 2

首先，你应该在图中找到所有强连通分量。为了更快地构建它，你可以使用Kosaraju算法或Tarjan算法。所有的根应该位于一个这样的分量中。接下来，你要找到没有入边的强连通分量。如果你有多个这样的分量，那么图就没有根顶点。如果你只有一个分量，你应该检查是否能从它到达其他分量，在这种情况下，这些分量包含了图中的所有根。

旧版方法：

你应该计算每个顶点的入边数量，这可以在O(m)时间内完成。所有入边数量为零的顶点将成为图的根，这需要O(n)时间。

- Alexander Kuznetsov

---

我认为你混淆了“根”和“源”。除非我弄错了，根是一个节点，通过有向边可以到达每个其他节点。根本身可能有入边，并且肯定不是每个没有这样的边的节点都是根。 - tobias_k