algorithm - 在有向图中查找可达顶点

Question

我想请教以下问题:

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

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

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

我从顶点 1 运行 DFS 并返回结果 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