Warshall传递闭包算法

Warshall算法是一种用于计算传递闭包的算法，它可以用于有向图和有向加权图。传递闭包是指在一个有向图，如果存在一条从节点i到节点j的路径，那么节点i和节点j之间就存在一条边。Warshall算法可以计算出图中所有节点之间的可达关系，即传递闭包。

以下是Warshall算法的实现步骤：

1. 初始化一个n x n的矩阵T，其中n是图中节点的数量。如果节点i可以到达节点j，则T[i][j]的值为1，否则为0。

2. 对于每一个节点k，遍历矩阵T，如果存在T[i][k]和T[k][j]都为1，则将T[i][j]的值设为1。

3. 重复步骤2，直到所有节点之间的可达关系都被计算出来。

以下是Python实现Warshall算法的代码：

def warshall(graph):
    n = len(graph)
    T = [[0 for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            T[i][j] = graph[i][j]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                T[i][j] = T[i][j] or (T[i][k] and T[k][j])
    return T

其中，graph是一个n x n的矩阵，表示有向图中节点之间的连通关系。函数返回一个n x n的矩阵，表示图中所有节点之间的可达关系。