有向无环图（DAG）的传递闭包问题

字数 2741 2025-12-08 10:25:58

有向无环图（DAG）的传递闭包问题

题目描述
给定一个有向无环图（DAG），其顶点数为 \(n\)，边数为 \(m\)。要求计算该图的传递闭包。
传递闭包是一个 \(n \times n\) 的布尔矩阵 \(T\)，其中 \(T[u][v] = \text{True}\) 当且仅当在图中存在一条从顶点 \(u\) 到顶点 \(v\) 的路径（包括长度为0的路径，即 \(u = v\) 时也为True）。换句话说，传递闭包记录了图中所有顶点对之间的可达性关系。

解题过程

传递闭包的计算可以通过多种方法实现。针对DAG，我们可以利用其无环的性质，采用基于拓扑排序的动态规划方法，效率较高。下面我将详细讲解这个算法。

步骤1：理解输入与输出
输入：DAG用邻接表表示，顶点编号从0到 \(n-1\)。
输出：一个 \(n \times n\) 的布尔矩阵（或位矩阵）\(T\)，表示传递闭包。

步骤2：核心思路
在有向无环图中，从顶点 \(u\) 出发可到达的顶点集合，可以通过考虑 \(u\) 的所有后继节点来递推得到。具体来说：

如果 \(u\) 可以直接到达 \(v\)，那么 \(T[u][v] = \text{True}\)。
如果 \(u\) 可以到达某个中间节点 \(w\)，并且 \(w\) 可以到达 \(v\)，那么 \(u\) 也可以到达 \(v\)。
为了高效计算，我们按照拓扑排序的顺序处理顶点。拓扑排序保证了当处理一个顶点 \(u\) 时，\(u\) 的所有后继节点都已经被处理过（因为DAG中无边指向已处理的顶点，且后继节点在拓扑序中位于 \(u\) 之后）。这样，我们可以用“后向传递”的方式更新传递闭包。

步骤3：算法步骤详解

拓扑排序
首先对DAG进行拓扑排序，得到一个顶点序列 \(order[0..n-1]\)。
拓扑排序可以用Kahn算法（基于入度）或DFS实现。这里以Kahn算法为例：
- 计算每个顶点的入度。
- 将入度为0的顶点加入队列。
- 当队列非空时，取出队首顶点 \(u\)，将其加入拓扑序列，然后对于 \(u\) 的每个邻居 \(v\)，将其入度减1，若入度变为0则将 \(v\) 入队。
动态规划计算传递闭包
我们维护一个二维布尔数组 \(T\)（大小为 \(n \times n\)），初始时全部为False。
对于每个顶点 \(u\)，\(T[u][u] = \text{True}\)（每个顶点可达自身）。
然后按照拓扑排序的逆序处理顶点（即从最后一个顶点向前处理）。为什么是逆序？
因为当我们处理顶点 \(u\) 时，我们希望 \(u\) 的所有后继节点都已经处理完毕，这样我们可以直接利用后继节点的可达信息来更新 \(u\) 的可达信息。在拓扑序列中，后继节点一定出现在 \(u\) 的后面，所以逆序处理（从后往前）就能保证这个性质。

具体更新过程：
对于当前顶点 \(u\)，首先标记 \(u\) 可达自身。然后遍历 \(u\) 的每个直接后继 \(v\)：
- 将 \(T[u][v]\) 设为True（因为存在边 \(u \to v\)）。
- 对于所有顶点 \(w\)，如果 \(T[v][w]\) 为True（即 \(v\) 可达 \(w\)），那么将 \(T[u][w]\) 也设为True。
  这步更新相当于：如果 \(u\) 可达 \(v\)，且 \(v\) 可达 \(w\)，则 \(u\) 可达 \(w\)。
复杂度分析
- 拓扑排序的时间复杂度为 \(O(n + m)\)。
- 动态规划部分：对于每个顶点 \(u\)，需要遍历其所有出边，并对每个出边对应的后继 \(v\)，可能需要更新 \(T[u][*]\) 的 \(n\) 个值。最坏情况下，每个顶点都可能更新 \(n\) 个值，总复杂度为 \(O(n^3)\)。但我们可以用位运算（bitset）优化：用 \(n\) 位的二进制位（bitset）表示每个顶点的可达集合，那么“如果 \(T[v][w]\) 为True，则设置 \(T[u][w]\) 为True”这个操作，可以通过位或（bitwise OR）在 \(O(n/word)\) 时间内完成（word通常为机器字长，如64）。这样总复杂度可降为 \(O(n^3 / 64)\)，在 \(n\) 较大时显著提升速度。

步骤4：举例说明
假设有一个DAG包含4个顶点：0,1,2,3，边为：0→1, 0→2, 1→3, 2→3。
拓扑排序结果：0,1,2,3（或0,2,1,3）。
按逆序处理：

处理顶点3：\(T[3][3] = True\)。
处理顶点2：先设 \(T[2][2]=True\)，边2→3，设 \(T[2][3]=True\)，然后将 \(T[3]\) 的可达集（位）合并到 \(T[2]\)：即 \(T[2] |= T[3]\)，此时 \(T[2]\) 表示{2,3}可达。
处理顶点1：类似，\(T[1][1]=True\)，边1→3，设 \(T[1][3]=True\)，然后 \(T[1] |= T[3]\)，得{1,3}。
处理顶点0：\(T[0][0]=True\)，边0→1，设 \(T[0][1]=True\)，然后 \(T[0] |= T[1]\)（得{0,1,3}）；边0→2，设 \(T[0][2]=True\)，然后 \(T[0] |= T[2]\)（得{0,1,2,3}）。
最终传递闭包矩阵中，\(T[0]\) 行全为True，其他行对应自身及后继。

步骤5：算法实现要点

使用邻接表存储图。
拓扑排序可用Kahn算法。
用bitset数组（如C++的std::bitset，Python中用整数位掩码）存储每个顶点的可达集合，更新时用位或操作。
最终 \(T[u][v]\) 即为第 \(u\) 个bitset的第 \(v\) 位。

这个算法结合了DAG的拓扑序特性与位运算优化，能够在 \(O(n^3 / 64)\) 时间内计算出传递闭包，是实践中高效的方法。

有向无环图（DAG）的传递闭包问题题目描述给定一个有向无环图（DAG），其顶点数为 \( n \)，边数为 \( m \)。要求计算该图的传递闭包。传递闭包是一个 \( n \times n \) 的布尔矩阵 \( T \)，其中 \( T[ u][ v ] = \text{True} \) 当且仅当在图中存在一条从顶点 \( u \) 到顶点 \( v \) 的路径（包括长度为0的路径，即 \( u = v \) 时也为True）。换句话说，传递闭包记录了图中所有顶点对之间的可达性关系。解题过程传递闭包的计算可以通过多种方法实现。针对DAG，我们可以利用其无环的性质，采用基于拓扑排序的动态规划方法，效率较高。下面我将详细讲解这个算法。步骤1：理解输入与输出输入：DAG用邻接表表示，顶点编号从0到 \( n-1 \)。输出：一个 \( n \times n \) 的布尔矩阵（或位矩阵）\( T \)，表示传递闭包。步骤2：核心思路在有向无环图中，从顶点 \( u \) 出发可到达的顶点集合，可以通过考虑 \( u \) 的所有后继节点来递推得到。具体来说：如果 \( u \) 可以直接到达 \( v \)，那么 \( T[ u][ v ] = \text{True} \)。如果 \( u \) 可以到达某个中间节点 \( w \)，并且 \( w \) 可以到达 \( v \)，那么 \( u \) 也可以到达 \( v \)。为了高效计算，我们按照拓扑排序的顺序处理顶点。拓扑排序保证了当处理一个顶点 \( u \) 时，\( u \) 的所有后继节点都已经被处理过（因为DAG中无边指向已处理的顶点，且后继节点在拓扑序中位于 \( u \) 之后）。这样，我们可以用“后向传递”的方式更新传递闭包。步骤3：算法步骤详解拓扑排序首先对DAG进行拓扑排序，得到一个顶点序列 \( order[ 0..n-1 ] \)。拓扑排序可以用Kahn算法（基于入度）或DFS实现。这里以Kahn算法为例：计算每个顶点的入度。将入度为0的顶点加入队列。当队列非空时，取出队首顶点 \( u \)，将其加入拓扑序列，然后对于 \( u \) 的每个邻居 \( v \)，将其入度减1，若入度变为0则将 \( v \) 入队。动态规划计算传递闭包我们维护一个二维布尔数组 \( T \)（大小为 \( n \times n \)），初始时全部为False。对于每个顶点 \( u \)，\( T[ u][ u ] = \text{True} \)（每个顶点可达自身）。然后按照拓扑排序的逆序处理顶点（即从最后一个顶点向前处理）。为什么是逆序？因为当我们处理顶点 \( u \) 时，我们希望 \( u \) 的所有后继节点都已经处理完毕，这样我们可以直接利用后继节点的可达信息来更新 \( u \) 的可达信息。在拓扑序列中，后继节点一定出现在 \( u \) 的后面，所以逆序处理（从后往前）就能保证这个性质。具体更新过程：对于当前顶点 \( u \)，首先标记 \( u \) 可达自身。然后遍历 \( u \) 的每个直接后继 \( v \)：将 \( T[ u][ v ] \) 设为True（因为存在边 \( u \to v \)）。对于所有顶点 \( w \)，如果 \( T[ v][ w] \) 为True（即 \( v \) 可达 \( w \)），那么将 \( T[ u][ w ] \) 也设为True。这步更新相当于：如果 \( u \) 可达 \( v \)，且 \( v \) 可达 \( w \)，则 \( u \) 可达 \( w \)。复杂度分析拓扑排序的时间复杂度为 \( O(n + m) \)。动态规划部分：对于每个顶点 \( u \)，需要遍历其所有出边，并对每个出边对应的后继 \( v \)，可能需要更新 \( T[ u][* ] \) 的 \( n \) 个值。最坏情况下，每个顶点都可能更新 \( n \) 个值，总复杂度为 \( O(n^3) \)。但我们可以用位运算（bitset）优化：用 \( n \) 位的二进制位（bitset）表示每个顶点的可达集合，那么“如果 \( T[ v][ w] \) 为True，则设置 \( T[ u][ w ] \) 为True”这个操作，可以通过位或（bitwise OR）在 \( O(n/word) \) 时间内完成（word通常为机器字长，如64）。这样总复杂度可降为 \( O(n^3 / 64) \)，在 \( n \) 较大时显著提升速度。步骤4：举例说明假设有一个DAG包含4个顶点：0,1,2,3，边为：0→1, 0→2, 1→3, 2→3。拓扑排序结果：0,1,2,3（或0,2,1,3）。按逆序处理：处理顶点3：\( T[ 3][ 3 ] = True \)。处理顶点2：先设 \( T[ 2][ 2]=True \)，边2→3，设 \( T[ 2][ 3]=True \)，然后将 \( T[ 3] \) 的可达集（位）合并到 \( T[ 2] \)：即 \( T[ 2] |= T[ 3] \)，此时 \( T[ 2 ] \) 表示{2,3}可达。处理顶点1：类似，\( T[ 1][ 1]=True \)，边1→3，设 \( T[ 1][ 3]=True \)，然后 \( T[ 1] |= T[ 3 ] \)，得{1,3}。处理顶点0：\( T[ 0][ 0]=True \)，边0→1，设 \( T[ 0][ 1]=True \)，然后 \( T[ 0] |= T[ 1] \)（得{0,1,3}）；边0→2，设 \( T[ 0][ 2]=True \)，然后 \( T[ 0] |= T[ 2 ] \)（得{0,1,2,3}）。最终传递闭包矩阵中，\( T[ 0 ] \) 行全为True，其他行对应自身及后继。步骤5：算法实现要点使用邻接表存储图。拓扑排序可用Kahn算法。用bitset数组（如C++的std::bitset，Python中用整数位掩码）存储每个顶点的可达集合，更新时用位或操作。最终 \( T[ u][ v ] \) 即为第 \( u \) 个bitset的第 \( v \) 位。这个算法结合了DAG的拓扑序特性与位运算优化，能够在 \( O(n^3 / 64) \) 时间内计算出传递闭包，是实践中高效的方法。