如何将给定adjacency matrix（邻接矩阵）转换为目标格式adjacency list（邻接表）

你提供的是无向带权图的邻接矩阵，矩阵中matrix[i][j]的数值代表节点i到节点j的边权，值为0代表两个节点之间没有直接连通的边，转换逻辑非常直接：

核心步骤 #

• 初始化一个长度和邻接矩阵行数相等的空列表作为邻接表，列表的每个下标对应一个源节点，对应位置存储该节点的所有出边信息
• 遍历邻接矩阵的每一行，当前行号即为源节点u
• 对当前行的每一列进行遍历，当前列号即为目标节点v
• 若当前位置的数值matrix[u][v]大于0，说明u到v存在有效边，将(v, matrix[u][v])元组插入到邻接表下标为u的列表中即可

代码示例（Python） #

def adjacency_matrix_to_list(matrix):
    node_count = len(matrix)
    adjacency_list = [[] for _ in range(node_count)]
    for u in range(node_count):
        for v in range(node_count):
            weight = matrix[u][v]
            if weight > 0:
                adjacency_list[u].append((v, weight))
    return adjacency_list

# 代入你的输入测试
input_matrix = [[0, 1, 0, 4], [1, 0, 3, 1], [0, 3, 0, 2], [4, 1, 2, 0]]
result = adjacency_matrix_to_list(input_matrix)
print(result)
# 输出结果与你给出的目标完全一致：[[(1, 1), (3, 4)], [(0, 1), (2, 3), (3, 1)], [(1, 3), (3, 2)], [(0, 4), (1, 1), (2, 2)]]

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