Warshall算法求传递闭包Python实现

Warshall算法求传递闭包python实现

算法描述： Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：

(1)置新矩阵A＝M； (2)i＝1； (3)对所有j如果A[j，i]＝1，则对k＝1，2，…，n，A[j，k]＝A[j，k]∨A； (4)i加1；（i是行，j是列） (5)如果i≤n，则转到步骤3)，否则停止。

例如： 一个矩阵M: 第一步：当i=1时;找到M[j][i]=1时的位置；即M[2][1]=1; 再将第j行加上第i行得到新的第j行，即把第2行加上第1行得到新的第2行;i+1；得到如下的新矩阵: 第二步：当i=2时，重复第一步：有M[1][2]=1,M[2][2]=1,M[4][2]=1;再将第2行分别和1、2、4行相加得到新的1、2、4行；i+1;得到如下的新矩阵： 第三步：当i=3时；重复上述步骤：有M[1][3]=1,M[2][3]=1,M[4][3]=1；将第3行分别加到1，2，4行得到新的矩阵，i+1； 第四步：当i=4时，重复上述步骤；有M[1][4],M[2][4],M[3][4],M[4][4]等于1；将第四行分别加到1、2、3、4行得到新的1、2、3、4行，i+1； 新矩阵如图所示： 右移i+1=5>4,停止，得到该矩阵的传递闭包的关系矩阵；

代码:

ls = []
n = int(input(请输入阶数:
))
#获取矩阵关系
for i in range(n):
    ls.append(input(第{}行.format(i+1)).split())

def logic(a,b):
    #逻辑加
    return 0 if a==0 and b==0 else 1

#Walshall算法
for lie in range(n):
    for hang in range(n):
        if int(ls[hang][lie])==1:
           for i in range(n):
               ls[hang][i]=logic(int(ls[hang][i]),int(ls[lie][i]))
    print(ls)