Python 如何将带权邻接表转换为嵌套列表形式的邻接矩阵

你碰到的ValueError本质是：带权邻接表的每行元素为(邻接点名, 权重)格式的元组，原有代码直接把整个元组当成邻接点名去节点列表中查找，自然会触发元素不存在的报错。
另外你提供的带权邻接表示例存在笔误：'M': [(I, 3), (K, 6)]中的I、K未加引号，运行时会先抛出NameError，需修正为[('I', 3), ('K', 6)]。

相比原有直接调用keys.index()的写法，我们额外增加一层「节点到矩阵索引的映射」，既提升查找效率，也能自动适配两种邻接表格式：

# 1. 获取所有节点并排序，生成节点-索引映射
keys = sorted(g.keys())
node2idx = {node: idx for idx, node in enumerate(keys)}
node_count = len(keys)

# 2. 初始化邻接矩阵
# 若权重可能为0，可将默认值改为`float('inf')`表示无连接
M = [[0] * node_count for _ in range(node_count)]

# 3. 遍历邻接表填充矩阵
for origin_node, neighbor_list in g.items():
    origin_idx = node2idx[origin_node]
    for item in neighbor_list:
        # 自动区分无权/带权场景
        if isinstance(item, tuple):
            # 带权场景：拆出邻接点和权重
            target_node, weight = item
        else:
            # 无权场景：权重默认设为1
            target_node, weight = item, 1
        target_idx = node2idx[target_node]
        M[origin_idx][target_idx] = weight

节点排序后为['I','J','K','L','M']，对应矩阵行/列索引0-4：

• 针对无权邻接表，最终生成的邻接矩阵为：

[
 [0, 1, 1, 0, 1],
 [1, 0, 1, 1, 0],
 [1, 1, 0, 0, 1],
 [0, 1, 0, 0, 0],
 [1, 0, 1, 0, 0]
]

• 针对修正后的带权邻接表，最终生成的邻接矩阵为：

[
 [0, 1, 2, 0, 3],
 [1, 0, 7, 5, 0],
 [2, 7, 0, 0, 6],
 [0, 5, 0, 0, 0],
 [3, 0, 6, 0, 0]
]

注意：如果你的带权图存在权重为0的边，初始化矩阵时不要用0作为默认值，可替换为float('inf')表示节点间无连接，避免和权重为0的边混淆。

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