本文详解如何正确实现基于字典的无向图邻接表表示，重点解决因重复添加边而导致 `get_number_of_adjacent_vertices` 返回错误顶点度数的问题，并提供健壮、高效的修复方案。
在使用字典实现无向图的邻接表（Adjacency Dictionary）时，一个常见但容易被忽视的问题是：未对重复边进行去重处理。原始代码中 add_new_edge 方法直接将顶点相互追加到对方的邻接列表中，而未检查该边是否已存在。当测试用例中多次调用 add_new_edge(1, 2) 时，顶点 1 的邻接列表会反复加入 2，导致 len(self.dic[vertex])（即顶点度数）被高估——这正是你遇到 AssertionError: 5 == 4 的根本原因：实际应有 4 个邻居，却因重复插入统计为 5。
✅ 正确做法：添加存在性检查
最直接的修复是在插入前判断目标顶点是否已存在于邻接列表中：
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)此修改确保每条无向边 (u, v) 在 dic[u] 和 dic[v] 中各仅出现一次，从而保证 get_number_of_adjacent_vertices 返回真实度数。
⚡ 更优方案：改用 set 存储邻接关系
虽然列表 + 检查可行，但时间复杂度为 O(d)（d 为当前度数），频繁查询效率低。推荐使用 set 替代 list，天然支持去重与 O(1) 成员检查：
立即学习“Python免费学习笔记（深入）”；
from typing import List, Set, Dict
class GraphAdjacencyDictionary:
def __init__(self, number_of_vertices: int):
# 使用 set 而非 list，自动去重、提升查询性能
self.dic: Dict[int, Set[int]] = {i: set() for i in range(number_of_vertices)}
def add_new_edge(self, vertex1: int, vertex2: int):
self.dic[vertex1].add(vertex2) # set.add() 自动忽略重复
self.dic[vertex2].add(vertex1)
def get_list_of_adjacent_vertices(self, vertex: int) -> List[int]:
# 注意：原逻辑有严重语义错误！
# 它返回的是 [0,1,0,1,...] 形式的邻接指示向量（长度=总顶点数），而非邻接顶点列表
# 若需求是“邻接顶点列表”，应直接返回 sorted(list(self.dic[vertex]))
return [1 if i in self.dic[vertex] else 0 for i in range(len(self.dic))]
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 方法当前实现返回的是长度为 n 的 0/1 列表（类似邻接矩阵的一行），而非直观的邻接顶点列表（如 [2, 3, 5]）。若题意要求后者，请改为 return list(self.dic[vertex]) 或 sorted(list(self.dic[vertex])) 以保持顺序一致性。
✅ 总结
- ❌ 错误根源：add_new_edge 无去重 → 邻接列表含重复顶点 → len() 返回错误度数。
- ✅ 快速修复：添加 if not in 检查。
- ⚡ 推荐升级：用 dict[int, set[int]] 替代 dict[int, list[int]]，兼顾正确性、性能与简洁性。
- ? 测试建议：手动验证 add_new_edge(0,1); add_new_edge(0,1) 后 get_number_of_adjacent_vertices(0) 是否恒为 1。
遵循以上改进，你的图结构将严格符合无向简单图定义（无自环、无重边），所有接口行为均可稳定通过单元测试。
