DFS / BFS 进阶（图搜索 + 回溯 + 扩散）
算法DFSBFS回溯拓扑排序
DFS / BFS 进阶（图搜索 + 回溯 + 扩散）
📖 学习路径： 01 树遍历 → 02 DFS/BFS 进阶 → 03 动态规划
⚠️ 本专题承接 01，不再重复树的遍历题。01 已覆盖：前/中/后序遍历、层序、最大/最小深度、路径总和、右视图、对称树。本专题聚焦回溯、网格搜索、扩散、拓扑排序、最短路径。
一、代码框架（本专题统一模板）
约定： 所有代码使用统一风格。
- 类型注解完整、变量名统一
- 条件判断用
while (queue.length > 0)- 网格方向数组统一命名为
DIRS- DFS 内部函数统一命名为
dfs- 结果变量统一命名为
result
框架一：DFS 回溯模板（全排列、组合、子集）
const backtrack = (选择列表) => {
const result: 结果类型[] = [];
const path: 元素类型[] = []; // ① 共享路径容器（引用类型）
const dfs = (start: number) => {
if (满足终止条件) {
result.push([...path]); // ② 深拷贝收集结果
return;
}
for (let i = start; i < 选择列表.length; i++) {
path.push(选择列表[i]); // ③ 做选择
dfs(下一个起点); // ④ 递归进入下一层
path.pop(); // ⑤ 撤销选择（回溯）
}
};
dfs(0);
return result;
};💡 回溯三要素： ① 共享
path数组 → ②push选择 → ③ 递归 → ④pop撤销
框架二：网格 DFS/BFS 模板（岛屿、扩散）
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 四方向：下、上、右、左
// DFS 版：原地标记
const dfs = (i: number, j: number) => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== 有效值) return;
grid[i][j] = 已访问值; // 原地标记
for (const [di, dj] of DIRS) {
dfs(i + di, j + dj);
}
};
// BFS 版：队列扩散
const queue: [number, number][] = [[startI, startJ]];
grid[startI][startJ] = 已访问值; // 入队前标记
while (queue.length > 0) {
const [i, j] = queue.shift()!;
for (const [di, dj] of DIRS) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] === 有效值) {
grid[ni][nj] = 已访问值; // 入队前标记
queue.push([ni, nj]);
}
}
}框架三：多源 BFS 扩散模板（腐烂橘子、01矩阵）
const queue: [number, number][] = [];
// ① 收集所有初始源点
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 源值) queue.push([i, j]);
}
}
let steps = 0;
// ② 按层扩散
while (queue.length > 0 && 还有未处理的目标) {
const size = queue.length;
let changed = false; // 本轮是否有变化
for (let k = 0; k < size; k++) {
const [i, j] = queue.shift()!;
for (const [di, dj] of DIRS) {
const ni = i + di, nj = j + dj;
if (有效且是目标值) {
grid[ni][nj] = 源值; // 标记
queue.push([ni, nj]);
changed = true;
}
}
}
if (changed) steps++; // 有变化才计数
}框架四：BFS 拓扑排序模板
// ① 建图 + 统计入度
const graph: number[][] = Array.from({ length: n }, () => []);
const indegree: number[] = new Array(n).fill(0);
for (const [to, from] of edges) {
graph[from].push(to);
indegree[to]++;
}
// ② 入度为 0 的节点入队
const queue: number[] = [];
for (let i = 0; i < n; i++) {
if (indegree[i] === 0) queue.push(i);
}
// ③ BFS 剥离
let count = 0;
while (queue.length > 0) {
const cur = queue.shift()!;
count++;
for (const next of graph[cur]) {
indegree[next]--;
if (indegree[next] === 0) queue.push(next);
}
}
// ④ 判断：count === n → 无环框架五：BFS 最短路径模板（单词接龙、转盘锁）
const bfsShortest = (start: 状态类型, target: 状态类型): number => {
const visited = new Set<状态类型>();
const queue: 状态类型[] = [start];
visited.add(start);
let steps = 0;
while (queue.length > 0) {
const size = queue.length;
for (let k = 0; k < size; k++) {
const cur = queue.shift()!;
if (cur === target) return steps; // 到达目标
// 生成所有合法下一状态
for (const next of 生成下一状态(cur)) {
if (!visited.has(next)) {
visited.add(next); // 入队前标记
queue.push(next);
}
}
}
steps++;
}
return -1; // 无法到达
};二、典型例题
🟢 回溯入门
1. 全排列（LeetCode 46）
问题： 给定不含重复数字的数组
nums，返回所有可能的全排列。
思路： 回溯模板 + used[] 标记已选元素。
const permute = (nums: number[]): number[][] => {
const result: number[][] = [];
const path: number[] = [];
const used: boolean[] = new Array(nums.length).fill(false);
const dfs = () => {
// 终止条件：路径长度 == 数组长度
if (path.length === nums.length) {
result.push([...path]); // 深拷贝
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // 跳过已选的
path.push(nums[i]); // 选择
used[i] = true;
dfs(); // 递归
path.pop(); // 撤销选择（回溯）
used[i] = false;
}
};
dfs();
return result;
};执行过程（nums=[1,2,3]）：
[]
/ | \
1 2 3
/ \ / \ / \
2 3 1 3 1 2
/ \ | | | \
3 2 3 1 2 1
path 变化： [1] → [1,2] → [1,2,3] → 收集 → pop(3) → [1,2] → pop(2) → [1]
→ [1,3] → [1,3,2] → 收集 → ...2. 子集（LeetCode 78）
问题： 给定不含重复元素的数组
nums，返回所有可能的子集（幂集）。
思路： 回溯，用 start 索引控制不重复选。
const subsets = (nums: number[]): number[][] => {
const result: number[][] = [];
const path: number[] = [];
const dfs = (start: number) => {
// 每个节点都是一个有效子集（包括空集）
result.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // 选择
dfs(i + 1); // 从 i+1 开始，保证不重复
path.pop(); // 回溯
}
};
dfs(0);
return result;
};执行过程（nums=[1,2,3]）：
[] ← start=0: 收集 []
/ | \
[1] [2] [3] ← start=1,2,3: 分别收集
/ \ |
[1,2] [1,3] [2,3] ← 继续深入
/
[1,2,3]
result = [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]💡 子集 vs 全排列的区别：子集用
start保证只往后选，全排列用used[]保证不重复选。
3. 组合总和（LeetCode 39）
问题： 给定无重复元素的数组
candidates和目标值target，找出所有和为target的组合。数字可无限次重复选取。
思路： 回溯 + 剪枝。关键：递归时传 i 而非 i+1，允许重复选当前元素。
const combinationSum = (candidates: number[], target: number): number[][] => {
const result: number[][] = [];
const path: number[] = [];
const dfs = (start: number, remaining: number) => {
if (remaining < 0) return; // 剪枝：超过目标
if (remaining === 0) {
result.push([...path]); // 找到一组解
return;
}
for (let i = start; i < candidates.length; i++) {
path.push(candidates[i]); // 选择
dfs(i, remaining - candidates[i]); // ← 传 i，允许重复选自己
path.pop(); // 回溯
}
};
dfs(0, target);
return result;
};执行过程（candidates=[2,3,5], target=8）：
(start=0, remaining=8)
/ | \
选2 选3 选5
(0, 6) (1, 5) (2, 3)
/ | \ / \ ✗ 5>3
2 3 5 3 5
(0,4) (1,3) (2,1) (1,2) (2,0) ← 收集 [3,5]
/ \ ✗ 3>1 ✗ 3>2
2 3
(0,2) (1,-1)✗
|
2
(0,0) ← 收集 [2,2,2,2]
最终：[[2,2,2,2], [2,3,3], [3,5]]🟡 网格搜索
4. 岛屿数量（LeetCode 200）
问题： 给定
'1'（陆地）和'0'（水）的二维网格，计算岛屿数量。岛屿是水平/垂直相邻的陆地组成的连通区域。
思路： 遍历网格，发现陆地就 DFS 淹没整个岛，计数 +1。
const numIslands = (grid: string[][]): number => {
const m = grid.length;
const n = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let count = 0;
const dfs = (i: number, j: number) => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') return;
grid[i][j] = '0'; // 淹没 = 标记已访问
for (const [di, dj] of DIRS) {
dfs(i + di, j + dj);
}
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++; // 发现新岛屿
dfs(i, j); // 淹没整个岛
}
}
}
return count;
};BFS 版（同思路，队列实现）：
const numIslandsBFS = (grid: string[][]): number => {
const m = grid.length, n = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++;
const queue: [number, number][] = [[i, j]];
grid[i][j] = '0'; // 入队前标记
while (queue.length > 0) {
const [r, c] = queue.shift()!;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
grid[nr][nc] = '0'; // 入队前标记
queue.push([nr, nc]);
}
}
}
}
}
}
return count;
};5. 岛屿的最大面积（LeetCode 695）
问题： 给定
0（水）和1（陆地）的二维网格，求最大的岛屿面积（连通陆地数量）。
思路： DFS 递归返回面积：1 + 四方向面积之和。
const maxAreaOfIsland = (grid: number[][]): number => {
const m = grid.length, n = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let maxArea = 0;
const dfs = (i: number, j: number): number => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === 0) return 0;
grid[i][j] = 0; // 标记已访问
// 当前格子 + 四个方向的面积
let area = 1;
for (const [di, dj] of DIRS) {
area += dfs(i + di, j + dj);
}
return area;
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
maxArea = Math.max(maxArea, dfs(i, j));
}
}
}
return maxArea;
};为什么要把四个方向的结果加起来？ DFS 递归返回的是以当前格子为起点向四个方向能连通的所有陆地数量，累加起来就是整个岛的面积。
6. 被围绕的区域（LeetCode 130）
问题： 给定
'X'和'O'的二维矩阵，将所有被'X'包围的'O'翻转为'X'。边界的'O'不被包围（或与边界'O'相连的也不被包围）。
思路： 逆向思维——从边界 'O' 出发 DFS 标记为 '#'，最后遍历：'#' → 'O'，'O' → 'X'。
原始： 边界DFS标记： 最终：
X X X X X X X X X X X X
X O O X → X O O X → X X X X
X X O X X X O X X X X X
X O X X X # X X X O X X
↑边界O标记#const solve = (board: string[][]): void => {
const m = board.length, n = board[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dfs = (i: number, j: number) => {
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== 'O') return;
board[i][j] = '#'; // 标记为"安全的O"
for (const [di, dj] of DIRS) {
dfs(i + di, j + dj);
}
};
// ① 从四边界出发，标记所有不被包围的 'O'
for (let i = 0; i < m; i++) {
if (board[i][0] === 'O') dfs(i, 0);
if (board[i][n - 1] === 'O') dfs(i, n - 1);
}
for (let j = 0; j < n; j++) {
if (board[0][j] === 'O') dfs(0, j);
if (board[m - 1][j] === 'O') dfs(m - 1, j);
}
// ② 最终处理：'#' 恢复为 'O'，'O' 翻转为 'X'
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === '#') board[i][j] = 'O';
else if (board[i][j] === 'O') board[i][j] = 'X';
}
}
};🟠 多源 BFS 扩散
7. 腐烂的橘子（LeetCode 994）
问题： 网格中
0=空、1=新鲜橘子、2=腐烂橘子。每分钟腐烂橘子让四方向相邻新鲜橘子腐烂。求所有橘子腐烂的最少分钟数，不可能则返回-1。
思路： 多源 BFS——所有烂橘子同时入队，按分钟（层）扩散。
const orangesRotting = (grid: number[][]): number => {
const m = grid.length, n = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const queue: [number, number][] = [];
let fresh = 0;
// ① 统计初始状态
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) queue.push([i, j]);
else if (grid[i][j] === 1) fresh++;
}
}
if (fresh === 0) return 0; // 没有新鲜橘子
let minutes = 0;
// ② 多源 BFS
while (queue.length > 0 && fresh > 0) {
const size = queue.length;
let changed = false;
for (let k = 0; k < size; k++) {
const [i, j] = queue.shift()!;
for (const [di, dj] of DIRS) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] === 1) {
grid[ni][nj] = 2; // 腐烂
fresh--;
queue.push([ni, nj]);
changed = true;
}
}
}
if (changed) minutes++; // 只有真的腐烂了新橘子才计数
}
return fresh === 0 ? minutes : -1;
};执行过程：
初始: 第1分钟: 第2分钟:
2 1 1 2 2 1 2 2 2
1 1 0 → 2 1 0 → 2 2 0
0 1 1 0 1 1 0 2 1
fresh=6 fresh=3 fresh=1
第3分钟: 第4分钟:
2 2 2 2 2 2
2 2 0 → 2 2 0
0 2 2 0 2 2
fresh=0 ✅ 答案=4💡
changed的作用：防止空转一轮（当前层没有腐烂任何橘子）也 +1。
🟣 拓扑排序
8. 课程表（LeetCode 207）
问题：
numCourses门课，prerequisites[i] = [a, b]表示先修b才能修a。判断能否修完所有课（即是否有环）。
思路： BFS 拓扑排序三步：建图+统计入度 → 入度0入队 → 逐层剥离。
const canFinish = (numCourses: number, prerequisites: number[][]): boolean => {
// ① 建图 + 统计入度
const graph: number[][] = Array.from({ length: numCourses }, () => []);
const indegree: number[] = new Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
// [1, 0] 表示 0 → 1（学完0才能学1）
graph[prereq].push(course);
indegree[course]++;
}
// ② 入度为 0 的课程入队（没有前置课，可以直接学）
const queue: number[] = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
// ③ BFS 逐层剥离
let count = 0; // 已完成的课程数
while (queue.length > 0) {
const cur = queue.shift()!;
count++;
for (const next of graph[cur]) {
indegree[next]--;
if (indegree[next] === 0) { // 前置课全部学完
queue.push(next);
}
}
}
// ④ 完成的课程数 == 总课程数 → 无环，可以完成
return count === numCourses;
};执行过程（4门课，[[1,0],[2,0],[3,1],[3,2]]）：
建图： 入度：
0 → [1, 2] 课程0: 0 ← 入队
1 → [3] 课程1: 1
2 → [3] 课程2: 1
3 → [] 课程3: 2
BFS:
出队0 → count=1 → 解锁1(入度1→0,入队), 解锁2(入度1→0,入队)
出队1 → count=2 → 解锁3(入度2→1)
出队2 → count=3 → 解锁3(入度1→0,入队)
出队3 → count=4
count=4 == numCourses=4 → true ✅
如果有环 [[0,1],[1,0]]：
入度: 0→1, 1→1 → 没有入度为0的课
队列为空 → count=0 → false ❌9. 课程表 II（LeetCode 210）
问题： 与课程表类似，但需要返回一种可行的上课顺序。
思路： 拓扑排序，出队顺序就是上课顺序。
const findOrder = (numCourses: number, prerequisites: number[][]): number[] => {
// 建图 + 统计入度（与上题完全相同）
const graph: number[][] = Array.from({ length: numCourses }, () => []);
const indegree: number[] = new Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
indegree[course]++;
}
const queue: number[] = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
const order: number[] = []; // ← 记录上课顺序
while (queue.length > 0) {
const cur = queue.shift()!;
order.push(cur); // 出队顺序 = 上课顺序
for (const next of graph[cur]) {
indegree[next]--;
if (indegree[next] === 0) queue.push(next);
}
}
return order.length === numCourses ? order : []; // 有环返回 []
};🟣 最短路径（BFS）
10. 单词接龙（LeetCode 127）
问题： 每次改变一个字母，且改变后的单词必须在词表中。求从
beginWord到endWord的最短转换序列长度。
思路： BFS 最短路径——逐字符变换 26 个字母，首次到达 endWord 即最短。
const ladderLength = (beginWord: string, endWord: string, wordList: string[]): number => {
const wordSet = new Set(wordList);
if (!wordSet.has(endWord)) return 0;
const queue: string[] = [beginWord];
wordSet.delete(beginWord); // 标记已访问
let steps = 1;
while (queue.length > 0) {
const size = queue.length;
for (let k = 0; k < size; k++) {
const word = queue.shift()!;
// 尝试改变每个位置的字母
for (let i = 0; i < word.length; i++) {
for (let c = 97; c <= 122; c++) { // a ~ z
const newChar = String.fromCharCode(c);
if (newChar === word[i]) continue;
const newWord = word.slice(0, i) + newChar + word.slice(i + 1);
if (newWord === endWord) return steps + 1; // 到达终点
if (wordSet.has(newWord)) {
queue.push(newWord);
wordSet.delete(newWord); // BFS首次到达即最短，无需再访问
}
}
}
}
steps++;
}
return 0;
};执行过程：
beginWord="hit", endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]
hit (steps=1)
→ hot 入队（删hot）
hot (steps=2)
→ dot 入队, lot 入队（删dot, lot）
dot (steps=3)
→ dog 入队（删dog）
lot (steps=3)
→ log 入队（删log）
dog (steps=4)
→ cog = endWord → return 5 ✅
序列：hit → hot → dot → dog → cog (5步)11. 打开转盘锁（LeetCode 752）
问题： 4 位圆形密码锁，初始
"0000"，每次可拨动一位数字（+1 或 -1，0→9 或 9→0）。给定死锁列表deadends和目标target，求最少拨动次数。
思路： BFS 最短路径——每次 8 种拨动（4位×2方向），用 Set 记录 visited。
const openLock = (deadends: string[], target: string): number => {
const dead = new Set(deadends);
const visited = new Set<string>();
const start = '0000';
if (dead.has(start)) return -1;
if (start === target) return 0;
const queue: string[] = [start];
visited.add(start);
let steps = 0;
while (queue.length > 0) {
const size = queue.length;
for (let k = 0; k < size; k++) {
const cur = queue.shift()!;
// 8 种拨动：4 位 × 2 方向
for (let i = 0; i < 4; i++) {
for (const delta of [1, -1]) {
const digit = (Number(cur[i]) + delta + 10) % 10; // 处理 0→9 和 9→0
const next = cur.slice(0, i) + digit + cur.slice(i + 1);
if (next === target) return steps + 1;
if (!dead.has(next) && !visited.has(next)) {
visited.add(next);
queue.push(next);
}
}
}
}
steps++;
}
return -1;
};🔴 克隆图
12. 克隆图（LeetCode 133）
问题： 给定无向连通图中的一个节点，深拷贝整个图。
思路： DFS/BFS + Map 映射（原节点 → 克隆节点）。
class GraphNode {
val: number;
neighbors: GraphNode[];
constructor(val?: number, neighbors?: GraphNode[]) {
this.val = val ?? 0;
this.neighbors = neighbors ?? [];
}
}
// ====== DFS 版 ======
const cloneGraphDFS = (node: GraphNode | null): GraphNode | null => {
if (!node) return null;
const map = new Map<GraphNode, GraphNode>(); // 原节点 → 克隆节点
const dfs = (n: GraphNode): GraphNode => {
if (map.has(n)) return map.get(n)!; // 已克隆，直接返回
const clone = new GraphNode(n.val);
map.set(n, clone); // 先存入 map，防止死循环
for (const neighbor of n.neighbors) {
clone.neighbors.push(dfs(neighbor));
}
return clone;
};
return dfs(node);
};
// ====== BFS 版 ======
const cloneGraphBFS = (node: GraphNode | null): GraphNode | null => {
if (!node) return null;
const map = new Map<GraphNode, GraphNode>();
const queue: GraphNode[] = [node];
// 先克隆第一个节点
map.set(node, new GraphNode(node.val));
while (queue.length > 0) {
const cur = queue.shift()!;
const clone = map.get(cur)!;
for (const neighbor of cur.neighbors) {
if (!map.has(neighbor)) {
map.set(neighbor, new GraphNode(neighbor.val));
queue.push(neighbor);
}
clone.neighbors.push(map.get(neighbor)!);
}
}
return map.get(node)!;
};三、本专题总结
题目速查表
| # | 题目 | 方法 | 关键技巧 |
|---|---|---|---|
| 1 | 全排列 | DFS回溯 | used[] + push/pop |
| 2 | 子集 | DFS回溯 | start 索引去重 |
| 3 | 组合总和 | DFS回溯 | 传 i 允许重复选 |
| 4 | 岛屿数量 | 网格DFS/BFS | 淹没标记 |
| 5 | 岛屿最大面积 | 网格DFS | 递归返回面积累加 |
| 6 | 被围绕的区域 | 边界DFS | 逆向标记 '#' |
| 7 | 腐烂的橘子 | 多源BFS | 所有源同时入队，按层扩散 |
| 8 | 课程表 | BFS拓扑排序 | 入度表 + 逐层剥离 |
| 9 | 课程表II | BFS拓扑排序 | 出队顺序即结果 |
| 10 | 单词接龙 | BFS最短路径 | 逐字符变换，Set删除标记 |
| 11 | 打开转盘锁 | BFS最短路径 | 8种拨动，visited Set |
| 12 | 克隆图 | DFS/BFS | Map 映射原节点→克隆节点 |
统一模板回顾
| 场景 | 模板 | 核心要素 |
|---|---|---|
| 全排列/子集/组合 | 回溯 DFS | push → 递归 → pop |
| 网格连通 | 网格 DFS/BFS | 四方向 + 原地标记 |
| 多源扩散 | 多源 BFS | 所有源入队 + 按层扩散 |
| 拓扑排序 | BFS + 入度表 | 建图 → 入度0入队 → 剥离 |
| 最短路径 | BFS + visited | 入队前标记 + 首次到达即返回 |
记忆口诀
- 回溯三步走：push → 递归 → pop
- 岛屿淹没法：遇1就计数，dfs全变0
- 橘子多源BFS：烂的先入队，按分钟扩散
- 拓扑看入度：入零就入队，出队数节点
- 最短路径BFS：入队前标记，首次到达就返回
关联题库
以下题目与本文知识点相关，可以跳转到题库练习：