沃肖尔的算法传递闭（蟒蛇） [英] Warshall's Algorithm for Transitive Closure(Python)

问题描述

我写一个使用沃肖尔的算法找到一个矩阵，再presents关系的传递闭包的程序。这里是一个链接的算法伪code：的 http://people.cs.pitt.edu/~adamlee/courses/cs0441/lectures/lecture27-closures.pdf （第21页）。

I am writing a program that uses Warshall's algorithm for to find a transitive closure of a matrix that represents a relation. Here is a link to the algorithm in psuedocode: http://people.cs.pitt.edu/~adamlee/courses/cs0441/lectures/lecture27-closures.pdf (page 21).

def warshall(a):

    assert (len(row) == len(a) for row in a)
    n = len(a)
    for k in range (1,n):
        for i in range (1,n):
            for j in range (1,n):
                a[i][j] = a[i][j] or (a[i][k] and a[k][j])


   return M

   print warshall([[0,0,0,1],[1,0,1,0],[1,0,0,1],[0,0,1,0]])

我应该得到[1,0,1,1]，[1,0,1,1]，[1,0,1,1]，[1,0,1,1]]

I should be getting [[1,0,1,1],[1,0,1,1],[1,0,1,1],[1,0,1,1]]

我越来越[0,0,0,1]，[1,0,1,1]，[1,0,1,1]，[0,0,1,1]]

Am getting [[0,0,0,1],[1,0,1,1],[1,0,1,1],[0,0,1,1]]

推荐答案

在讲座中，索引是从1到n，但在这里，你必须从0到去N-1，因此范围函数必须是范围（0，N）或，更简明范围（N）（还，这是返回，而不是M）

in the lecture, indexes are from 1 to n, but here, you have to go from 0 to n-1, so the range function must be range(0,n) or, more concisely range(n) (also, it's return a, not M)

def warshall(a):
    assert (len(row) == len(a) for row in a)
    n = len(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                a[i][j] = a[i][j] or (a[i][k] and a[k][j])
    return a

这篇关于沃肖尔的算法传递闭（蟒蛇）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！