本文详解如何正确实现基于字典的无向图邻接表表示，重点解决因未去重添加边而导致 `get_number_of_adjacent_vertices` 返回错误值的问题，并提供健壮、高效的修复方案。
在使用字典实现无向图的邻接表（GraphAdjacencyDictionary）时，一个常见但隐蔽的陷阱是：未对重复边进行校验。你当前的 add_new_edge 方法会无条件将 vertex2 追加到 self.dic[vertex1]，同时将 vertex1 追加到 self.dic[vertex2]。若测试用例中多次调用 add_new_edge(1, 2)，就会导致邻接列表中出现重复顶点（如 [2, 2, 2]），进而使 len(self.dic[vertex]) 返回错误的“度数”——这正是 AssertionError: 5 == 4 的根源：实际存了 5 个元素，但逻辑上应只有 4 个唯一邻接点。
✅ 正确做法：添加存在性检查
最直接的修复是在插入前判断目标顶点是否已存在：
def add_new_edge(self, vertex1: int, vertex2: int):
if vertex2 not in self.dic[vertex1]:
self.dic[vertex1].append(vertex2)
self.dic[vertex2].append(vertex1)此修改确保每条无向边仅被记录一次，从而保证 get_number_of_adjacent_vertices 返回真实的邻接顶点数量（即顶点度数）。
⚠️ 更优方案：用 set 替代 list 存储邻接顶点
虽然上述修复有效，但 list 的 in 操作时间复杂度为 O(n)，且需手动维护去重逻辑。更符合图结构语义、性能更优的做法是改用 set：
立即学习“Python免费学习笔记（深入）”；
def __init__(self, number_of_vertices: int):
self.dic = {i: set() for i in range(number_of_vertices)}
def add_new_edge(self, vertex1: int, vertex2: int):
self.dic[vertex1].add(vertex2) # 自动去重，O(1) 平均复杂度
self.dic[vertex2].add(vertex1)
def get_list_of_adjacent_vertices(self, vertex: int) -> List[int]:
# 注意：原方法逻辑有误 —— 它返回的是全 0/1 序列（类似邻接矩阵行），而非邻接顶点列表
# 若需求是“返回邻接顶点索引列表”，应改为：
return list(self.dic[vertex])
def get_number_of_adjacent_vertices(self, vertex: int) -> int:
return len(self.dic[vertex]) # 现在始终准确反映唯一邻接点数量
def is_edge(self, vertex1: int, vertex2: int) -> bool:
return vertex2 in self.dic[vertex1]? 关键提醒：你原版 get_list_of_adjacent_vertices 方法实际实现的是“邻接矩阵的某一行”（长度为总顶点数，值为 0/1），而非邻接表意义上的“邻接顶点列表”。请根据实际测试用例需求确认接口语义——多数图算法库中该方法应返回 [v2, v3, v5] 这类明确的邻居列表。
总结
- ❌ 错误根源：add_new_edge 未判重，导致邻接列表含冗余项，破坏度数计算准确性；
- ✅ 快速修复：添加 if not in 判断；
- ? 推荐升级：用 set 实现邻接集合，兼顾正确性、性能与可读性；
- ? 额外建议：单元测试中应包含重复加边用例（如连续两次 add_new_edge(0, 1)），以验证去重逻辑鲁棒性。
