python - 在python中将邻接列表转换为邻接矩阵

Question

尝试编写代码将图形表示从邻接列表转换为邻接矩阵。

该函数应输入邻接表adj_list = [[1,2],[2],[],[0,1]]并输出二进制矩阵

adj_mat = [0. 1. 1. 0]
          [0. 0. 1. 0.]
          [0. 0. 0. 0.]
          [1. 1. 0. 0.] 

但是运行代码

 def adj_list_to_matrix(adj_list):
    n = len(adj_list)
    adj_matrix = np.nan * np.ones((n,n))
    np.fill_diagonal(adj_matrix,0)

    for i in range(n):
        for j, w in adj_list[i]:
            adj_matrix[i,j] = w
    return adj_matrix

产生错误信息

for j, w in adj_list[i]:
TypeError: cannot unpack non-iterable int object 

任何人都可以帮助解决此问题以获取工作代码吗？

标签： pythonfunctionadjacency-matrixadjacency-list

Answer 1

for j, w in adj_list[i]:不起作用，因为adj_list[i]它只是一个列表，所以你只能在 for 循环中解压缩一个值。看起来您想w成为一个权重因子，但您的邻接列表没有任何权重。

你可以这样做，假设所有的权重都是 1（我认为这是你想要的，基于你在问题中的预期输出）。

def adj_list_to_matrix(adj_list):
    n = len(adj_list)
    adj_matrix = np.nan * np.ones((n,n))
    np.fill_diagonal(adj_matrix,0)

    for i in range(n):
        for j in adj_list[i]:
            adj_matrix[i,j] = 1
    return adj_matrix

输出

[[ 0.,  1.,  1., nan],
 [nan,  0.,  1., nan],
 [nan, nan,  0., nan],
 [ 1.,  1., nan,  0.]])

加权邻接矩阵

如果你想要一个加权邻接矩阵，你需要把权重放在adj_list这样的地方：

adj_list = [{1:0.2,2:0.5},{2:1},{},{0:0.1,1:0.6}]

然后你的代码只需要一个小的调整就可以工作

def adj_list_to_matrix(adj_list):
    n = len(adj_list)
    adj_matrix = np.nan * np.ones((n,n))
    np.fill_diagonal(adj_matrix,0)

    for i in range(n):
        for j, w in adj_list[i].items():
            adj_matrix[i,j] = w
    return adj_matrix

输出

[[0. , 0.2, 0.5, nan],
 [nan, 0. , 1. , nan],
 [nan, nan, 0. , nan],
 [0.1, 0.6, nan, 0. ]]