传递闭包是关系代数的一个概念，具体理论见 （链接未公开）。

在图论中，传递闭包体现为一幅有向图的超图。

概念

定义

有向图 G = (V, E) 的传递闭包 H = (V, E') 可如下定义：

• H 的点集和 G 的点集相同；
• 对任意两个节点 u, v，若 G 中 u 与 v 间存在路径，则 (u, v) 为 H 中一条边。

算法

Warshall 算法

和最短路的 Floyd 算法非常类似，使用动态规划实现。

按一定顺序排列元素（节点），仅考虑前 k 个节点 u_1, \dots, u_k，u_i 是否可达 u_j 记为 w_{ij}^{(k)}，定义 0-1 矩阵 W^{(k)}。

则转移方程如下：

该方程的意义：i 在第 k 步可达 j，当且仅当 i 已经可达 j，或者加入节点 k 后 i 通过 k 可达 j。初始状态为 W^{(0)} = R。

时间复杂度 O(n^3)，可以进一步用 bitset 进行常数优化。