一、深度搜索dfs和广度搜索bfs
- dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
- bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
问“最短” → BFS
问“有没有环” → DFS
问“连通区域” → DFS
问“是否能到达” → BFS/DFS 都行
多源同时扩散 → 多源 BFS
要找所有路径/组合 → DFS
1.BFS模板
q.add(start)
while(q非空):
遍历当前层
扩散到下一层
以腐烂的橘子为例（多源）
// 固定：方向数组（如果是网格 BFS） int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; // 固定：队列结构 Queue<int[]> q = new LinkedList<>(); // 可变：根据题意加入起点（单源 BFS 只有一个） q.offer(new int[]{startX, startY}); // 固定：标记 visited，防止重复访问 boolean[][] vis = new boolean[m][n]; vis[startX][startY] = true; // 固定：开始 BFS 四层模板 int steps = 0; while (!q.isEmpty()) { // 固定：按层遍历（求最短步数必需） int size = q.size(); while (size-- > 0) { // 固定：取出队头 int[] cur = q.poll(); int x = cur[0], y = cur[1]; // 可变：题意相关逻辑（例如判断是否到达目标） // if (grid[x][y] == TARGET) return steps; // 固定：扩散到四个方向 for (int[] d : dirs) { int nx = x + d[0]; int ny = y + d[1]; // 可变：边界条件、障碍条件、题目特判 if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (vis[nx][ny]) continue; // if (grid[nx][ny] == '#') continue; // 按题意定义障碍 // 固定：入队 + 标记访问 vis[nx][ny] = true; q.offer(new int[]{nx, ny}); } } // 固定：每扩散一层， steps++ steps++; }固定步骤：
1.新建队列
2.visit数组防重复访问
3.层序遍历框架
int size = q.size(); while (size-- > 0) { ... } steps++;4.四个方向扩散
需要根据题目改变的地方：
1. 初始入队的点（单源 / 多源）
2. 访问条件，比如：边界，grid[x][y] == 0/1/2，不能访问障碍，可以访问某个点
3. 到达目标时的处理
4. 返回值含义（最短步数 or 是否可达 or 最大层数）
如果是单源，那么就直接把这个点入队就行
q.offer(new int[]{startX, startY}); vis[startX][startY] = true;如果是多源，那么就要for循环遍历所有的点
for (int[] src : sources) { q.offer(src); vis[src[0]][src[1]] = true; }2.DFS模板
岛屿数量
dfs(x):
if(不能继续) return
标记访问
dfs(邻居)
void dfs(int x, int y) { // 可变：越界判断 / 终止条件 if (x < 0 || x >= m || y < 0 || y >= n) return; if (grid[x][y] != '1') return; // 固定：标记为已访问 grid[x][y] = '2'; // 或 vis[x][y] = true // 固定：四方向递归 DFS dfs(x + 1, y); dfs(x - 1, y); dfs(x, y + 1); dfs(x, y - 1); }固定步骤：
1. 函数结构（传坐标/节点）
2. 递归调用自身
3. 标记访问
需要根据题目改变的地方：
1. 终止条件根据题目不同：越界，遇到障碍，遇到已访问过的点，符合某个条件停止
2. 标记方式
3. 图的结构 网格（四方向），树，图（邻接表）
4. 返回值
图的结构
树
void dfs(TreeNode root) { if (root == null) return; dfs(root.left); dfs(root.right); }图（检测环）
boolean dfs(int x) { if (color[x] == 1) return true; // 找到环 if (color[x] == 2) return false; color[x] = 1; for (int y : g[x]) { if (dfs(y)) return true; } color[x] = 2; return false; }二、拓扑排序
课程表
public int[] topoSort(int numCourses, int[][] prerequisites) { // 固定：构造图的邻接表 List<Integer>[] g = new ArrayList[numCourses]; Arrays.setAll(g, i -> new ArrayList<>()); // 固定：统计所有节点的入度 indegree[] int[] indegree = new int[numCourses]; // 可变：根据题目加入边信息 // prerequisites[i] = {a, b} 意味 b -> a for (int[] p : prerequisites) { int a = p[0], b = p[1]; g[b].add(a); indegree[a]++; } // 固定：队列存储所有入度为 0 的节点 Queue<Integer> q = new LinkedList<>(); for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) q.offer(i); } // 固定：拓扑序存放结果 int[] order = new int[numCourses]; int idx = 0; // 固定：BFS 弹出入度为 0 的点，并降低邻接点入度 while (!q.isEmpty()) { int x = q.poll(); order[idx++] = x; for (int y : g[x]) { indegree[y]--; if (indegree[y] == 0) q.offer(y); } } // 可变：根据题意返回不同的内容 // 这里如果 idx < numCourses 说明有环，无法完成 if (idx < numCourses) return new int[0]; // 有环 return order; }固定步骤：
1.构造邻接表
2. indegree 数组
3.入度为 0 进队列
4.队列 BFS
5.拉出节点 → 降低其邻接节点的入度
6.入度减到 0 再进队列
需要根据题目改变的地方：
1.边方向，先干嘛后干嘛
2.返回内容
三、前缀树
从二叉树到多叉树
以实现Trie前缀树为例
class Trie { private static class Node { Node[] son = new Node[26]; // 固定：表示 26 个字母 boolean end; // 固定：这个节点是否是某个单词的结尾 } private final Node root = new Node(); // 固定：根节点 // 插入单词（固定模板） public void insert(String word) { Node cur = root; for (char c : word.toCharArray()) { c -= 'a'; if (cur.son[c] == null) { cur.son[c] = new Node(); } cur = cur.son[c]; } cur.end = true; } // 查找完整单词（固定模板） public boolean search(String word) { Node t = find(word); return t != null && t.end; } // 查找前缀（固定模板） public boolean startsWith(String prefix) { return find(prefix) != null; } // 根据字符串找到最后一个节点（核心固定） private Node find(String word) { Node cur = root; for (char c : word.toCharArray()) { c -= 'a'; if (cur.son[c] == null) return null; cur = cur.son[c]; } return cur; } }
