运行BFS代码时触发TypeError：缺少graph位置参数的问题求助

问题描述 #

调用search.breadthFirstSearch('San Bernardino', 'Los Angeles', graph)时触发错误：

TypeError: SearchAlgorithms.breadthFirstSearch() missing 1 required positional argument: 'graph'

错误原因 #

1. 参数不匹配：breadthFirstSearch方法定义要求传入start, stack, goal, graph四个参数（不含self），但调用时只传了start, goal, graph三个，缺少stack参数。
2. BFS逻辑错误：原方法用栈（stack.pop()）实现，不符合BFS先进先出的特性，应该用队列。
3. 未初始化变量：方法内使用的path、visited、explored均未提前定义，会引发NameError。

修复步骤 #

1. 调整方法参数：移除多余的stack参数，将方法签名改为def breadthFirstSearch(self, start, goal, graph):，在方法内部初始化队列。
2. 初始化内部变量：在方法内创建visited集合（记录已访问节点）、queue队列（BFS核心结构），并维护路径追踪的字典。
3. 修正BFS逻辑：使用deque.popleft()实现队列的先进先出，替换原栈的pop()操作。
4. 修复返回值：统一返回格式，确保使用已定义的变量。

完整修正代码 #

from queue import PriorityQueue
from pprint import pprint
from collections import deque  # 导入deque用于高效队列操作

graph = {
         "San Bernardino": ["Riverside", "Rancho Cucamonga"], 
         "Riverside": ["San Bernardino", "Ontario", "Pomona"],
         "Rancho Cucamonga": ["San Bernardino", "Azusa", "Los Angeles"],
         "Ontario": ["Riverside", "Whittier", "Los Angeles"],
         "Pomona": ["Riverside", "Whittier", "Azusa", "Los Angeles"], 
         "Whittier": ["Ontario", "Pomona", "Los Angeles"],
         "Azusa": ["Rancho Cucamonga", "Pomona", "Arcadia"], 
         "Arcadia": ["Azusa", "Los Angeles"],
         "Los Angeles": ["Rancho Cucamonga", "Ontario", "Pomona", "Whittier", "Arcadia"]
        }

weights = {('San Bernardino', 'Riverside'): 2,
 ('San Bernardino', 'Rancho Cucamonga'): 1,
 ('Riverside', 'Ontario'): 1,
 ('Riverside', 'Pomona'): 3,
 ('Rancho Cucamonga', 'Los Angeles'): 5,
 ('Pomona', 'Los Angeles'): 2,
 ('Ontario', 'Whittier'): 2,
 ('Ontario', 'Los Angeles'): 3,
 ('Rancho Cucamonga', 'Azusa'): 3,
 ('Pomona', 'Azusa'): 2,
 ('Pomona', 'Whittier'): 2,
 ('Azusa', 'Arcadia'): 1,
 ('Whittier', 'Los Angeles'): 2,
 ('Arcadia', 'Los Angeles'): 2}

heuristic = {'San Bernardino': 4,
 'Riverside': 2,
 'Rancho Cucamonga': 1,
 'Ontario': 1,
 'Pomona': 3,
 'Whittier': 4,
 'Azusa': 3,
 'Arcadia': 2,
 'Los Angeles': 0}

class SearchAlgorithms:
    def breadthFirstSearch(self, start, goal, graph):
        visited = set()
        queue = deque([start])
        # 记录路径：key是当前节点，value是父节点
        parent = {}
        
        while queue:
            current = queue.popleft()  # BFS用popleft实现先进先出
            if current == goal:
                # 回溯构建路径
                path = []
                while current in parent:
                    path.append(current)
                    current = parent[current]
                path.append(start)
                return path[::-1], visited  # 反转得到从start到goal的路径
            if current not in visited:
                visited.add(current)
                for neighbor in graph[current]:
                    if neighbor not in visited and neighbor not in queue:
                        parent[neighbor] = current
                        queue.append(neighbor)
        # 未找到路径的情况
        return [], visited

# 创建类实例
search = SearchAlgorithms() 

# 调用BFS并打印结果
print("Breadth First Search Result")
path, explored = search.breadthFirstSearch('San Bernardino', 'Los Angeles', graph)
print(f"Path: {path}")
print(f"Expanded cities: {explored}")

说明 #

修正后的代码：

• 符合BFS先进先出的核心逻辑，使用deque提升队列操作效率
• 正确追踪路径，返回从起点到终点的完整路径
• 修复了参数不匹配和未初始化变量的问题
• 清晰返回路径和已探索节点集合

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