使用Numpy计算传递闭包矩阵结果异常，请求排查

我尝试用Python计算有向图邻接矩阵的传递闭包，但代码运行后每次输出结果都不一样，而且我预期第2行全为0（该顶点无法到达任何其他顶点），实际结果却和预期不符。以下是我的代码和多次运行的输出，希望找出问题所在：

我的代码 #

import numpy as np

def checkReach(mat):
    ''' Creates the reachablity table to check whether the given route is possible in the case of a directional graph/matrix'''
    order = len(mat)
    sum = np.empty([order, order], int)
    prev = np.identity(order, int)
    for i in range(order):
        prev = np.dot(prev, mat)
        prev[prev > 1] = 1
        prev[prev < 1] = 0
        sum = np.array(sum)+ np.array(prev)
    
    sum[sum > 1] = 1
    sum[sum < 1] = 0
    return sum

if __name__ == '__main__':
    adj_mat = [
    #   [0,1,2,3,4,5,6,7,8,9]   Headings
        [0,1,1,0,1,0,0,0,0,0],  # 0th row
        [1,0,1,0,0,0,0,0,0,0],  # 1st row
        [0,0,0,0,0,0,0,0,0,0],  # 2nd row
        [0,0,0,0,1,1,1,0,0,0],  # 3rd row
        [1,0,0,1,0,0,0,1,0,0],  # 4th row
        [0,0,0,1,0,0,1,1,1,0],  # 5th row
        [0,0,0,1,0,1,0,0,0,0],  # 6th row
        [0,0,0,0,1,1,0,0,1,0],  # 7th row
        [0,0,0,0,0,1,0,1,0,1],  # 8th row
        [0,0,0,0,0,0,0,0,1,0]   # 9th row
    ]
    sum = checkReach(adj_mat)
    print(sum)

预期与实际输出 #

我预期输出的第2行全为0，但多次运行结果如下：

第一次运行结果 #

[[1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 0]]

第二次运行结果 #

[[1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [0 0 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]]

第三次运行结果 #

[[1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1 1 1]]

问题分析与修复 #

核心问题 #

1. 未初始化sum数组：np.empty([order, order], int)创建的数组包含随机垃圾值，每次运行时这些值不同，导致累加结果不稳定。
2. 算法逻辑偏差：循环中矩阵乘法的累加逻辑未准确覆盖所有路径长度，且数值累加不如逻辑判断直观可靠。

修复后的代码 #

import numpy as np

def checkReach(mat):
    '''计算有向图邻接矩阵的传递闭包'''
    order = len(mat)
    # 初始化可达矩阵为全0，用于记录所有可达路径
    reach = np.zeros([order, order], dtype=int)
    # 初始为单位矩阵，代表自身到自身可达
    current = np.identity(order, dtype=int)
    
    for _ in range(order):
        current = np.dot(current, mat)
        # 大于1的值置为1，代表存在路径
        current[current > 1] = 1
        # 用逻辑或累加所有可达性
        reach = np.logical_or(reach, current).astype(int)
    
    return reach

if __name__ == '__main__':
    adj_mat = [
        [0,1,1,0,1,0,0,0,0,0],
        [1,0,1,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,1,1,1,0,0,0],
        [1,0,0,1,0,0,0,1,0,0],
        [0,0,0,1,0,0,1,1,1,0],
        [0,0,0,1,0,1,0,0,0,0],
        [0,0,0,0,1,1,0,0,1,0],
        [0,0,0,0,0,1,0,1,0,1],
        [0,0,0,0,0,0,0,0,1,0]
    ]
    reach_matrix = checkReach(adj_mat)
    print(reach_matrix)

修复说明 #

• 用np.zeros初始化可达矩阵，彻底避免垃圾值干扰。
• 使用np.logical_or替代数值累加，直接判断是否存在任意长度的可达路径，逻辑更清晰。
• 保留单位矩阵的初始值，确保每个顶点自身可达（若不需要该规则，可在最后将对角线置0）。

运行修复后的代码，第2行将稳定输出全0，符合预期。

内容的提问来源于stack exchange，提问作者bokku