无向图的传递闭包（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 思想，所以核心是理解动态规划如何逐步传播可达性。