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

Question

Trying to write a code to convert a graph representation from adjacency list to adjacency matrix.

该函数应输入邻接表 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

任何人都可以帮助解决这个问题以获得工作代码吗？

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. ]]

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

Converting adjacency list to adjacency matrix in python

python

function

adjacency-list

adjacency-matrix

加权邻接矩阵