网格上的 BFS / DFS
01 / 一句话本质
从种子出发在隐式图上行走,入队时即把格子标记为已访问 — 队列给出广度(最近优先), 栈给出深度(一条路走到底),其余完全是同一个算法。
题目从 (r, c) 出发,按 4-邻接关系泛洪网格4 × 4起点(0, 0)模式bfs
1
1
1
1
1
·
·
1
1
·
·
1
1
1
1
1
队列 (1)
(0,0)
← 队首从 (0,0) 开始。队列以种子格初始化。
步
0 / 13
已访问
0
前沿
1
当前
—
0 / 13
02 / 模式骨架
# 从 (sr, sc) 开始泛洪visited ← {(sr, sc)}frontier ← [(sr, sc)]while frontier 非空:cell ← frontier. pop_front() // BFS// 或 frontier.pop() // DFSfor cell 的每个 4-邻居:if 在界内、可通行、 未访问:标记为已访问;压入 frontier
03 / 什么时候用这个模式
"网格 / 地图"
问题描述了一个带邻接关系的二维布局 —— 岛屿、迷宫、腐烂的橘子、墙与通路。
"最短 / 最少"
你需要从源点出发的距离 —— 最少步数、最少移动。BFS 一遍即可求出,因为它按层向外扩张。
"可达 / 连通"
你只需要知道哪些格子可达,不在意顺序 —— 两种遍历都行; DFS 用递归写起来通常更简单。
"隐式图"
"顶点"并非预先构造 —— 它们是状态(位置、棋盘局面),由后继函数按需生成。 算法完全相同,变的只是邻居函数。
04 / 常见坑
i.
在错误的时刻标记已访问。
应该在入队那一刻就把格子标为已访问,而不是出队时再标 —— 否则同一个格子会在被处理前被多次压入。对 BFS 来说,这会破坏最短路不变式; 对两者来说,都会让内存膨胀。
ii.
在顺序至关重要时混用 BFS 与 DFS。
无权图上的最短路问题必须用 BFS。DFS 不会给出最短路 —— 它沿一个方向一路走到底,只有遇到死胡同才回溯。
iii.
DFS 的递归深度。
在 1000×1000 的网格上,递归 DFS 沿一条长路径走下去可能溢出调用栈。 对大规模输入改用显式栈,或者用 BFS 替代。
05 / 去 LeetCode 上练习
四道题。前两道是基本的泛洪 / 可达性;第三道把你推进多源 BFS; 第四道把同一个算法搬到隐式图上。