动态图的传递闭包25-1

传递闭包是指在有向图中，如果存在从节点 A 到节点 B 的路径，则节点 A 和节点 B 之间存在传递性关系。动态图的传递闭包可以通过 Floyd-Warshall 算法来计算。

以下是一个示例有向图：

   ┌───┐    ┌───┐
   │ 1 │───►│ 2 │
   └───┘    └───┘
    ▲ ▲      ▲
    │ │      │
    │ └──────┘
    │
   ┌┴─┐
   │ 3 │
   └┬─┘
    │
   ┌┴─┐
   │ 4 │
   └┬─┘
    │
   ┌┴─┐
   │ 5 │
   └───┘

我们可以用一个邻接矩阵来表示这个有向图：

    1   2   3   4   5
1   0   1   0   0   0
2   0   0   0   1   0
3   0   1   0   0   0
4   0   0   1   0   0
5   0   0   0   1   0

其中，矩阵中的元素 a[i][j] 表示从节点 i 到节点 j 是否存在一条有向边。

接下来，我们用 Floyd-Warshall 算法来计算这个图的传递闭包。

初始化：

    1   2   3   4   5
1   0   1   0   0   0
2   0   0   0   1   0
3   0   1   0   0   0
4   0   0   1   0   0
5   0   0   0   1   0

第一轮迭代：

    1   2   3   4   5
1   1   1   0   1   0
2   0   0   0   1   0
3   1   1   0   1   0
4   0   0   1   0   0
5   0   0   0   1   0

第二轮迭代：

    1   2   3   4   5
1   1   1   0   1   0
2   1   1   0   1   0
3   1   1   0   1   0
4   0   0   1   0   0
5   0   0   0   1   0

第三轮迭代：

    1   2   3   4   5
1   1   1   0   1   0
2   1   1   0   1   0
3   1   1   0   1   0
4   1   1   1   1   0
5   0   0   0   1   0

第四轮迭代：

    1   2   3   4   5
1   1   1   0   1   0
2   1   1   0   1   0
3   1   1   0   1   0
4   1   1   1   1   0
5   1   1   1   1   0

最终的矩阵中，a[i][j] 的值为 1 表示从节点 i 到节点 j 存在传递性关系，值为 0 则表示不存在。因此，动态图的传递闭包就是这个矩阵。在这个示例中，节点 1、2、3 之间存在传递性关系，节点 4、5 之间也存在传递性关系，但是两者之间没有传递性关系。