有向图的传递闭包（Transitive Closure）的 Floyd-Warshall 算法
字数 2517 2025-12-10 13:21:50

有向图的传递闭包（Transitive Closure）的 Floyd-Warshall 算法

题目描述

传递闭包是图论中的一个重要概念，它描述有向图中顶点之间的可达性。给定一个有向图 \(G = (V, E)\)，传递闭包是一个新的有向图 \(G^* = (V, E^*)\)，其中如果从顶点 \(u\) 到顶点 \(v\) 在 \(G\) 中存在一条路径（长度可以为0），则 \((u, v) \in E^*\)。换句话说，传递闭包记录了所有顶点对之间是否可达。
题目要求：实现一个算法，计算给定有向图的传递闭包。

解题过程

第一步：理解问题与建模

  • 输入：有向图 \(G\) 的邻接矩阵 \(A\)，其中 \(A[u][v] = 1\) 当且仅当存在有向边 \(u \to v\)。
  • 输出：传递闭包的邻接矩阵 \(T\)，其中 \(T[u][v] = 1\) 当且仅当在 \(G\) 中从 \(u\) 到 \(v\) 可达。
  • 自反性：通常传递闭包定义中包含每个顶点到自身的可达性（长度为0的路径），即 \(T[u][u] = 1\)。

第二步：朴素方法（DFS/BFS）

  • 对每个顶点 \(u\)，从 \(u\) 开始做 DFS 或 BFS，标记所有从 \(u\) 可达的顶点 \(v\)，并令 \(T[u][v] = 1\)。
  • 时间复杂度：\(O(V \times (V + E))\)，稀疏图约为 \(O(V^2)\)，稠密图为 \(O(V^3)\)。
  • 缺点：对稠密图不够高效，且实现稍显繁琐。

第三步：Floyd-Warshall 算法的核心思想

Floyd-Warshall 算法原本用于求所有点对的最短路径，但经过简单修改，可高效求传递闭包。
基本思想：动态规划。定义：

\[\text{reach}[u][v][k] = \text{是否存在路径 } u \leadsto v \text{，且路径的中间节点（不含首尾）的编号} \le k \]

  • 初始：\(\text{reach}[u][v][-1]\) 对应邻接矩阵，即只考虑直接边（中间节点为空）。
  • 递推：考虑是否经过顶点 \(k\) 作为中间节点：
    • 若不经过 \(k\)：\(\text{reach}[u][v][k] = \text{reach}[u][v][k-1]\)
    • 若经过 \(k\)：需要 \(u \leadsto k\) 且 \(k \leadsto v\) 都在中间节点 \(\le k-1\) 的情况下可达，即 \(\text{reach}[u][k][k-1] \land \text{reach}[k][v][k-1]\)
    • 合并：\(\text{reach}[u][v][k] = \text{reach}[u][v][k-1] \lor \big( \text{reach}[u][k][k-1] \land \text{reach}[k][v][k-1] \big)\)
  • 最终：\(T[u][v] = \text{reach}[u][v][n-1]\)。

第四步：空间优化与实现

  • 观察发现递推中 \(k\) 只依赖 \(k-1\)，因此可省略第三维，直接用二维矩阵 \(T\) 迭代更新：

\[T[u][v] := T[u][v] \lor (T[u][k] \land T[k][v]) \]

  • 算法步骤：
    1. 初始化 \(T\) 为邻接矩阵 \(A\)。
    2. 将每个 \(T[u][u]\) 设为 1（允许自反路径，但根据定义可选，不影响最终传递性）。
    3. 对每个 \(k\) 从 0 到 \(n-1\)：
      对每对 \((u, v)\)：

\[ T[u][v] = T[u][v] \lor (T[u][k] \land T[k][v]) \]

  • 时间复杂度：\(O(V^3)\)，空间复杂度：\(O(V^2)\)。

第五步：举例说明

考虑有向图顶点集 {0, 1, 2}，边：0→1, 1→2。
初始化 \(T\)（自反设为1）：

\[T = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \]

迭代：

  • \(k=0\)：对 \(u=1, v=2\)，\(T[1][0] \land T[0][2] = 0\)，不更新。
  • \(k=1\)：对 \(u=0, v=2\)，\(T[0][1] \land T[1][2] = 1\)，更新 \(T[0][2]=1\)。
  • \(k=2\)：无新更新。
    最终：

\[T = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \]

表示 0 可达 2。

第六步：算法正确性解释

  • 动态规划考虑了所有可能的中间节点顺序。当 \(k\) 从 0 到 \(n-1\) 迭代时，我们逐渐允许路径经过更多编号的顶点作为中间节点。最终 \(T[u][v]=1\) 当且仅当存在一条任意中间节点的路径。
  • 自反性初始化（\(T[u][u]=1\)）确保了长度为 0 的路径被包括，符合传递闭包的定义。

第七步：扩展与优化

  • 稀疏图优化：可以使用 Warshall 算法 的位运算优化（bitset），将内层循环用位运算批量处理，可将常数降低约 \(\frac{V}{w}\) 倍（\(w\) 是字长，如 64）。
  • 实际实现中，如果不需要自反闭包，可不设 \(T[u][u]=1\)，但此时传递闭包不包含顶点到自身。
有向图的传递闭包（Transitive Closure）的 Floyd-Warshall 算法 题目描述 传递闭包 是图论中的一个重要概念，它描述有向图中顶点之间的 可达性 。给定一个有向图 \( G = (V, E) \)，传递闭包是一个新的有向图 \( G^* = (V, E^ ) \)，其中如果从顶点 \( u \) 到顶点 \( v \) 在 \( G \) 中存在一条路径（长度可以为0），则 \( (u, v) \in E^ \)。换句话说，传递闭包记录了所有顶点对之间是否可达。 题目要求：实现一个算法，计算给定有向图的传递闭包。 解题过程 第一步：理解问题与建模 输入：有向图 \( G \) 的邻接矩阵 \( A \)，其中 \( A[ u][ v ] = 1 \) 当且仅当存在有向边 \( u \to v \)。 输出：传递闭包的邻接矩阵 \( T \)，其中 \( T[ u][ v ] = 1 \) 当且仅当在 \( G \) 中从 \( u \) 到 \( v \) 可达。 自反性：通常传递闭包定义中包含每个顶点到自身的可达性（长度为0的路径），即 \( T[ u][ u ] = 1 \)。 第二步：朴素方法（DFS/BFS） 对每个顶点 \( u \)，从 \( u \) 开始做 DFS 或 BFS，标记所有从 \( u \) 可达的顶点 \( v \)，并令 \( T[ u][ v ] = 1 \)。 时间复杂度：\( O(V \times (V + E)) \)，稀疏图约为 \( O(V^2) \)，稠密图为 \( O(V^3) \)。 缺点：对稠密图不够高效，且实现稍显繁琐。 第三步：Floyd-Warshall 算法的核心思想 Floyd-Warshall 算法原本用于求所有点对的最短路径，但经过简单修改，可高效求传递闭包。 基本思想 ：动态规划。定义： \[ \text{reach}[ u][ v][ k ] = \text{是否存在路径 } u \leadsto v \text{，且路径的中间节点（不含首尾）的编号} \le k \] 初始：\( \text{reach}[ u][ v][ -1 ] \) 对应邻接矩阵，即只考虑直接边（中间节点为空）。 递推：考虑是否经过顶点 \( k \) 作为中间节点： 若不经过 \( k \)：\(\text{reach}[ u][ v][ k] = \text{reach}[ u][ v][ k-1 ]\) 若经过 \( k \)：需要 \( u \leadsto k \) 且 \( k \leadsto v \) 都在中间节点 \( \le k-1 \) 的情况下可达，即 \(\text{reach}[ u][ k][ k-1] \land \text{reach}[ k][ v][ k-1 ]\) 合并：\(\text{reach}[ u][ v][ k] = \text{reach}[ u][ v][ k-1] \lor \big( \text{reach}[ u][ k][ k-1] \land \text{reach}[ k][ v][ k-1 ] \big)\) 最终：\( T[ u][ v] = \text{reach}[ u][ v][ n-1 ] \)。 第四步：空间优化与实现 观察发现递推中 \( k \) 只依赖 \( k-1 \)，因此可省略第三维，直接用二维矩阵 \( T \) 迭代更新： \[ T[ u][ v] := T[ u][ v] \lor (T[ u][ k] \land T[ k][ v ]) \] 算法步骤： 初始化 \( T \) 为邻接矩阵 \( A \)。 将每个 \( T[ u][ u ] \) 设为 1（允许自反路径，但根据定义可选，不影响最终传递性）。 对每个 \( k \) 从 0 到 \( n-1 \)： 对每对 \( (u, v) \)： \[ T[ u][ v] = T[ u][ v] \lor (T[ u][ k] \land T[ k][ v ]) \] 时间复杂度：\( O(V^3) \)，空间复杂度：\( O(V^2) \)。 第五步：举例说明 考虑有向图顶点集 {0, 1, 2}，边：0→1, 1→2。 初始化 \( T \)（自反设为1）： \[ T = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \] 迭代： \( k=0 \)：对 \( u=1, v=2 \)，\( T[ 1][ 0] \land T[ 0][ 2 ] = 0 \)，不更新。 \( k=1 \)：对 \( u=0, v=2 \)，\( T[ 0][ 1] \land T[ 1][ 2] = 1 \)，更新 \( T[ 0][ 2 ]=1 \)。 \( k=2 \)：无新更新。 最终： \[ T = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \] 表示 0 可达 2。 第六步：算法正确性解释 动态规划考虑了所有可能的中间节点顺序。当 \( k \) 从 0 到 \( n-1 \) 迭代时，我们逐渐允许路径经过更多编号的顶点作为中间节点。最终 \( T[ u][ v ]=1 \) 当且仅当存在一条任意中间节点的路径。 自反性初始化（\( T[ u][ u ]=1 \)）确保了长度为 0 的路径被包括，符合传递闭包的定义。 第七步：扩展与优化 稀疏图优化：可以使用 Warshall 算法 的位运算优化（bitset），将内层循环用位运算批量处理，可将常数降低约 \( \frac{V}{w} \) 倍（\( w \) 是字长，如 64）。 实际实现中，如果不需要自反闭包，可不设 \( T[ u][ u ]=1 \)，但此时传递闭包不包含顶点到自身。