Python生成随机图时邻接表字典未正确填充引发KeyError问题排查

嘿，我瞅见你遇到KeyError的问题了，咱们来捋捋为啥会这样，以及怎么解决～

核心问题：字典键的类型不匹配 #

你代码里的问题根源很清晰：

• 当你调用g.add_vertex(Vertex(s))时，是把**Vertex类的实例对象**作为键存入了adjacency_list字典。
• 但到了添加边的步骤，你传给add_undirected_edge的是字符串类型的顶点标识（比如str(edges[i][0])），这和字典里的键类型完全不匹配，字典找不到对应的键，自然就抛出KeyError了。

另外还有个小细节：原代码里没导入random模块，运行时会先报这个错，记得补上哦。

修正方案：两种思路任选 #

思路1：直接引用Vertex实例（推荐） #

创建顶点时把所有Vertex实例存到一个列表里，后续生成边时直接从列表里取实例来操作，确保和字典的键类型一致：

import random  # 别忘了导入random模块

class Vertex:
    def __init__(self, label):
        self.label = label
        self.distance = float('inf')
        self.pred_vertex = None

class Graph:
    def __init__(self):
        self.adjacency_list = {}
        self.edge_weights = {}

    def add_vertex(self, new_vertex):
        self.adjacency_list[new_vertex] = []

    def add_directed_edge(self, from_vertex, to_vertex, weight = 1.0):
        self.edge_weights[(from_vertex, to_vertex)] = weight
        self.adjacency_list[from_vertex].append(to_vertex)

    def add_undirected_edge(self, vertex_a, vertex_b, weight = 1.0):
        self.add_directed_edge(vertex_a, vertex_b, weight)
        self.add_directed_edge(vertex_b, vertex_a, weight)

g = Graph()
vertices = []  # 用来存储所有Vertex实例

# 添加顶点0-19到图中
for i in range(20):
    vertex = Vertex(str(i))
    vertices.append(vertex)
    g.add_vertex(vertex)

# 生成10条随机无向边（可选去重，避免重复连接同一对顶点）
edges = []
used_pairs = set()
while len(edges) < 10:
    idx1 = random.randint(0, 19)
    idx2 = random.randint(0, 19)
    # 避免自环和重复边
    if idx1 != idx2 and frozenset((idx1, idx2)) not in used_pairs:
        edges.append((vertices[idx1], vertices[idx2]))
        used_pairs.add(frozenset((idx1, idx2)))

# 添加边到图中
for v_a, v_b in edges:
    g.add_undirected_edge(v_a, v_b, random.randint(0, 100))

思路2：维护label到Vertex实例的映射 #

如果需要通过顶点的label（比如字符串"0"）来操作顶点，可以给Graph类加一个字典来映射label和实例，这样就能通过label找到对应的顶点对象：

import random

class Vertex:
    def __init__(self, label):
        self.label = label
        self.distance = float('inf')
        self.pred_vertex = None

class Graph:
    def __init__(self):
        self.adjacency_list = {}
        self.edge_weights = {}
        self.label_to_vertex = {}  # 新增：label -> Vertex实例的映射

    def add_vertex(self, new_vertex):
        self.adjacency_list[new_vertex] = []
        self.label_to_vertex[new_vertex.label] = new_vertex

    def get_vertex(self, label):
        # 通过label获取顶点实例，不存在则返回None
        return self.label_to_vertex.get(label)

    def add_directed_edge(self, from_vertex, to_vertex, weight = 1.0):
        self.edge_weights[(from_vertex, to_vertex)] = weight
        self.adjacency_list[from_vertex].append(to_vertex)

    def add_undirected_edge(self, vertex_a, vertex_b, weight = 1.0):
        self.add_directed_edge(vertex_a, vertex_b, weight)
        self.add_directed_edge(vertex_b, vertex_a, weight)

g = Graph()
l = []

# 添加顶点0-19到图中
for i in range(20):
    l.append(i)
    s = str(i)
    g.add_vertex(Vertex(s))

# 生成随机边
edges = [[random.choice(l), random.randrange(0, 20)] for i in range(10)]

# 添加边到图中
for edge in edges:
    # 通过label获取顶点实例
    v_a = g.get_vertex(str(edge[0]))
    v_b = g.get_vertex(str(edge[1]))
    # 确保两个顶点都存在再添加边
    if v_a and v_b and v_a != v_b:
        g.add_undirected_edge(v_a, v_b, random.randint(0, 100))

总结 #

不管选哪种思路，核心都是确保添加边时传入的顶点对象和adjacency_list字典中的键类型一致，这样就能避免KeyError啦。

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