7

我需要找到一种算法，用于在 O(n+m) 中找到有向图中的所有根。

我有一个查找单个根的算法：

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

现在，如果我想找到所有的根，每次在最后一棵树的不同顶点上运行上述算法 O(n) 次的最佳方法是什么？假设我找到了一个根，如果另一个根存在，那么它必须在最后一棵树上，那么如果我继续运行上述算法直到收到“不存在根”或直到遍历所有顶点，它是 O(n+m) 吗？

提前致谢 ！

4

2 回答 2

5

两种方法：

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

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

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

于 2013-11-13T12:49:48.670 回答
2

首先，您应该在图中找到所有强连通分量。要在更短的时间内构建它，您可以使用Kosaraju's algorithm或Tarjan's algorithm。所有根应位于一个这样的组件中。接下来，您会找到没有传入边的强连接组件。如果您有多个这样的组件，则图没有根顶点。如果您只有一个组件，您应该检查是否可以从中访问其他组件，在这种情况下，此组件包含图中的所有根。

旧变种。

您应该计算到顶点的传入边数，这可以在 O(m) 中完成。所有传入边数为零的顶点将成为图的根，为此您将需要 O(n) 时间。

于 2013-11-13T09:47:46.163 回答