如何可靠判定Python中两个自定义Graph类实例是否相等

原有基于__repr__输出的相等判断存在本质缺陷：Python处理带自引用的对象字符串输出时，会在递归到循环引用位置后自动用[...]截断内容，根本不会遍历全量节点，只要浅层结构一致，哪怕深层节点val不匹配也会误判为相等；同时如果直接递归比对节点值和邻居，又会因为图的环形结构触发无限递归，最终栈溢出。

更可靠的方案是基于图遍历（BFS/DFS）+ 已访问节点映射实现相等校验，逻辑不会受环形引用影响，也能覆盖所有节点的校验。

核心实现逻辑 #

• 先做空值边界校验：两个图的根节点如果一个为空一个非空，直接判定不等；根节点值不匹配也直接判定不等
• 建立访问映射字典：键为第一个图中已经遍历过的节点，值为第二个图中与之匹配的对应节点，既避免重复遍历，也用来校验邻居对应关系是否正确
• 从根节点开始迭代遍历（BFS/DFS均可）：
  • 每次取出一对待比对的节点，先校验二者的邻居数量，数量不一致直接判定不等
  • 逐位比对两个节点的邻居：如果邻居已经在访问映射中，检查对应关系是否匹配；如果邻居未被访问过，先校验节点值是否一致，一致就存入映射加入遍历队列
• 所有可达节点校验完成无异常，即可判定两个图相等

可直接复用的代码实现 #

from collections import deque

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
    
    def __repr__(self):
        return f"Node(val: {self.val}, neighbors: {self.neighbors})"
    
    def __str__(self):
        return self.__repr__()

class Graph:
    def __init__(self, adj_list=None):
        self.root = self.make_graph(adj_list) if adj_list else None
        
    def __repr__(self):
        return str(self.root) if self.root else "Empty Graph"
    
    def __str__(self):
        return self.__repr__()
    
    def __eq__(self, other):
        if not isinstance(other, self.__class__):
            return False
        # 空图边界判断
        if self.root is None and other.root is None:
            return True
        if self.root is None or other.root is None:
            return False
        if self.root.val != other.root.val:
            return False
        
        # 存储两图节点的匹配映射，避免重复遍历和循环递归
        node_map = {}
        traverse_queue = deque()
        traverse_queue.append((self.root, other.root))
        node_map[self.root] = other.root

        while traverse_queue:
            node_a, node_b = traverse_queue.popleft()
            # 邻居数量不一致直接判定不等
            if len(node_a.neighbors) != len(node_b.neighbors):
                return False
            # 逐位校验邻居匹配关系
            for nei_a, nei_b in zip(node_a.neighbors, node_b.neighbors):
                if nei_a in node_map:
                    # 已访问过的节点，检查对应关系是否正确
                    if node_map[nei_a] is not nei_b:
                        return False
                else:
                    # 未访问节点先校验值是否一致
                    if nei_a.val != nei_b.val:
                        return False
                    node_map[nei_a] = nei_b
                    traverse_queue.append((nei_a, nei_b))
        
        return True
    
    def make_graph(self, adj_list) -> Node:
        nodes = [Node(i + 1) for i in range(len(adj_list))]
        for i, neighbors in enumerate(adj_list):
            nodes[i].neighbors = [nodes[j-1] for j in neighbors]
        return nodes[0]

方案优势 #

• 无递归溢出风险：用迭代方式做BFS遍历，不管图的环结构多复杂、规模多大都能正常运行
• 无漏判问题：所有从根节点可达的节点都会被逐一校验值和邻居对应关系，不存在字符串截断导致的深层节点漏比较
• 性能更优：时间复杂度为O(N)（N为图中节点总数），每个节点仅访问一次，远高于生成、比较长字符串的原方案效率

补充说明 #

• 上述实现和给出的make_graph构造逻辑匹配，默认处理连通无向图场景（从根出发可到达所有节点）。如果需要支持非连通图、有向图，只需要在校验末尾增加对第二个图的全量节点遍历，检查是否存在未被映射到的孤立节点即可。
• 不建议把全图遍历的相等判断逻辑写在Node.__eq__方法中，否则单节点的相等判断会意外触发全图遍历，带来不必要的性能损耗，收敛在Graph.__eq__中更符合类的职责划分。
• __repr__的设计目标是生成面向开发者的调试输出，不是可用于逻辑判断的结构化数据，永远不要依赖__repr__的返回值做业务逻辑判断。

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