将邻接矩阵转换为邻接表表示图

基础概念

邻接矩阵是一种表示图的数据结构，其中矩阵的行和列分别代表图中的顶点，矩阵中的元素表示两个顶点之间的连接关系。如果顶点 i 和顶点 j 之间有边，则矩阵的第 i 行第 j 列的元素为 1（或边的权重），否则为 0。

邻接表是另一种表示图的数据结构，它为每个顶点维护一个列表，列表中包含所有与该顶点相邻的顶点及其边的权重。

转换过程

将邻接矩阵转换为邻接表的过程如下：

初始化邻接表：创建一个列表，列表中的每个元素是一个字典，字典包含两个键：“vertex”表示顶点，“weight”表示边的权重。
遍历邻接矩阵：对于邻接矩阵中的每一个元素，如果元素的值不为 0，则在对应的邻接表中添加一条记录。
构建邻接表：将所有顶点的邻接信息存储在邻接表中。

代码示例

以下是一个 Python 示例代码，展示如何将邻接矩阵转换为邻接表：

def adjacency_matrix_to_list(matrix):
    n = len(matrix)  # 图的顶点数
    adj_list = []  # 初始化邻接表
    
    for i in range(n):
        vertex_adj = []  # 当前顶点的邻接列表
        for j in range(n):
            if matrix[i][j] != 0:
                vertex_adj.append({"vertex": j, "weight": matrix[i][j]})
        adj_list.append(vertex_adj)
    
    return adj_list

# 示例邻接矩阵
adj_matrix = [
    [0, 1, 0, 2],
    [1, 0, 3, 0],
    [0, 3, 0, 4],
    [2, 0, 4, 0]
]

# 转换为邻接表
adj_list = adjacency_matrix_to_list(adj_matrix)
print(adj_list)

输出结果

[
    [{'vertex': 1, 'weight': 1}, {'vertex': 3, 'weight': 2}],
    [{'vertex': 0, 'weight': 1}, {'vertex': 2, 'weight': 3}],
    [{'vertex': 1, 'weight': 3}, {'vertex': 3, 'weight': 4}],
    [{'vertex': 0, 'weight': 2}, {'vertex': 2, 'weight': 4}]
]

应用场景

邻接矩阵适用于稠密图（边数接近顶点数的平方），因为它的空间复杂度是 O(V^2)，其中 V 是顶点数。
邻接表适用于稀疏图（边数远小于顶点数的平方），因为它的空间复杂度是 O(V + E)，其中 E 是边数。

优势

邻接矩阵的优势在于可以快速检查两个顶点之间是否有边（O(1) 时间复杂度），并且可以方便地获取边的权重。
邻接表的优势在于节省空间，特别是对于稀疏图，并且可以方便地遍历一个顶点的所有邻接顶点。

遇到的问题及解决方法

问题：在转换过程中，可能会遇到矩阵元素为负数或非数字的情况。

原因：这可能是由于输入数据不正确或矩阵表示有误。

解决方法：在转换之前，检查矩阵中的每个元素是否为有效的边权重（通常是正数或 0）。如果不是，可以抛出异常或进行相应的处理。

def adjacency_matrix_to_list(matrix):
    n = len(matrix)
    adj_list = []
    
    for i in range(n):
        vertex_adj = []
        for j in range(n):
            if not isinstance(matrix[i][j], (int, float)) or matrix[i][j] < 0:
                raise ValueError(f"Invalid weight at position ({i}, {j}): {matrix[i][j]}")
            if matrix[i][j] != 0:
                vertex_adj.append({"vertex": j, "weight": matrix[i][j]})
        adj_list.append(vertex_adj)
    
    return adj_list

通过这种方式，可以确保转换过程的正确性和鲁棒性。