Python网格搜索类问题：BFS执行后返回全零数组排查

你的代码存在多个关键问题，导致BFS无法正确执行，最终返回全零数组：

核心问题点 #

• 参数不匹配：__init__中调用self.bfs(start_row, start_col)传入两个参数，但bfs方法只定义了一个参数s，运行时会直接报错。
• 二维网格与一维邻接表混淆：原BFS代码是为一维邻接表设计的，但你的场景是二维网格，节点是(行,列)坐标，不是单个整数。
• visited初始化错误：max(self.graph)试图对二维数组取最大值，实际得到的是某一行的列表，无法和整数做加法，会抛出类型错误。
• 队列操作错误：queue.pop()默认从列表末尾弹出元素，这是栈的行为（DFS逻辑），BFS需要从队首弹出，应该用queue.pop(0)或collections.deque的popleft()。
• 语法错误：queue.append[i]是错误写法，正确的是queue.append(i)。
• 未记录遍历结果：原代码仅标记节点是否访问，没有将BFS的遍历顺序或结果写入self.graph，所以最终还是全零数组。

修正后的完整代码 #

下面是实现了二维网格BFS和DFS的类，会将遍历顺序标记到网格中：

from collections import deque

class Graph:
    def __init__(self, start_row: int, start_col: int, size_row: int, size_col: int):
        # 初始化全零网格
        self.graph = [[0] * size_col for _ in range(size_row)]
        # 检查起点是否在网格范围内
        if 0 <= start_row < size_row and 0 <= start_col < size_col:
            # 执行BFS并记录结果
            self.bfs(start_row, start_col)
            # 如果需要执行DFS，取消下面注释
            # self.dfs(start_row, start_col)
        else:
            raise ValueError("起点坐标超出网格范围")

    def bfs(self, start_row: int, start_col: int):
        # 网格的行、列数
        rows, cols = len(self.graph), len(self.graph[0])
        # 初始化visited矩阵，记录节点是否被访问
        visited = [[False for _ in range(cols)] for _ in range(rows)]
        # 使用deque实现队列，popleft()效率更高
        queue = deque()
        # 标记起点为已访问，加入队列，同时记录遍历顺序（从1开始）
        visited[start_row][start_col] = True
        queue.append((start_row, start_col))
        step = 1
        self.graph[start_row][start_col] = step

        # 定义四个方向：上、下、左、右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while queue:
            # 从队首取出当前节点
            row, col = queue.popleft()
            # 遍历四个相邻方向
            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc
                # 检查相邻节点是否在网格内且未被访问
                if 0 <= new_row < rows and 0 <= new_col < cols and not visited[new_row][new_col]:
                    visited[new_row][new_col] = True
                    step += 1
                    self.graph[new_row][new_col] = step
                    queue.append((new_row, new_col))

    def dfs(self, start_row: int, start_col: int):
        rows, cols = len(self.graph), len(self.graph[0])
        visited = [[False for _ in range(cols)] for _ in range(rows)]
        step = 1

        def dfs_helper(row, col):
            nonlocal step
            # 边界检查和访问检查
            if row < 0 or row >= rows or col < 0 or col >= cols or visited[row][col]:
                return
            # 标记访问并记录顺序
            visited[row][col] = True
            self.graph[row][col] = step
            step += 1
            # 递归遍历四个方向
            dfs_helper(row-1, col)
            dfs_helper(row+1, col)
            dfs_helper(row, col-1)
            dfs_helper(row, col+1)

        dfs_helper(start_row, start_col)

# 测试代码
def test_graph():
    # 创建8行9列的网格，起点(3,5)
    g = Graph(3, 5, 8, 9)
    # 打印BFS遍历后的网格
    for row in g.graph:
        print(row)

test_graph()

代码说明 #

1. 参数校验：初始化时检查起点是否在网格范围内，避免越界错误。
2. BFS实现：
   • 使用collections.deque实现队列，保证队首弹出的效率。
   • 用二维visited矩阵记录节点访问状态。
   • 定义四个方向数组，遍历当前节点的上下左右相邻节点。
   • 将遍历顺序（从1开始的整数）写入self.graph，替代原来的全零值。
3. DFS实现：采用递归方式，同样记录遍历顺序到网格中，可根据需求选择执行BFS或DFS。
4. 测试逻辑：创建实例后打印网格，能直接看到遍历结果。

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