无向图的邻接矩阵表示转换为邻接表表示函数题

### 将无向图的邻接矩阵转换为邻接表 为了实现从无向图的邻接矩阵到邻接表的转换，可以设计如下算法。此过程涉及遍历整个邻接矩阵并构建相应的链表结构来表示每一对相邻节点。 #### Python 实现代码： ```python class Node: def __init__(self, vertex, weight=0, next=None): self.vertex = vertex # 节点索引 self.weight = weight # 边权重，默认为0适用于未加权图 self.next = next # 下一个节点指针 def matrix_to_adjlist(matrix, vertices): """ 把给定的无向图的邻接矩阵matrix转成邻接表形式。 参数: matrix -- 图的邻接矩阵，其中matrix[i][j]代表顶点i和j之间的边权重；如果不存在这样的边，则设为None或特殊标记如无穷大。 vertices -- 表示各个顶点名称列表 返回值: adj_list -- 邻接表字典，键是顶点名字符串，值是由Node对象组成的单链表头部引用。 """ n = len(vertices) # 初始化空的邻接表 adj_list = {v: None for v in vertices} for i in range(n): # 对于每一个起点vertex_i prev_node = None # 记录前驱结点用于建立新连接 curr_head = adj_list[vertices[i]] # 当前顶点对应的链表头 for j in range(i+1, n): # 只需考虑上三角部分即可因为是对称关系 if matrix[i][j]: new_node = Node(vertex=j, weight=matrix[i][j]) if not curr_head: # 如果当前顶点还没有任何邻居 adj_list[vertices[i]] = new_node prev_node = new_node else: # 否则追加到已有链表后面 while prev_node and prev_node.next is not None: prev_node = prev_node.next prev_node.next = new_node # 添加反方向的边（由于这是无向图） opposite_new_node = Node(vertex=i, weight=matrix[i][j]) if not adj_list[vertices[j]]: adj_list[vertices[j]] = opposite_new_node else: temp = adj_list[vertices[j]] while temp.next is not None: temp = temp.next temp.next = opposite_new_node return adj_list ``` 上述方法通过双重循环访问了输入`matrix`中的每一项，并创建了一个新的数据结构——邻接表来保存这些信息[^2]。注意这里只处理了一半的数据(`for j in range(i+1,n)`),这是因为考虑到无向图的特点，在另一侧会有相同的关系存在，所以不需要重复记录两次相同的边[^3]。