针对每个节点，计算在有向图中可以到达的节点数量

Question

在一个有向图中（假设它有很多环），我需要计算每个节点能够到达的节点数量。我应该如何用最小的努力来做到这一点？我需要使用哪个算法？

注意：我认为这个问题的一个合理算法应该递归地计算这些数字（例如，如果a连接到b，则“节点a”的结果取决于“节点b”的结果）。

- bfaskiplar

Answer 1

你需要的算法叫做Floyd-Warshall算法，它是一种非常好的、高效的动态规划算法。它可以用于计算图中每个节点可达的节点集合（传递闭包），尽管它更常用于计算图中每个节点到所有其他节点的最短路径。

（编辑：Floyd-Warshall算法比你所需的要复杂一些，因为Floyd扩展了它以计算最短路径。你可能会发现这个页面有帮助，它只描述了算法的“Warshall”部分-你所需要的部分。）

我碰巧正在为课程学习它，并且在我的桌子上有这篇论文。F-W的传递闭包版本的递推公式为：

T(i,j,k) = T(i,j,k-1) ∨ (T(i,k,k-1) ∧ T(k,j,k-1))

当且仅当在图中使用前c个顶点从a到b存在路径时，T(a,b,c)为真（在运行算法之前必须给它们一个任意编号）。

直观地说，递归公式表示如果：

• i和j之间有一条直接路径，该路径使用前k-1个顶点，或者
• i和k之间有一条路径，k和j之间有一条路径，这两条路径都使用前k-1个顶点，则i和j之间存在一条使用前k个顶点的路径。

您可以按照典型的动态规划方式构建整个T(i,j,k)的三维表，然后计算您想要的源节点上所有TRUE条目的数量（使用最大的k），以获取该源节点的传递闭包的大小。

如果您仍然能够理解我不好的解释，您可以通过一些技巧使算法变得非常高效：

• 原来你不需要表中的k维度；你可以反复覆盖同一行的值。现在程序看起来是这样的：

  T(i,j) = T(i,j) || (T(i,k) && T(k,j))

• 如果T(i,k)为0，则可以跳过整个步骤，因为在该步骤中没有任何变化。

• 如果T(i,k)为1，则新值将是T(i,j) || T(k,j)。由于块或在现代处理器上非常快，因此可以大块地执行此操作。

希望这有所帮助...

- Rag