网格上的 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 / 61
已访问
0
前沿
1
当前
—
0 / 61
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 / 常见坑
在错误的时刻标记已访问。
应该在入队那一刻就把格子标为已访问,而不是出队时再标 —— 否则同一个格子会在被处理前被多次压入。对 BFS 来说,这会破坏最短路不变式; 对两者来说,都会让内存膨胀。
在顺序至关重要时混用 BFS 与 DFS。
无权图上的最短路问题必须用 BFS。DFS 不会给出最短路 —— 它沿一个方向一路走到底,只有遇到死胡同才回溯。
DFS 的递归深度。
在 1000×1000 的网格上,递归 DFS 沿一条长路径走下去可能溢出调用栈。 对大规模输入改用显式栈,或者用 BFS 替代。
05 / 去 LeetCode 上练习
中等32
01Word Search— LC 79→02Surrounded Regions— LC 130→03Clone Graph— LC 133→04Number of Islands— LC 200→05Course Schedule— LC 207→06Course Schedule II— LC 210→07Graph Valid Tree— LC 261→08Walls and Gates— LC 286→09Number of Connected Components in an Undirected Graph— LC 323→10Evaluate Division— LC 399→11Pacific Atlantic Water Flow— LC 417→12Minimum Genetic Mutation— LC 433→1301 Matrix— LC 542→14Number of Provinces— LC 547→15Max Area of Island— LC 695→16Open the Lock— LC 752→17Is Graph Bipartite?— LC 785→18All Paths From Source to Target— LC 797→19Keys and Rooms— LC 841→20Possible Bipartition— LC 886→21Snakes and Ladders— LC 909→22Shortest Bridge— LC 934→23Rotting Oranges— LC 994→24Number of Enclaves— LC 1020→25Shortest Path in Binary Matrix— LC 1091→26Shortest Path with Alternating Colors— LC 1129→27As Far from Land as Possible— LC 1162→28Path with Maximum Gold— LC 1219→29Number of Closed Islands— LC 1254→30Number of Operations to Make Network Connected— LC 1319→31Count Sub Islands— LC 1905→32Maximum Number of Fish in a Grid— LC 2658→
困难11
01Word Ladder II— LC 126→02Word Ladder— LC 127→03Word Search II— LC 212→04Number of Islands II— LC 305→05Longest Increasing Path in a Matrix— LC 329→06Reconstruct Itinerary— LC 332→07Robot Room Cleaner— LC 489→08Bus Routes— LC 815→09Making A Large Island— LC 827→10Unique Paths III— LC 980→11Shortest Path in a Grid with Obstacles Elimination— LC 1293→