搜索与图论全解析：从状态建模到BFS/DFS与最短路径

如果你写过一阵子算法题，会发现大量题目绕不开“搜索与图论”这四个字。搜索不是单纯地跑循环，图论也不是拿来背概念；这两者放在一起，其实是在回答同一件事：如何把问题变成一张图，再沿着边找到你要的答案。这篇内容来自我近期自己做的一个算法整理项目——把搜索与图论的核心模型、存储方式、经典算法和常见踩坑重新过了一遍。适合刚接触图论、准备面试和打比赛的人对照着看。

1. 搜索与图论的本质关系：状态就是节点，转移就是边

1.1 图论不是在教你画图，而是在教你描述关系

图论里的图，抽象成一组点和一组边。点可以是地图上的路口，可以是社交网络里的人，也可以是一个算法的某种“局面”。边则表示它们之间能不能一步到达。

做搜索题时最关键的转换，就是把题目里那些约束变成点与边：八个棋子的一种摆放是一个点，一次移动改变摆放，得到另一张图，这就是一条边。搜索算法的工作，就是从起点出发，沿着这些边找到终点。理解这一点后，“搜索与图论”就不是两个知识点，而是一套组合拳。

我在实际整理项目时，先画了一张关系图：结点是所有可能的“状态”，边是所有可能的一次“操作”，最终答案往往就是一条路径。这么一想，很多题目的套路立刻统一了。

1.2 搜索算法的本质是遍历，不是碰运气

很多人以为搜索是“一个个试”，其实它是对状态空间进行系统遍历。BFS、DFS 的差别只在于遍历顺序有差别。BFS 像排队叫号，一层层检查；DFS 像一条路走到黑，不行再回头。但无论哪种，都需要保证每个节点尽量只访问一次。

这种“状态到边再到目的地”的抽象，适用于迷宫、棋盘、拼图、地图导航、网络爬虫、编译器依赖解析，几乎所有带“路径”含义的问题都能套进去。做题时先把状态定义清楚，搜索只是执行者。我强烈建议用一个统一模板去套，而不是每次临场发挥。

2. 图的存储方式：搜索之前先解决“怎么记录地图”

2.1 邻接矩阵：直观，但代价高

邻接矩阵用二维数组 g[u][v] 表示 u 到 v 是否有边或权值。写起来简单，判断两个点是否相邻是 O(1)。但代价非常明显：空间是 O(V²)。V 到 10⁴ 时就是 10⁸ 个数，内存爆炸。所以它适合点数少、边数接近满图的稠密图，例如 Floyd 算法。

我实际项目里的经验是：点数超过 5000 就要犹豫，超过 2 万基本不要用。使用邻接矩阵还有个隐藏问题：遍历某一个点的所有邻居时，必须扫描整行的 n 个位置，如果是稀疏图，大量时间浪费在判断“这条边根本不存在”上。

2.2 邻接表：竞赛和工程里的主流

邻接表只存实际存在的边。实现方式可以用 vector 嵌套，也可以用结构体数组。以 C++ 为例：

vector<pair<int, int>> g[MAXN]; g[u].push_back({v, w});

遍历 u 的邻居时直接遍历 g[u]，复杂度是 O(V+E)，空间也是 O(V+E)。对稀疏图非常友好。多数题目给的图都是稀疏图，边数远小于 V²，所以邻接表最常用。

Python 里我习惯用二维列表，或者用 dict 的 setdefault 来做带权邻接表。做题目时，邻接表几乎可以覆盖 90% 的场景，掌握它是性价比最高的选择。

2.3 链式前向星：比赛党喜欢的省内存写法

链式前向星用几个数组模拟链式结构：head、to、next。要加边时，新边指向当前链表头，再把头更新为新边：

void addEdge(int u, int v, int w) { to[++tot] = v; weight[tot] = w; nextEdge[tot] = head[u]; head[u] = tot; }

遍历时从 head[u] 往下顺着 next 走。初学者可能觉得别扭，但它省去 vector 的动态扩容，访问连续内存，数据量大时性能更稳定。如果只是做题，邻接表完全够用；如果是打竞赛并且追求极致，建议掌握链式前向星。我第一次完全理解它时花了小半天，之后写多源最短路确实爽很多。

2.4 如何选择：一张表说清楚

选择逻辑其实很简单：除 Floyd 等少数算法外，优先邻接表。E 接近 V² 时再考虑矩阵。这个决策不需要纠结，看题目数据范围即可。

3. 深度优先搜索：递归、回溯和剪枝

3.1 DFS 的基础模板

DFS 是图论最基础的搜索方式。从某个点出发，标记为已访问，再递归访问所有未访问的邻居。

void dfs(int u) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) dfs(v); } }

代码看起来简单，但应用时有两个容易出错的地方：一是递归出口，二是回溯状态。如果是用来找路径，visited 只在当前路径上标记，递归返回后要恢复；如果只做连通性检验，就全局标记不恢复。两种场景必须分清楚。

我在整理项目时把 DFS 分成两类：一类是“遍历型”，做完后整张图的状态都在；另一类是“搜索型”，需要在多条路径中找目标。这两类的代码看起来很像，但标记和撤销逻辑完全不同。

3.2 回溯算法，其实是 DFS 加状态复原

以 N 皇后为例，每一行放一个棋子，用 col 数组记录已经占用的列和对角线。尝试放一个位置后递归下一行，回来再撤销。伪代码如下：

void dfs(int row) { if (row == n) { count++; return; } for (int col = 0; col < n; col++) { if (check(row, col)) { mark(row, col); dfs(row + 1); unmark(row, col); } } }

核心就是“尝试、递归、撤销”。撤销很有必要，否则后面的分支会读到脏状态。我见过很多人写回溯时忘记恢复，导致答案数量翻倍；调试时很难发现，因为遍历顺序已经错了。实际写 N 皇后时，判断对角线可以用 row+col 和 row-col 两个值，不需要开二维数组模拟整个棋盘，这样内存和时间都更好。

3.3 剪枝：DFS 的加速器

剪枝不是复杂魔法，就是在递归前判断“这条路还有没有意义”。常见的有两类：可行性剪枝，当前状态已经违反约束，直接返回；最优性剪枝，当前花费已经超过已知最优解，直接返回。

比如走迷宫时，如果当前位置到终点的曼哈顿距离已经大于剩余步数，就可以停止。剪枝能极大减少分支数，但要注意维护合适的全局变量，别为了省时间牺牲正确性。我调试剪枝题时，习惯在递归入口打印“当前深度、当前消耗、当前最优”，这样能快速看出是不是剪掉了本不该剪的路径。

4. 广度优先搜索：无权图最短路径的默认选择

4.1 BFS 的队列机制

BFS 用队列保存待扩展的节点，逐层向外扩展。因为每一层离起点的距离相同，所以第一次访问某个节点时的层数就是最短距离。

queue<int> q; q.push(start); dist[start] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } }

这里有一个关键细节：在入队时更新 dist，而不是出队时更新。为什么？入队时更新可以防止同一节点被重复进队；出队时更新会让很多节点进入队列两次以上，最坏情况队列爆炸。这个细节是很多新手的盲区，也是线上超时的常见原因。

4.2 双向 BFS：把两棵大树从中间接上

单向 BFS 的扩展量随层数指数增长。双向 BFS 同时从起点和终点向外扩展，每次扩展节点数少的一层，直到两边相遇。假设每层平均分支数为 b，单向搜索 d 层大概要处理 b^d，双向只需要两个 b^(d/2)，提升非常可观。

实现时我用两个队列、两个 dist 数组，或者用 unordered_map 记录状态。每次扩展一层，不要一边多扩展几步另一边少扩展。按层交替扩展，才能保证第一次相遇时路径最短。

我做过一个典型例子：单词接龙，从一个单词变到另一个单词，字典里有几千个词。单向 BFS 经常要遍历好几层，双向 BFS 能在几毫秒内结束。工程里如果搜索空间很大，这个优化很值得先写进去。

4.3 状态搜索：八数码与单词接龙

搜索不只在图上，也可以在一个“状态集合”上。把每个合法状态当节点，一次操作当边。八数码有大概 9!/2 个状态，用 BFS 可以求最少步数。单词接龙每个词是一个点，能互相转换的加边，BFS 找最短变换路径。

这类问题难点不是搜索，而是如何设计状态的压缩编码和展开邻接状态。我见过很多把状态定义成多维数组的写法，能跑但极慢；用字符串编码或整数编码，内存和时间都会好很多。八数码常用康托展开或字符串加 map 做去重，核心思路是让每个状态有唯一、轻量的表示方式。

5. 进阶：迭代加深、A* 与记忆化搜索

5.1 迭代加深搜索：DFS 的空间，BFS 的耐心

如果题目要求最短步数，但状态空间非常深，BFS 会占用大量内存。迭代加深 IDDFS 是不断限制 DFS 深度：先从深度 1 开始，不行就限制 2，依次递增。因为 DFS 只记录当前路径，空间很小；随着深度逐步增加，第一次找到解时就是最短解。代价是重复搜索前面的层，但每层扩展是指数的，重复的代价通常可以接受。

这个算法适合那些“答案深度未知、但状态分叉多”的场景，例如一些棋盘游戏。实际写的时候要小心深度限制的退出条件：如果一层内没有新的可扩展节点，说明已经遍历完状态空间，应该停止，否则会无限加深。

5.2 A*：把 BFS 变成有方向的搜索

A* 的核心是估价函数 f(n)=g(n)+h(n)。g 是起点到当前点实际代价，h 是当前点到目标的估计代价。当 h 小于等于真实代价时，A* 保证找到最优路径，这叫做可采纳性。

在地图寻路里，常见 h 用欧几里得距离或曼哈顿距离。实现时维护一个优先队列，每次弹出 f 最小的节点。可以说 BFS 是 h=0 的特例，Dijkstra 也类似，只是把 g 当作优先级。A* 的调参经验：h 设计得过松，搜索几乎退化成 Dijkstra；h 设计得过紧、高估，速度更快但可能得不到最优解。

我做一个网格寻路 Demo 时，用曼哈顿距离做 h，比普通 BFS 快了一个数量级。不过 A* 在 OpenList 里重复插入节点时要小心，更新 dist 后旧记录会留在堆里，弹出时一定要判断当前记录是否过期。

5.3 记忆化搜索：搜索和动态规划之间的桥

如果搜索过程中同一个状态会被多次重复计算，可以在第一次计算后把结果存下来，这就是记忆化搜索。它在 DAG 路径计数、博弈问题里特别实用。

int dfs(int u) { if (dp[u] != -1) return dp[u]; int res = 0; for (int v : adj[u]) res += dfs(v); return dp[u] = res; }

注意记忆化只能用于无环状态转移；有环时依赖关系互相交织，直接记忆化会死循环。遇到带环图想求最长路，得先判环或缩点，这是另一套知识。我自己的判断方式很简单：如果状态转移是单向推进的，比如 i 到 j，且 j 一定在 i 之后，就可以记忆化；如果可能出现循环，就不能用。

6. 实操：从零写一个迷宫最短路径工具

6.1 建模：迷宫地图就是一张四邻接图

迷宫用二维数组保存，0 表示空地，1 表示墙，起点在左上角，终点在右下角。上下左右四个方向移动。每个坐标是一个节点，能走的相邻坐标之间就是边。因为是四方向且步长相同，所以用 BFS 可以求最短步数。

这个建模过程是搜索与图论知识落地的最好练习：不需要显式建图，只要在 BFS 中用方向数组动态生成邻居即可。方向数组的顺序会影响 DFS 的遍历路径，但对 BFS 最短步数没有影响。

6.2 Python 实现

from collections import deque def bfs_maze(maze): rows, cols = len(maze), len(maze[0]) dist = [[-1] * cols for _ in range(rows)] pre = [[None] * cols for _ in range(rows)] dist[0][0] = 0 q = deque([(0, 0)]) dirs = [(1,0), (-1,0), (0,1), (0,-1)] while q: x, y = q.popleft() if (x, y) == (rows - 1, cols - 1): break for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and dist[nx][ny] == -1: dist[nx][ny] = dist[x][y] + 1 pre[nx][ny] = (x, y) q.append((nx, ny)) return dist, pre

dist 矩阵记录最短步数，pre 记录每个格子是从哪里来的。返回后从终点沿着 pre 倒推，就能恢复整条路径。

def reconstruct(pre, end): path = [] cur = end while cur is not None: path.append(cur) cur = pre[cur[0]][cur[1]] path.reverse() return path

注意起点 pre 要保留为 None，否则会回溯到起点之外。恢复时如果终点 dist 是 -1，说明不可达，直接返回空路径。

6.3 调试建议

跑输出前，先打印 dist 矩阵。如果某个可达格仍是 -1，说明 BFS 访问顺序写错了，或者墙判断反了。再用小迷宫，比如 3x3，手动模拟队列，看扩展顺序是否一致。重要的是先保证小规模正确，再上大数据。

我自己踩过一次坑：方向数组里用了 (0, 1) 和 (0, -1) 但坐标判断写成行大于列，导致越界数组访问在本地不报错，输出却明显错误。现在我会把边界判断单独抽成函数，并对随机生成的多个迷宫做回归测试。

7. 常见问题与排查技巧实录

7.1 重复访问导致的死循环

最常见的错误是没有标记 visited 或标记时机不对。在 DFS 里，应该在进入递归前标记；在 BFS 里，应该在入队时标记。如果只标记而不撤销，可能漏掉其他路径；如果该撤销的不撤销，可能无限递归。区分“全局访问”和“当前路径访问”很关键。

排查时可以打印每个节点的第一次访问时间，或者打印递归深度，超过一定值立刻终止。遇到环图时尤其要小心：没有 visited 的 DFS 在有向有环图里会无限绕圈，这是很多数据弱时能过、强时超时的隐藏原因。

7.2 递归栈溢出

深度达到 10⁵ 时，递归 DFS 很容易爆栈。系统栈不是无限大的。解决方式是改迭代式 DFS：

stack<int> st; st.push(start); while (!st.empty()) { int u = st.top(); st.pop(); if (visited[u]) continue; visited[u] = true; for (int v : adj[u]) { if (!visited[v]) st.push(v); } }

迭代式没有路径深度的递归栈问题。但要注意入栈的顺序和递归可能有差异，必要时反向遍历邻居。我在做超大树形图时，一般直接用这种写法，省得还要调整系统栈大小。

7.3 路径还原被覆盖

BFS 用 pre 数组记录前驱时，如果目标节点有多条边能到达，后到达的可能覆盖先到达的位置。但实际不会，因为 BFS 第一次访问时更新 pre，后续不再更新；所以 pre 是稳定的。真正容易错的是初始化 pre 为 None，终点没有 pre 时说明不可达，别直接回溯。

如果你写的是“出队时才记录前驱”，那么同一层或更早层的节点可能被后弹出的路径覆盖，导致路径混乱。所以记录前驱也要在入队时做，和 dist 更新保持同步。

7.4 内存爆炸

邻接矩阵存 20000 个顶点，需要 4 亿个 int；BFS 队列里塞满所有节点也可能内存很大。遇到这种题先看数据范围，超过内存限制就换邻接表，或者用 A* 减少扩展节点数。不要盲目堆数据结构。

补充一点：Python 里二维 list 存大图会额外消耗很多对象头，如果是超大图，用数组模块或一维索引压缩。工程里我也见过用数据库加缓存做图遍历的，但算法题里不需要这么复杂，控制好数据规模就行。

8. 最后的一点经验

我不是第一天就把这些全弄明白的。做搜索与图论这个整理项目时，最难的不是算法本身，而是“把题面翻译成图”的这一步。我给自己定的练习方式是：每道题至少画出状态怎么定义、节点怎么转移、是否无环、是求路径还是计数，然后再动手写代码。这个方法对新手特别有效。

另外分享一个调试技巧：把搜索过程可视化。不管是在控制台打印队列，还是用简单脚本输出每一步的 visited 状态，调试效率都比死盯代码高很多。搜索与图论的坑大多不在语法，而在状态管理。状态一旦理清，代码往往一个多小时就能稳定下来。