Python水壶问题BFS代码报错：KeyError: <exception str() failed>

问题概述 #

这段代码旨在实现三个水壶的状态搜索，目标是找到任一水壶达到指定容量的操作状态序列，但运行时抛出KeyError: <exception str() failed>错误，同时代码存在多处逻辑缺陷。

错误原因分析 #

1. KeyError根源
   BFS中创建的起始节点start = Graph.GraphNode(0, 0, 0, "white")是全新对象，而self.V字典中的初始(0,0,0)节点是Graph初始化时生成的另一个实例。Python字典按键的对象身份（内存地址）匹配，两个属性相同的节点因不是同一实例无法匹配，导致self.V[a]触发KeyError。此外GraphNode未实现__eq__和__hash__方法，无法让字典识别属性相同的节点为同一键。

2. 邻接关系判断完全错误
   原isAdjacent方法通过self.V[a]==b判断邻接，但self.V的所有值都是None，完全不符合邻接关系的定义——邻接应指两个状态可通过一次合法操作（装满、倒空、互相倾倒）转换。

3. 其他逻辑问题

   • v.color == "gray"是比较运算符而非赋值，无法标记节点状态
   • BFS中找到目标节点后提前return，导致路径只记录单个节点就终止
   • GraphNode未实现__str__方法，打印时触发<exception str() failed>异常
   • self.V字典无实际意义，所有值均为None

修复后的完整代码 #

class Graph:
    class GraphNode:
        def __init__(self, jar1=0, jar2=0, jar3=0, color="white", pi=None):
            self.jar1 = jar1
            self.jar2 = jar2
            self.jar3 = jar3
            self.color = color
            self.pi = pi

        def __eq__(self, other):
            if isinstance(other, Graph.GraphNode):
                return (self.jar1 == other.jar1 and
                        self.jar2 == other.jar2 and
                        self.jar3 == other.jar3)
            return False

        def __hash__(self):
            return hash((self.jar1, self.jar2, self.jar3))

        def __str__(self):
            return f"({self.jar1}, {self.jar2}, {self.jar3})"

        def __repr__(self):
            return self.__str__()

    def __init__(self, jl1=0, jl2=0, jl3=0, target=0):
        self.jl1 = jl1
        self.jl2 = jl2
        self.jl3 = jl3
        self.target = target
        self.visited = set()  # 用集合高效记录已访问节点

    def isFound(self, a: GraphNode) -> bool:
        return self.target in [a.jar1, a.jar2, a.jar3]

    def get_adjacent_nodes(self, current: GraphNode):
        adj_nodes = []
        jars = [('jar1', self.jl1), ('jar2', self.jl2), ('jar3', self.jl3)]
        # 1. 装满某个水壶
        for jar_name, capacity in jars:
            new_vals = [current.jar1, current.jar2, current.jar3]
            idx = ['jar1', 'jar2', 'jar3'].index(jar_name)
            new_vals[idx] = capacity
            new_node = Graph.GraphNode(*new_vals)
            if new_node not in self.visited:
                adj_nodes.append(new_node)
        # 2. 倒空某个水壶
        for jar_name, _ in jars:
            new_vals = [current.jar1, current.jar2, current.jar3]
            idx = ['jar1', 'jar2', 'jar3'].index(jar_name)
            new_vals[idx] = 0
            new_node = Graph.GraphNode(*new_vals)
            if new_node not in self.visited:
                adj_nodes.append(new_node)
        # 3. 互相倾倒：从A倒到B
        pour_pairs = [('jar1', 'jar2'), ('jar1', 'jar3'),
                      ('jar2', 'jar1'), ('jar2', 'jar3'),
                      ('jar3', 'jar1'), ('jar3', 'jar2')]
        from_jar_names = ['jar1', 'jar2', 'jar3']
        for from_jar, to_jar in pour_pairs:
            from_idx = from_jar_names.index(from_jar)
            to_idx = from_jar_names.index(to_jar)
            from_val = [current.jar1, current.jar2, current.jar3][from_idx]
            to_val = [current.jar1, current.jar2, current.jar3][to_idx]
            to_cap = [self.jl1, self.jl2, self.jl3][to_idx]
            # 计算实际倾倒量
            pour_amount = min(from_val, to_cap - to_val)
            new_vals = [current.jar1, current.jar2, current.jar3]
            new_vals[from_idx] -= pour_amount
            new_vals[to_idx] += pour_amount
            new_node = Graph.GraphNode(*new_vals)
            if new_node not in self.visited:
                adj_nodes.append(new_node)
        return adj_nodes

    def BFS(self):
        start = Graph.GraphNode(0, 0, 0)
        queue = [start]
        self.visited.add(start)
        while queue:
            u = queue.pop(0)
            if self.isFound(u):
                # 回溯生成完整路径
                path = []
                while u:
                    path.insert(0, u)
                    u = u.pi
                return path
            # 遍历所有合法邻接节点
            for v in self.get_adjacent_nodes(u):
                v.color = "gray"
                v.pi = u
                self.visited.add(v)
                queue.append(v)
            u.color = "black"
        return []

# 输入处理
j1 = input("第一个水壶容量: ")
j2 = input("第二个水壶容量: ")
j3 = input("第三个水壶容量: ")
t = input("目标容量: ")

jar1 = int(j1)
jar2 = int(j2)
jar3 = int(j3)
target = int(t)

graph1 = Graph(jar1, jar2, jar3, target)
output = graph1.BFS()

if output:
    print("状态序列:")
    for idx, state in enumerate(output):
        print(f"步骤 {idx}: {state}")
else:
    print("无法达到目标容量")

关键修复点 #

• 解决KeyError：给GraphNode实现__eq__和__hash__方法，让属性相同的节点被视为同一键；用visited集合替代无效的self.V字典，高效管理已访问节点。
• 重构邻接逻辑：替换原错误的isAdjacent方法为get_adjacent_nodes，通过生成所有合法操作后的状态获取邻接节点，覆盖装满、倒空、互相倾倒三种操作。
• 修正BFS逻辑：修复赋值错误，调整路径回溯逻辑以生成完整状态序列，提前判断当前节点是否为目标以优化遍历效率。
• 完善节点打印：实现__str__方法，解决节点打印时的异常问题。

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