登录以参加训练计划

“搜索、树与图论” 是算法竞赛中分水岭级别的模块。

为什么这么说？

1. 搜索 (DFS/BFS) 是“万能算法”，遇到不会做的题，暴力搜索通常能拿 30%~50% 的分，甚至通过剪枝能拿到 100% 的分。
2. 树与图 是提高组（CSP-S/NOIP）的核心领域，普及组（CSP-J）压轴题也经常涉及图的遍历。

下面我为你深度总结这一模块的核心知识点。

---

一、 图的存储 (Graph Storage)

在遍历图之前，首先要把图存进计算机里。主要有三种方式：

存储方式	代码结构	优点	缺点	适用场景
邻接矩阵	int g[N][N];	$O(1)$ 查询两点是否有边	极其浪费空间 $O(N^2)$	节点数 $N \le 1000$ 的稠密图，或 Floyd 算法
邻接表 (Vector)	vector<int> g[N];	最推荐。节省空间，只存存在的边	稍慢一点点，但忽略不计	绝大多数题目 ($N \le 10^5$)
链式前向星	head[], nxt[], to[]	空间极小，速度最快	代码难写，容易写错	卡空间/卡时间的极端情况 (SPFA/网络流)

教练建议： CSP-J/S 阶段，无脑选 vector 邻接表。写法简单，不易出错。

// 存图：u 指向 v
g[u].push_back(v); 
// 如果是无向图，还要反向存一次
g[v].push_back(u);

---

二、 深度优先搜索 (DFS)

1. 核心逻辑 “不撞南墙不回头”。一条路走到黑，没路了再退回来（回溯）。

• 实现方式：递归（系统栈）或手写栈。

2. 必考应用

• 连通性判断：迷宫能不能走通？
• 求全排列/组合：$N$ 个数选 $K$ 个的所有方案。
• 回溯法 (Backtracking)：
  • 八皇后问题、数独问题。
  • 核心在于**“恢复现场”**：递归进去时标记占领，递归出来时取消标记。
• 树的遍历：先序、中序、后序遍历。

3. 优化技巧 (剪枝)

• 可行性剪枝：发现当前路不通，提前 return。
• 最优性剪枝：发现当前花费已经超过了之前找到的最优解，提前 return。

---

三、 广度优先搜索 (BFS)

1. 核心逻辑 “水波纹扩散”。一层一层往外扩，先访问离起点近的，再访问远的。

• 实现方式：队列 (std::queue)。

2. 必考应用

• 无权图的最短路径：这是 BFS 最王牌的用法！走迷宫最少几步？象棋马跳到终点最少几步？
• 层序遍历：按树的层级输出节点。
• Flood Fill (洪水填充)：统计地图上有几个连通块（比如统计水坑数量）。

3. BFS 模板三部曲

1. 入队：起点入队，标记 vis。
2. 循环：while(!q.empty()) 取队首，弹出。
3. 扩散：遍历队首的所有邻居，如果没访问过，就入队、标记、更新距离。

---

四、 记忆化搜索 (Memoization)

1. 核心概念 DFS + 备忘录。 普通的 DFS 会重复计算很多相同的状态，导致超时。记忆化搜索就是：算过一次的结果，存进数组 memo[] 里，下次遇到直接查，不算了。

2. 它是谁？ 它其实就是 动态规划 (DP) 的递归写法（自顶向下）。

3. 经典例题

• 斐波那契数列：f(n) = f(n-1) + f(n-2)。不加记忆化是 $O(2^n)$，加了是 $O(n)$。
• 滑雪问题 / 数字三角形：在一个矩阵里找最长路径。

---

五、 树与图的遍历 (Traversal)

1. 树 (Tree)

• 特性：$N$ 个点，$N-1$ 条边，连通且无环。
• 遍历：由于树没有环，DFS 遍历时通常不需要 vis 数组，只需要记录 father（父节点）防止倒流即可。

  void dfs(int u, int father) {
      for(int v : g[u]) {
          if(v == father) continue; // 别走回头路
          dfs(v, u);
      }
  }
  

2. 图 (Graph)

• 特性：可能有环，可能不连通。
• 遍历：必须使用 bool vis[N] 数组记录访问过的点，否则会在环里死循环。

---

🏆 教练的总结速查表

场景	推荐算法	复杂度
找最短路 (边权均为1)	BFS	$O(N+M)$
找所有方案 / 排列组合	DFS	指数级
走迷宫 / 连通块统计	BFS / DFS 均可	$O(N \times M)$
树的深度 / 子树大小	DFS	$O(N)$
状态有重叠的递归	记忆化搜索	等同于 DP
图的存储	Vector 邻接表	空间最优

学习建议： 先彻底搞懂 BFS 走迷宫 和 DFS 排列数字 这两个模板题，它们是这整个模块的基石。加油！

---

你抓住了问题的关键！DFS（全排列/回溯） 和 BFS（走迷宫/最短路） 是搜索算法的“任督二脉”。打通了这两个，后续的树形 DP、图论最短路、网络流等高级算法才能学得动。

我为你精心设计了一份循序渐进、从板子到实战的洛谷刷题单。请务必按照顺序刷，不要跳关。

---

第一阶段：DFS 排列组合与回溯 (深度优先)

核心心法：不撞南墙不回头。 代码结构：void dfs(step) { 边界判断; 枚举所有可能; 标记; 下一层递归; 回溯(取消标记); }

顺序	题号	题目名称	难度	训练重点（教练点评）
1	P1706	全排列问题	🟠 普及-	【绝对的板子】 DFS 的Hello World。必须能够默写出来。理解 vis 数组标记和回溯的作用。
2	P1157	组合的输出		【进阶板子】 从排列变成组合（不考虑顺序）。需要在 DFS 中增加一个参数 start_index，保证生成的数是递增的，从而去重。
3	P1605	迷宫		【易混淆】 注意！这题问的是有多少种方案，而不是最短路径。凡是问“方案数”或者“能不能到达”，首选 DFS。
4	P2089	烤鸡		枚举应用。实际上是“数字拆分”问题，把 $N$ 拆成 10 个数之和。考察 DFS 枚举每一种调料放多少克。
5	P2392	kkksc03考前临时抱佛脚		0/1 背包型 DFS。每个题目只有“做”或“不做”两种选择，枚举所有情况找最优。
6	P1219	[USACO1.5] 八皇后	🟡 普及/提高-	【DFS 毕业考】 经典中的经典。难点在于如何用数组快速判断“对角线”是否冲突（i+j 和 i-j 的技巧）。

---

第二阶段：BFS 走迷宫与扩散 (广度优先)

核心心法：层层推进，水波纹扩散。 代码结构：queue 入队 -> while 循环 -> 取队首 -> 遍历方向 -> 合法且未访问则入队+更新步数。

顺序	题号	题目名称	难度	训练重点（教练点评）
1	P1443	马的遍历	🟠 普及-	【绝对的板子】 象棋马跳到棋盘各点最少几步？这就是标准的 BFS 最短路。注意马有 8 个方向。
2	P1746	离开中山路		标准迷宫。从 $(x1, y1)$ 到 $(x2, y2)$ 最少几步？上下左右 4 个方向。练习 struct {x, y, step} 结构体入队。
3	P1135	奇怪的电梯	🟡 普及/提高-	一维 BFS。不要以为 BFS 只能走格子！这题是在楼层之间跳跃，把楼层看作点，按钮看作边，求最少按几次。
4	P1162	填涂颜色	🟠 普及-	Flood Fill (种子填充)。找被围起来的 0。建议从边界外的 0 开始跑 BFS，把外围染成一种颜色，剩下的就是里面的。
5	P1683	入门		连通块计数。问你能到达多少个格子？BFS 只要入队一次，计数器就+1。

---

第三阶段：搜索综合与剪枝 (提高组预备)

目标：区分何时用 DFS，何时用 BFS，以及如何优化 DFS。

顺序	题号	题目名称	难度	训练重点（教练点评）
1	P1433	吃奶酪	🔵 提高+/省选-	状压 DFS / 搜索。它是推销员问题 (TSP)。需要记录“已经吃过的奶酪集合”，涉及到简单的剪枝。
2	P3958	[NOIP2017 提高] 奶酪	🟡 普及/提高-	连通性判断。虽然是三维坐标，但本质是判断球与球是否相连。可以用 BFS 也可以用并查集。
3	P1379	八数码难题	🔵 提高+/省选-	状态压缩 BFS。地图本身是一个状态，需要用 map<string, int> 来判重。经典的 BFS 求最小移动步数。

---

📝 教练的避坑指南 (黄金法则)

在做这些题的时候，初学者最容易晕的是 “这题到底该用 DFS 还是 BFS？”

请背诵以下黄金判断法则：

1. 问“最少步数”、“最短距离”、“最少操作次数”：

   • 👉 99% 是 BFS。（因为 BFS 第一次搜到终点时，一定是层数最少的）
   • 例题：马的遍历、奇怪的电梯。

2. 问“有多少种方案”、“打印所有路径”、“是否存在某种解”：

   • 👉 99% 是 DFS。（因为 DFS 方便回溯，能遍历完所有可能）
   • 例题：全排列、迷宫(P1605)、八皇后。

3. 连通块问题（染色、填色）：

   • 👉 BFS 和 DFS 都可以。
   • 但是建议用 BFS，因为递归太深容易爆栈（Stack Overflow），而队列在堆内存里，容量大。

先去把 P1706（全排列） 和 P1443（马的遍历） 做通，这两题过了，你的搜索大门就打开了！加油！