字典实现图邻接表：get_number_of_adjacent_vertices测试失败求助

我用字典实现了图的邻接表表示，编写了GraphAdjacencyDictionary类代码，但其中get_number_of_adjacent_vertices方法触发断言错误：5 == 4。我认为自己的代码正确，怀疑测试用例存在错误，恳请帮忙验证该猜想。

代码如下：

from typing import List

class GraphAdjacencyDictionary:

    def __init__(self, number_of_vertices: int):
        self.dic = {}
        for i in range(number_of_vertices):
            self.dic[i] = []

    def add_new_edge(self, vertex1: int, vertex2: int):
        self.dic[vertex1].append(vertex2)
        self.dic[vertex2].append(vertex1)
        print(self.dic)

    def get_list_of_adjacent_vertices(self, vertex: int) -> List[int]:
        res = []
        for i in self.dic:
            res.append(1) if i in self.dic[vertex] else res.append(0)
        return res

    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_number_of_adjacent_vertices方法逻辑是直接返回顶点邻接列表的长度，但你的add_new_edge方法没有做重复边的校验——每次调用都会往两个顶点的邻接列表里追加节点，哪怕这条边已经存在。

举个例子：如果测试用例中给某个顶点添加了4条不同的边，但不小心重复调用了一次add_new_edge添加其中某条边，那该顶点的邻接列表会包含5个元素（比如[1,2,3,4,1]），此时get_number_of_adjacent_vertices返回5，但测试用例期望的是不同邻接节点的数量4（因为无向图中每条边只算一次）。

这种情况下，断言错误的原因不是测试用例出错，而是你的代码没有处理重复边的场景，导致统计的是边的总添加次数，而非实际不同邻接节点的数量。

修复方向 #

如果要符合测试用例的预期（统计不同邻接节点数），可以二选一：

• 修改add_new_edge，添加前检查边是否已存在：

  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)
      print(self.dic)
  

• 或者修改get_number_of_adjacent_vertices，返回去重后的邻接节点数量：

  def get_number_of_adjacent_vertices(self, vertex: int) -> int:
      return len(set(self.dic[vertex]))
  

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