无法修改Node类时如何在其实例图上实现BFS并追踪访问状态

因为无法修改Node类且不能使用字典，这里提供几种可行的已访问节点追踪方式：

方法1：用列表存储已访问节点 #

直接用列表保存所有遍历过的Node实例，处理新节点前检查是否在列表中。实现简单，适合小规模图：

from collections import deque

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def bfs_with_list(root):
    if not root:
        return []
    queue = deque([root])
    visited = []
    result = []
    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.append(node)
        result.append(node.val)
        # 可根据图的邻接逻辑扩展，比如这里的left/right
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

方法2：使用weakref.WeakSet（推荐） #

weakref.WeakSet专门存储对象的弱引用，不会阻止对象被垃圾回收，且基于对象身份判断存在性，查找效率为O(1)，适合大规模图：

import weakref
from collections import deque

def bfs_with_weakset(root):
    if not root:
        return []
    queue = deque([root])
    visited = weakref.WeakSet()
    result = []
    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

方法3：利用对象id存集合 #

每个Python对象都有唯一的id()，将节点id存入集合，通过判断id是否存在追踪访问状态，效率为O(1)：

from collections import deque

def bfs_with_id_set(root):
    if not root:
        return []
    queue = deque([root])
    visited_ids = set()
    result = []
    while queue:
        node = queue.popleft()
        node_id = id(node)
        if node_id in visited_ids:
            continue
        visited_ids.add(node_id)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

注意事项 #

• 若Node类重写了__eq__和__hash__方法，列表和WeakSet的判断可能失效，但id()方式不受影响，因为id是对象的唯一标识，与自定义哈希无关。
• 列表方式查找效率较低，节点数量多时不建议使用。

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