计算每个节点在有向图中特定节点可以达到的节点数

Question

在一个有向图中（假设它有很多循环），我需要计算每个节点的特定节点可以达到的节点数。我怎样才能用最小的努力做到这一点？我需要使用哪种算法？

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

Answer 1

您正在寻找的算法称为Floyd-Warshall算法，这是一种非常有效的动态编程算法。尽管它通常用于计算从图中的每个单个节点到所有其他节点的最短路径，但是它可用于计算从图中的每个单个节点可到达的节点集（可传递闭包）。

（编辑：Floyd-Warshall算法比您使用的算法要复杂得多，因为Floyd对其进行了扩展，以计算出最短路径。您可能会发现此页面很有用，该页面仅描述了该算法的“ Warshall”部分算法-您需要的部分。）

我碰巧正在上课学习，并将论文放在桌子上。FW的传递闭包版本的重复性为：

T(i,j,k) = T(i,j,k-1) ? (T(i,k,k-1) ? T(k,j,k-1))

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

从直觉上讲，递归表示如果存在以下情况，则使用前k个顶点存在从i到j的路径：

• 在i和j之间有一条直接路径，使用前k-1个顶点，或
• 使用前k-1个顶点，在i和k之间有一条路径，在k和j之间有一条路径。

您可以采用典型的动态编程方式来构建T（i，j，k）的整个3维表，然后对所需源节点上的所有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)。由于块OR在现代处理器上非常快，因此可以大块完成。

希望有帮助...