在有向图中查找可达顶点

Question

我想请教以下问题：

给定一个有向图（不一定是 DAG），对于每个顶点 v 计算 v 的可达顶点数。

所以使用蛮力方法（n 倍 DFS）我们可以在 O(n^2) 时间复杂度内得到答案。有没有办法更快地计算它？我绝对可以使用 SCC 从给定的图中制作 DAG。我尝试使用以前计算的值，因此我只能访问每个顶点一次，但它根本不起作用。最大的问题在于这样的图表：

  2 -> 1
  3 -> 2
  3 -> 1
  1 -> 4

我运行来自顶点 1 的 DFS 和 return 结果 1。然后，使用它我可以立即计算 2 的答案（我没有在第二个 DFS 中再次输入顶点 1，我使用它的答案），什么是 2。然后我到达顶点 3，并且...算法将对 1 和 2 的结果求和，因为我可以到达这两个顶点。但是顶点 1 已经计算在顶点 2 的结果中。这样我得到的答案等于 4，这是不正确的。

Answer 1

我真的怀疑没有已知的更好的通用图算法。我找到的关于主题 [1] [2] 的所有论文都描述了在 O(|V| * |E|) 时间内运行的算法。

维基百科页面 [3] 说最快的算法将问题简化为矩阵乘法。

[1] http://ion.uwinnipeg.ca/~ychen2/conferencePapers/tranRelationCopy.pdf

[2]http://www.vldb.org/conf/1988/P382.PDF

[3] http://en.wikipedia.org/wiki/Transitive_closure#Algorithms

Answer 2

我认为最好的算法运行 O(|V| * |E|).

算法：

1 - 对图表执行 SCC。

2 - 构建简化图 Gr.

3 - 运行 Gr 中的每个顶点 v 一个 dfs并且对于每个访问过的不同SCC（包括v的SCC）累积其中的顶点数量（从步骤 1 预先计算）。

使用此算法，您可以从蛮力 O(|V| * |V| + |V| 中消除 |V|*|V| 因素* |E|)).

这是我所知道的解决此问题的最好且最简单的算法。我没有演示，但我很确定没有更好的方法。

在有向图中查找可达顶点

Finding reachable vertices in directed graph

algorithm

graph

graph-algorithm