Python 图的邻接字典实现：避免重复边导致的度数计算错误_网络技术

本文详解如何正确实现基于字典的无向图邻接表表示，重点解决因重复添加边而导致 `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) 成员检查：

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。

遵循以上改进，你的图结构将严格符合无向简单图定义（无自环、无重边），所有接口行为均可稳定通过单元测试。

# python # app # edge

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】