无向图的传递闭包（Transitive Closure）的 Floyd-Warshall 算法
字数 2447 2025-12-24 23:03:50

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

题目描述
给定一个无向图（可能有环），计算其传递闭包。
传递闭包是一个矩阵 \(T\)，其中 \(T[i][j] = 1\) 表示顶点 \(i\) 到顶点 \(j\) 是可达的（即存在一条路径从 \(i\) 到 \(j\)），否则 \(T[i][j] = 0\)。
要求设计算法计算这个矩阵。

解题过程

第一步：理解问题

  • 无向图的传递闭包通常比有向图简单，因为无向图的连通性是对称的：如果 \(i\) 可达 \(j\)，则 \(j\) 也可达 \(i\)。
  • 在无向图中，如果两个顶点属于同一个连通分量，则它们互相可达；否则不可达。
  • 传递闭包矩阵是对称的。

第二步：从有向图传递闭包算法出发
有向图的传递闭包常用 Floyd-Warshall 算法 求解，其思想基于动态规划：

  1. 定义状态：设 \(T^{(k)}[i][j] = 1\) 表示“考虑前 \(k\) 个顶点作为中间顶点时，从 \(i\) 到 \(j\) 是否可达”。
  2. 初始时，\(T^{(0)}\) 就是图的邻接矩阵（如果 \(i\) 和 \(j\) 有边则为 1，否则为 0；且 \(T^{(0)}[i][i] = 1\)）。
  3. 状态转移：在从 \(T^{(k-1)}\) 到 \(T^{(k)}\) 时，考虑是否加入顶点 \(k\) 作为中间顶点：

\[ T^{(k)}[i][j] = T^{(k-1)}[i][j] \ \text{OR} \ (T^{(k-1)}[i][k] \ \text{AND} \ T^{(k-1)}[k][j]) \]

即：如果原来就可达，或者可以通过 \(k\) 中转，则新的状态为可达。
4. 对所有 \(k\) 从 1 到 \(n\) 迭代，最终得到传递闭包矩阵 \(T^{(n)}\)。

时间复杂度为 \(O(n^3)\)，空间复杂度可优化到 \(O(n^2)\)（只用一张矩阵）。

第三步：应用到无向图
无向图是特殊的有向图（每条边双向连通），所以 Floyd-Warshall 算法可以直接使用，但我们可以利用对称性简化：

  • 初始矩阵 \(T\) 是对称的。
  • 在更新时，由于对称性，只需计算上三角（或下三角）部分，另一半可以同步更新。

算法步骤：

  1. 输入：邻接矩阵 \(\text{adj}\)，顶点数为 \(n\)。
  2. 初始化 \(T\) 为 \(\text{adj}\)，并将对角线元素 \(T[i][i]\) 设为 1（每个顶点自己可达）。
  3. 循环 \(k\) 从 0 到 \(n-1\)：
    • 对每对 \((i, j)\)，如果 \(T[i][k] = 1\) 且 \(T[k][j] = 1\)，则设置 \(T[i][j] = 1\)。
  4. 输出 \(T\) 作为传递闭包矩阵。

注意：由于无向图中连通分量是传递闭包的核心，实际上可以通过 BFS/DFS 以 \(O(n^2)\) 时间求解（对每个顶点做 BFS/DFS 标记可达顶点）。但本题要求用 Floyd-Warshall 算法的思想，所以我们用这个动态规划方法来理解闭包的计算过程。

第四步：具体例子
考虑一个无向图（顶点 0,1,2,3）：

边：0-1, 1-2, 3 孤立

初始矩阵 \(T^{(0)}\)（对角线为1，有边的位置为1）：

\[\begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

迭代 \(k=0\)：加入顶点 0 作为中间顶点。
检查所有 \(i,j\)：

  • \(T[0][0]=1\)，不会新增。
    更新后矩阵不变。

迭代 \(k=1\)：加入顶点 1 作为中间顶点。
检查 \(i=0, j=2\)：\(T[0][1]=1\) 且 \(T[1][2]=1\) → 设置 \(T[0][2]=1\)（对称地 \(T[2][0]=1\)）。
矩阵变为：

\[\begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

迭代 \(k=2\)：加入顶点 2 作为中间顶点，不会新增（因为顶点 0,1,2 已全连通）。

迭代 \(k=3\)：加入顶点 3 作为中间顶点，不会影响其他顶点。

最终矩阵：

\[\begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

表示顶点 0,1,2 互相可达，顶点 3 只到自己可达，符合预期。

第五步：时间复杂度与空间复杂度

  • 时间复杂度：三层循环 \(O(n^3)\)。
  • 空间复杂度：\(O(n^2)\) 存储矩阵。

第六步：扩展讨论
虽然 Floyd-Warshall 能直接用于无向图，但在实际中，无向图的传递闭包等价于求连通分量。我们可以用以下更优方法：

  1. 用 BFS/DFS 找出所有连通分量，时间复杂度 \(O(n + m)\)。
  2. 对同一个分量内的所有顶点对，设置闭包矩阵对应项为 1。

这比 \(O(n^3)\) 的 Floyd-Warshall 更高效。但题目要求基于 Floyd-Warshall 思想，所以核心是理解动态规划如何逐步传播可达性。

无向图的传递闭包（Transitive Closure）的 Floyd-Warshall 算法 题目描述 给定一个无向图（可能有环），计算其传递闭包。 传递闭包是一个矩阵 \( T \)，其中 \( T[ i][ j] = 1 \) 表示顶点 \( i \) 到顶点 \( j \) 是可达的（即存在一条路径从 \( i \) 到 \( j \)），否则 \( T[ i][ j ] = 0 \)。 要求设计算法计算这个矩阵。 解题过程 第一步：理解问题 无向图的传递闭包通常比有向图简单，因为无向图的连通性是对称的：如果 \( i \) 可达 \( j \)，则 \( j \) 也可达 \( i \)。 在无向图中，如果两个顶点属于同一个连通分量，则它们互相可达；否则不可达。 传递闭包矩阵是 对称的 。 第二步：从有向图传递闭包算法出发 有向图的传递闭包常用 Floyd-Warshall 算法 求解，其思想基于动态规划： 定义状态：设 \( T^{(k)}[ i][ j ] = 1 \) 表示“考虑前 \( k \) 个顶点作为中间顶点时，从 \( i \) 到 \( j \) 是否可达”。 初始时，\( T^{(0)} \) 就是图的邻接矩阵（如果 \( i \) 和 \( j \) 有边则为 1，否则为 0；且 \( T^{(0)}[ i][ i ] = 1 \)）。 状态转移：在从 \( T^{(k-1)} \) 到 \( T^{(k)} \) 时，考虑是否加入顶点 \( k \) 作为中间顶点： \[ T^{(k)}[ i][ j] = T^{(k-1)}[ i][ j] \ \text{OR} \ (T^{(k-1)}[ i][ k] \ \text{AND} \ T^{(k-1)}[ k][ j ]) \] 即：如果原来就可达，或者可以通过 \( k \) 中转，则新的状态为可达。 对所有 \( k \) 从 1 到 \( n \) 迭代，最终得到传递闭包矩阵 \( T^{(n)} \)。 时间复杂度为 \( O(n^3) \)，空间复杂度可优化到 \( O(n^2) \)（只用一张矩阵）。 第三步：应用到无向图 无向图是特殊的有向图（每条边双向连通），所以 Floyd-Warshall 算法可以直接使用，但我们可以利用对称性简化： 初始矩阵 \( T \) 是对称的。 在更新时，由于对称性，只需计算上三角（或下三角）部分，另一半可以同步更新。 算法步骤 ： 输入：邻接矩阵 \( \text{adj} \)，顶点数为 \( n \)。 初始化 \( T \) 为 \( \text{adj} \)，并将对角线元素 \( T[ i][ i ] \) 设为 1（每个顶点自己可达）。 循环 \( k \) 从 0 到 \( n-1 \)： 对每对 \( (i, j) \)，如果 \( T[ i][ k] = 1 \) 且 \( T[ k][ j] = 1 \)，则设置 \( T[ i][ j ] = 1 \)。 输出 \( T \) 作为传递闭包矩阵。 注意 ：由于无向图中连通分量是传递闭包的核心，实际上可以通过 BFS/DFS 以 \( O(n^2) \) 时间求解（对每个顶点做 BFS/DFS 标记可达顶点）。但本题要求用 Floyd-Warshall 算法的思想，所以我们用这个动态规划方法来理解闭包的计算过程。 第四步：具体例子 考虑一个无向图（顶点 0,1,2,3）： 初始矩阵 \( T^{(0)} \)（对角线为1，有边的位置为1）： \[ \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \] 迭代 \( k=0 \)：加入顶点 0 作为中间顶点。 检查所有 \( i,j \)： \( T[ 0][ 0 ]=1 \)，不会新增。 更新后矩阵不变。 迭代 \( k=1 \)：加入顶点 1 作为中间顶点。 检查 \( i=0, j=2 \)：\( T[ 0][ 1]=1 \) 且 \( T[ 1][ 2]=1 \) → 设置 \( T[ 0][ 2]=1 \)（对称地 \( T[ 2][ 0 ]=1 \)）。 矩阵变为： \[ \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \] 迭代 \( k=2 \)：加入顶点 2 作为中间顶点，不会新增（因为顶点 0,1,2 已全连通）。 迭代 \( k=3 \)：加入顶点 3 作为中间顶点，不会影响其他顶点。 最终矩阵： \[ \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \] 表示顶点 0,1,2 互相可达，顶点 3 只到自己可达，符合预期。 第五步：时间复杂度与空间复杂度 时间复杂度：三层循环 \( O(n^3) \)。 空间复杂度：\( O(n^2) \) 存储矩阵。 第六步：扩展讨论 虽然 Floyd-Warshall 能直接用于无向图，但在实际中，无向图的传递闭包等价于 求连通分量 。我们可以用以下更优方法： 用 BFS/DFS 找出所有连通分量，时间复杂度 \( O(n + m) \)。 对同一个分量内的所有顶点对，设置闭包矩阵对应项为 1。 这比 \( O(n^3) \) 的 Floyd-Warshall 更高效。但题目要求基于 Floyd-Warshall 思想，所以核心是理解动态规划如何逐步传播可达性。