蓝桥杯python备赛笔记之（六）搜索&BFS&DFS

困死，根本不会

588人浏览 · 2026-03-10 09:16:34

困死，根本不会 · 2026-03-10 09:16:34 发布

整篇笔记共分为十章，都是博主在准备25年蓝桥杯时所写，听的网课是这个，讲的非常好，很适合零基础速成，如果有听不懂的可以多听几遍

https://www.bilibili.com/video/BV1Zs9VYrEgg?spm_id_from=333.788.videopod.sections&vd_source=5edde23df276e6fb4a94821fa44f38b5

目录如下：

1.Python语法基础及算法入门
2.语法进阶&常用数据结构&算法入门
3.贪心&排序
4.哈希&暴力&前缀
5.二分查找&二分答案
6.搜索&BFS&DFS
7.[数据结构]并查集&堆
8.动态规划
9.图论
10.数论基础&日期问题

一、网格模型 BFS（广度优先搜索）

1. 核心概念

2. 网格 BFS 核心原理

3. 网格 BFS 关键实现细节（Python）

（1）方向向量（核心）

（2）队列实现

（3）已访问标记

4. 网格 BFS 通用模板（Python）

3. 网格 DFS 关键实现细节（Python）

（1）递归深度限制

（2）回溯标记

（3）方向向量

4. 网格 DFS 通用模板（递归版，Python）

5. 非递归 DFS（栈实现，解决递归深度问题）

三、BFS 与 DFS 的对比与选型（蓝桥杯实战关键）

论文投稿：
第八届信息科学、电气与自动化工程国际学术会议（ISEAE 2026）
大会官网：https://ais.cn/u/nUjQ7f
大会时间：2026年4月18-20日
大会地点：中国-黑龙江-大庆市

一、网格模型 BFS（广度优先搜索）

1. 核心概念

BFS（Breadth-First Search）即广度优先搜索，按层遍历是其核心特征。在蓝桥杯常考的二维网格模型中，BFS 适用于给定初始位置、按指定蔓延条件，求解最短路径、区域计数、蔓延最值、连通块统计等问题，是网格类问题的高频解法。

2. 网格 BFS 核心原理

利用队列存储待遍历的网格位置（坐标），队列的 “先进先出” 特性保证遍历的层序性；
初始化队列：将所有初始位置一次性加入队列，并标记为已访问（避免重复遍历）；
层序遍历：每次从队列取出队首位置，遍历其上下左右四个相邻方向；
合法性判断：相邻位置需满足「网格边界内 + 未被访问 + 符合蔓延条件」，满足则加入队列并标记已访问；
循环执行，直到队列为空，过程中统计结果（计数 / 最值）。

3. 网格 BFS 关键实现细节（Python）

（1）方向向量（核心）

定义上下左右四个方向的坐标偏移量，简化相邻位置遍历：

# 上、下、左、右四个方向
dirs = [(-1,0), (1,0), (0,-1), (0,1)]

（2）队列实现

Python 中用deque（双端队列）实现，popleft()为 O (1) 时间复杂度，远优于列表pop(0)的 O (n)，避免蓝桥杯数据量大时超时：

from collections import deque
q = deque()
# 入队：初始位置(x0,y0)
q.append((x0, y0))
# 出队
x, y = q.popleft()

（3）已访问标记

两种常用方式，根据题目场景选择：

原地修改网格：将已访问位置设为特殊值（如网格是 0/1 矩阵，访问后设为 1），节省空间；
单独创建访问矩阵：visited = [[False for _ in range(cols)] for _ in range(rows)]，不破坏原网格，适合需要复用网格的场景。

4. 网格 BFS 通用模板（Python）

from collections import deque

def bfs(grid, start_pos):
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]  # 四方向
    visited = [[False]*cols for _ in range(rows)]
    q = deque()
    
    # 初始化：加入所有初始位置
    for x, y in start_pos:
        if 0<=x<rows and 0<=y<cols:
            q.append((x, y))
            visited[x][y] = True
    
    res = 0  # 结果变量，根据题目定义（计数/步数等）
    while q:
        # 层序遍历：若需统计步数/层数，加此循环
        size = len(q)
        for _ in range(size):
            x, y = q.popleft()
            # 题目核心逻辑：如计数、更新状态等
            res += 1
            # 遍历四方向
            for dx, dy in dirs:
                nx = x + dx
                ny = y + dy
                # 合法性判断：边界+未访问+蔓延条件（如grid[nx][ny]==0）
                if 0<=nx<rows and 0<=ny<cols and not visited[nx][ny] and grid[nx][ny]==0:
                    visited[nx][ny] = True
                    q.append((nx, ny))
    return res

5. 蓝桥杯网格 BFS 典型考法

最短路径：从起点到终点的最少步数（层序的层数即为步数）；
区域蔓延：初始位置按条件蔓延，求最终覆盖的网格数；
多源 BFS：多个初始位置同时蔓延（如多个传染源），求全部覆盖的最短时间；
连通块：统计网格中符合条件的连通区域数量（每次 BFS 遍历一个连通块，计数 + 1）。

二、DFS（深度优先搜索）

1. 核心概念

DFS（Depth-First Search）即深度优先搜索，沿着一条路径遍历到底，再回溯是其核心特征。相比 BFS，DFS 更适合解决网格连通性、排列组合、子集、路径存在性、暴力枚举等问题，在蓝桥杯中常考网格 DFS和普通 DFS（组合 / 排列）两类，Python 中可通过递归快速实现（注意递归深度限制）。

2. 网格 DFS 核心原理

从起始位置出发，遍历其上下左右四方向；
对每个合法方向（边界内 + 未访问 + 符合条件），递归访问该位置；
递归结束后回溯（若使用单独的访问矩阵，需恢复未访问状态；若原地修改，需恢复原值）；
遍历完所有路径后，统计结果（如连通块数、路径数）。

3. 网格 DFS 关键实现细节（Python）

（1）递归深度限制

Python 默认递归深度约1000，若蓝桥杯题目中网格规模超过 1000（如 1000*1000 网格），递归 DFS 会报RecursionError，此时需改用 ** 非递归 DFS（栈实现）** 或 BFS。

（2）回溯标记

与 BFS 一致，支持原地修改网格和访问矩阵两种方式，原地修改在网格 DFS 中更常用（减少空间开销），递归回溯时需恢复原值。

（3）方向向量

与 BFS 完全相同，使用dirs = [(-1,0), (1,0), (0,-1), (0,1)]简化遍历。

4. 网格 DFS 通用模板（递归版，Python）

def dfs(grid, x, y, visited):
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    # 终止条件：越界+已访问+不满足蔓延条件
    if x<0 or x>=rows or y<0 or y>=cols or visited[x][y] or grid[x][y]!=0:
        return
    # 标记已访问
    visited[x][y] = True
    # 题目核心逻辑：如计数、记录路径等
    global res  # 或使用非局部变量nonlocal
    res += 1
    # 遍历四方向递归
    for dx, dy in dirs:
        dfs(grid, x+dx, y+dy, visited)

# 主调用
grid = [[]]  # 输入的二维网格
rows = len(grid)
cols = len(grid[0]) if rows else 0
visited = [[False]*cols for _ in range(rows)]
res = 0
# 遍历所有网格，处理多连通块
for i in range(rows):
    for j in range(cols):
        if not visited[i][j] and grid[i][j]==0:
            dfs(grid, i, j, visited)
            # 若统计连通块数，加此计数
            # count +=1
print(res)

5. 非递归 DFS（栈实现，解决递归深度问题）

用栈模拟递归的调用过程，核心是 “入栈 = 递归调用，出栈 = 回溯”，适合大规模网格：

def dfs_non_recursive(grid, start_x, start_y):
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    visited = [[False]*cols for _ in range(rows)]
    stack = [(start_x, start_y)]
    visited[start_x][start_y] = True
    res = 0
    while stack:
        x, y = stack.pop()  # 栈：先进后出
        res +=1
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 0<=nx<rows and 0<=ny<cols and not visited[nx][ny] and grid[nx][ny]==0:
                visited[nx][ny] = True
                stack.append((nx, ny))
    return res

6. 蓝桥杯 DFS 典型考法

（1）网格类

统计网格中符合条件的连通块数量（如 0 的连通块、岛屿数量）；
判断网格中是否存在从起点到终点的路径；
求网格中符合条件的最长路径（DFS 遍历所有路径，记录最大值）。

（2）组合 / 排列类

子集问题：从 n 个数中选 k 个的所有组合；
排列问题：n 个数的全排列 / 部分排列；
暴力枚举：蓝桥杯部分填空题，DFS 暴力枚举所有可能解（简单高效）。

7. DFS 剪枝技巧（蓝桥杯必学）

DFS 易出现超时问题，核心优化手段是剪枝，提前排除不可能的路径：

可行性剪枝：若当前路径已不满足题目条件，直接返回；
最优性剪枝：若当前结果已超过已知最优解，直接返回；
记忆化搜索：记录已计算的状态，避免重复递归（如 DFS + 动态规划）。

三、BFS 与 DFS 的对比与选型（蓝桥杯实战关键）

表格

特性	BFS	DFS
遍历方式	层序遍历，按距离扩散	深度遍历，回溯探索
数据结构	队列（deque）	栈 / 递归调用栈
核心优势	求最短路径 / 最值，结果唯一	求所有路径 / 组合，适合暴力枚举
空间复杂度	最坏 O (rows*cols)	最坏 O (rows*cols)
时间复杂度	O (rows*cols)（每个位置仅访问一次）	O (rows*cols)（每个位置仅访问一次）
递归问题	无递归，无深度限制	递归版有深度限制，需非递归优化
典型场景	网格最短路径、多源蔓延、最少步数	连通块统计、排列组合、路径存在性、最长路径