企业官网建设流程全解析

搜索和图论这块，是很多学算法的人又爱又怕的部分。爱的是它跟现实结合得特别紧，迷宫寻路、导航规划、网络布线都能用上；怕的是概念又多又绕，DFS、BFS、最短路、最小生成树听起来像四门课，实际上放一起学反而更容易搭出体系感。这篇就按我自己的理解，把这几个算法从原理到模板再到避坑，完整过一遍，希望能给准备面试或者刚入门数据结构的同学一些参考。

先交代一下背景：我一般会把这讲放在算法课的图谱之后来讲，因为图结构本身就靠遍历来驱动，而最短路和最小生成树本质上又都是在图这种结构上做优化。换句话说，你先把DFS/BFS吃透，后面理解最短路、生成树就会顺畅很多，它们是同一个思路在不同问题上的延伸。

1. 先从整体上拆解这几个算法的关系

1.1 图的遍历是所有图论算法的基础

不管是最短路也好，最小生成树也好，第一步都得先能“走”到图的每个节点。而图上的“走法”无非就两种：深度优先和广度优先。DFS是一条道走到黑，撞了南墙再回头；BFS是一层一层往外扩散，像水波一样推开。

学的时候要有一个很清晰的意识：DFS和BFS不只是两个孤立的模板，它们解决的是“图能不能被访问到、从一个点能到哪些点”这类连通性问题。我把它们当作整块图论知识的地基来看。比如大家熟悉的拓扑排序，用DFS可以写，用BFS也能写，只是思路不同。再比如无向图的连通分量、有向图的强连通分量，本质上也都是DFS的扩展用法。

1.2 最短路问题和最小生成树问题的本质区别

很多人容易把最短路和最小生成树搞混，原因是它们都在求“最小”，但对象完全不同。最短路求的是“从a点到b点的最小代价”，关心的是路径；最小生成树求的是“让所有点连通起来的最小总代价”，关心的是边集的取舍。

我习惯这样区分：如果题目问的是“从某个起点到某个终点的最少花费/最短时间/最少步数”，那就是最短路；如果题目问的是“要让所有城市通网/通水/通电，最少要修多长的线路”，那就是最小生成树。一个是单源到单点的局部最优化，一个是覆盖全图的全局最优化。

再往深了说，这两类问题在算法选型上也有很大差异。最短路问题里有单源的Dijkstra，也有全源的Floyd；最小生成树里有从点出发的Prim，也有从边出发的Kruskal。学的时候别急着背模板，先把“什么时候用谁”的道理搞清楚，下面的代码才不会白抄。

1.3 学习路线建议：先搜索，再最短路，最后生成树

我上课的习惯是给自己排一条主线：先把图的存储方式定下来（邻接矩阵、邻接表或者链式前向星），接着用DFS/BFS做连通性练习，再进入最短路，最后才是最小生成树。为什么要这么排？因为最短路里要反复进行“松弛操作”，本质就是遍历加贪心；而Prim算法从写法上看几乎是Dijkstra的孪生兄弟。你把前面基础打牢了，后面会发现很多代码模板换个皮就能复用。

另外，这一讲涉及的算法都对数据规模敏感。比如邻接矩阵存图简单，但V到1000以上就开始吃紧；优先队列优化的Dijkstra能应付十万级别的点；Floyd基本只适合二三百个点的小图。做实战题前一定要先看数据范围，这是我踩过无数次坑之后总结出来的第一条铁律。

2. 深度优先搜索：回溯就是DFS的灵魂

2.1 DFS的思维模型：一条路走到黑，再回头

DFS在代码上其实极其简单，核心就是递归。每次进入一个节点，尝试所有可能的分支，如果分支走不通或者走到头了，就回到上一个状态继续试别的分支。这个“回到上一个状态”的动作，就是回溯。

我把DFS的模板写成了固定三步：

1. 判断当前状态是否满足结束条件，满足就记录并返回
2. 遍历所有可能的分支，逐一尝试
3. 每次尝试前做状态标记，递归返回后撤销标记

在这里，第二步和第三步才是重点。递归本身包含了调用栈，所以DFS的空间复杂度是O(V)，体现在递归深度上；但搜索全部方案时，时间复杂度往往是O(2^N)甚至O(N!)，这是很多人容易忽略的点。如果题目数据范围稍微大一点，就要考虑配合剪枝，否则跑死也出不来结果。

2.2 回溯法的代码模板

这里的伪代码我会写得比较通用，但放在实际的DFS题目里可以直接套：

void dfs(当前状态) { if (满足结束条件) { 记录结果; return; } for (每个可能的分支) { 如果分支不合法，跳过; 做出选择，标记状态; dfs(进入下一层状态); 撤销选择，恢复标记; } }

这个模板几乎覆盖了全排列、组合、子集、n皇后、岛屿数量这类经典DFS题目。区别只在于“分支的选择”和“状态标记”怎么写。举个例子，全排列问题里状态标记是一个used数组，当递归到深度等于数组长度时记录答案；而n皇后问题的状态标记是列号、主对角线和副对角线的占用情况。

这里有个很常见的坑：不同题目的“状态撤销”方式可能完全不一样。排列组合类问题通常需要撤销的是布尔数组标记，记忆化搜索类问题可能完全不需要撤销。我在初期做题时，经常会多写一句撤销反而导致状态错误，后来才意识到剪枝和回溯的区别——回溯是“尝试别的可能”，剪枝是“提前排除不可能的路径”。

2.3 DFS的经典应用：从排列组合到图上连通性

DFS最常见的入门题是全排列和组合总和，这类题练的是对递归层数的控制；再往前走一步，就是图的连通性问题，比如判断一个无向图里有多少个连通分量，或者从某个点出发能到达的所有点。其实代码和图的遍历差不多：

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

这段代码不用回溯，因为这里要的是“到达过哪些点”，一旦标记了就是访问过了。但它和回溯模板的区别恰好说明了一个重要观点：DFS不一定要撤销状态，只有当你需要枚举不同路径方案时才必须撤销。这个区分是做DFS题的“分水岭”，我见过很多同学在这上面绕很久。

2.4 DFS的剪枝技巧

写DFS的时候最容易遇到的问题就是超时。本质上是因为搜索空间太大了，指数级别的分支数量在一些数据点上根本撑不住。剪枝的思路是：在递归早期就判断当前路径是否还有希望走向正确答案，如果没有就提前返回。

常见的剪枝策略我整理几个：

• 可行性剪枝：当前路径已经违反约束，直接return
• 最优性剪枝：即使当前路径继续走完，代价也已经超过已知最优解，剪掉
• 排序预处理：先对候选分支排序，把成功率更高的分支放在前面，往往能更快找到较优解，为剪枝创造机会

这些技巧在“组合总和”类问题上特别常用。我第一次遇到组合总和的数据范围加强版时，单纯靠回溯会严重超时，增加了一个“当前和大于目标值就返回”的判断，运行时间直接从不可接受降到几十毫秒。这个教训也说明了一个道理：DFS本身是一种暴力枚举的思维方式，只有搭配剪枝才能真正落地在工业场景中。

3. 广度优先搜索：BFS在层级与最短路径中的独特地位

3.1 BFS的核心：队列与扩散层

BFS的逻辑比DFS更贴近人的直觉。它在图上遵循一个严格的顺序：先访问起点，再访问起点相邻的所有点，接着访问它们的相邻点，一层一层向外扩展。为了保证这种层序顺序，BFS必须借助队列。

我用一句话概括BFS的本质：越先出队的节点，离起点的距离越近，且这个距离一定是最短距离，前提是图中所有边的权值相同。因此，BFS天然适合解决两类问题：一类是“最少步数/最短路径”，另一类是“层序遍历”，比如树的层序遍历、多源扩散模拟。

3.2 BFS模板：用队列模拟层序推进

下面是最标准的BFS模板，配套一个dist数组记录到每个点的最短步数：

void bfs(int s) { queue<int> q; dist[s] = 0; q.push(s); 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数组来代替vis数组，因为用它判断是否访问过的同时还可以顺便记录距离。如果是二维网格上的迷宫问题，只需要把“点”打包成坐标，数组换成二维即可，核心逻辑是一样的。

3.3 BFS在最短路径中的经典使用场景

BFS最典型的一个应用是“迷宫最短步数”。假设二维迷宫里有起点、终点和若干障碍物，每次只能上下左右走一格，问从起点到终点最少走多少步。地图规模在几百乘几百的范围内用BFS都非常稳。为什么不用DFS？因为DFS找到的第一条路径不一定是最短路径，你必须把全部分支都搜完才能确定答案，效率很差；而BFS的层序扩展天然保证第一次到达终点的路径就是最短路径。

另一个被反复拿出来考的场景是“多源BFS”，比如多个火源同时蔓延，或者多个快递站点同时开始送货，要计算某个位置被覆盖到的最早时间。处理方式也简单：给队列里一次性塞入所有起点，dist数组初始化成0，剩下的扩展示意和单源BFS完全一样。

3.4 A*算法与BFS的差异

先说结论：A算法是在BFS基础上加入了启发式评估的升级版。BFS只看当前扩散到哪里，完全不管哪个方向更有潜力；A则设计一个评估函数 f(n) = g(n) + h(n)，其中g(n)是起点到当前点的实际代价，h(n)是当前点到终点的估计代价，然后优先扩展f(n)最小的节点。

我用一个对比表来看它们的优缺点：

在游戏AI寻路里，A基本是标配，因为它的搜索范围远小于BFS，实时性更好。但BFS的代码简单、思想直观，面试里问基础题时出现频率极高。学的时候建议先吃透BFS，再往A延伸，不要一上来就纠结启发函数怎么设计。实际工程里启发函数往往只用一个曼哈顿距离或欧几里得距离就能取得很好的效果，反而是在代码的优先级队列维护上容易出bug。

4. 最短路算法：单源、多源、全源的全梳理

不管你是搞后端、客户端还是算法岗，最短路都是绕不开的高频考点。现实中导航、物流配送、社交网络的“几度人脉”背后都能归约成最短路问题。但算法本身有很多口味必要，选错了就是在错误的方向上浪费时间。

先放一张总览表，方便后面展开讲：

4.1 Dijkstra：贪心思想与堆优化

Dijkstra每次从尚未确定最短路的点中，挑出当前距离起点最近的点，然后用它去尝试更新相邻点的距离。这里最核心的前提是“所有边的权值非负”，因为只有这样才能保证当前取出的最近点以后不可能再被其他点更新，一旦出队它的最短路就确定了。

堆优化就是用优先队列维护候选点。每次更新的代码长这样：

void dijkstra(int s) { memset(dist, 0x3f, sizeof dist); dist[s] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } }

注意一下if (d > dist[u]) continue;这行，它能过滤掉那些已经被更小距离优化过的旧队列条目。这一行如果漏了，算法可能在自己的数据面前乱套，这是入坑Dijkstra后最容易犯的错误之一。

4.2 Bellman-Ford与SPFA：处理负权边

Dijkstra解决不了负权边，因为一旦有负数边，贪心的“当前最近点一定不会被更新”就失效了。比如起点到A点是5，起点到B点是10，但B到A有一条-6的边，A的最短路径实际上是通过B走的4，Dijkstra在起点直接取A的态度就会漏掉这个最优解。

Bellman-Ford的思路是进行n-1轮松弛，每轮遍历所有边，尝试用已知的dist[u] + w更新dist[v]。因为一条最短路最多包含n-1条边，所以反复松弛n-1轮后一定能收敛。如果第n轮还有边能更新，那就说明图里存在负环。

SPFA是Bellman-Ford的队列优化：只有上一轮被更新过的点才有资格更新别人的距离。这样在很多实际图中速度会快很多，但复杂度仍然不稳定，最坏情况可能会退化到O(VE)，挂大数据点的题时心里要有数。

4.3 Floyd：从动态规划视角看全源最短路

Floyd虽然代码短，但理解起来更绕。它其实是动态规划，dp[k][i][j]表示“只允许经过前k个中间节点时，从i到j的最短距离”。状态转移就是：要么不经过第k个节点，要么经过第k个节点，取两者的最小值。

写成二维滚动数组后就是大家最熟悉的三层循环：

for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } }

这里有个很关键的点：k必须放在最外层循环。如果把i和j放在外层，dp状态的含义就乱了，算出来的结果会出错。这个我在现场debug过好几次，都是因为觉得三层循环无所谓顺序，结果怎么跑都差几个数。

Floyd适合n小于等于300到500的场景，因为O(n^3)在1000个点时就开始吃力了。但它实现零门槛，既能求任意两点间距离，又能顺带做传递闭包，在小规模应用题里非常香。

4.4 最短路算法怎么选？看数据范围和权值符号

我自己的选择逻辑是这样的：

1. 如果权值全非负，优先用堆优化的Dijkstra，这是性能最好的通用单源方案
2. 如果存在负权边但没有负环，用Bellman-Ford或SPFA
3. 如果只是小规模图，点不超过几百个，也要求多个点对之间的最短距离，直接用Floyd最省事
4. 如果明确知道有负环，那道题的考点就不再是最短路本身，而是负环检测了

说实话，Dijkstra的出场率远远高于其他两个，这是面试题里最常见的考查点。负权相关的题出得不多，但一旦出就是区分度很大的题目，所以混个眼熟也很重要。

5. 最小生成树：为什么是“树”，并且是“最小”的

5.1 最小生成树到底在求什么

最小生成树的定义其实很直白：在原图上选n-1条边，让n个点保持连通，同时所有边权之和最小。为什么是n-1条边？因为这正好构成一棵树的边数，再多一条就会成环，少一条就不连通。算法领域里给了个严谨的定义：无环且连通，则必为一棵树。

实际场景很好理解：假设一个园区有若干个机房，机房之间可能有各种光纤线路，但运营商不希望你全铺一遍，而是让你挑最省钱的一组线路，保证每个机房都能间接或直接连通，这就是一个最小生成树问题。

5.2 Prim算法：从一个点开始“生长”

Prim算法的思路特别像Dijkstra：初始化时从任意一个点出发，把这个点加入生成树集合；然后重复n-1次，每次从“当前生成树集合”到“集合外”的所有边中，挑一条权值最小的边，把对应的点加入集合。

朴素Prim的代码复杂度是O(V^2)，适合稠密图。如果你用邻接矩阵存图，维数又不大，这个写法最简洁：

void prim() { memset(lowcost, 0x3f, sizeof lowcost); lowcost[0] = 0; for (int i = 0; i < n; ++i) { int u = -1, minv = INF; for (int j = 0; j < n; ++j) { if (!vis[j] && lowcost[j] < minv) { minv = lowcost[j]; u = j; } } if (u == -1) result = INF; // 图不连通 vis[u] = true; ans += minv; for (int v = 0; v < n; ++v) { if (!vis[v] && g[u][v] < lowcost[v]) { lowcost[v] = g[u][v]; } } } }

这个lowcost数组就是整个Prim的精华，它维护的是当前生成树到每个未加入点的最短边权。

5.3 Kruskal算法：排序 + 并查集

Kruskal的思路和Prim完全相反，它直接对边下手。把所有边按权值从小到大排序，然后依次遍历，如果一条边连接的两个点还不属于同一个集合，就把它们合并，同时把这条边加入最小生成树。这个“是否属于同一集合”的判断，用并查集实现非常自然。

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void kruskal() { sort(edges, edges + m); for (int i = 0; i < m; ++i) { int a = edges[i].u, b = edges[i].v, w = edges[i].w; int ra = find(a), rb = find(b); if (ra == rb) continue; fa[ra] = rb; ans += w; cnt++; if (cnt == n - 1) break; } }

这里涉及到并查集的两个核心优化：路径压缩和按秩合并。上面的代码里find函数用了路径压缩，查询效率会接近常数级别。如果只写一种优化至少要写路径压缩，不然大数据下性能堪忧。

Kruskal的时间复杂度主要取决于排序，O(E log E)，所以最擅长处理稀疏图。它的实现也比Prim直观，在我个人刷题经验里，实战中Kruskal的使用频率要高于Prim。

5.4 Prim vs Kruskal，什么场景怎么选

如果是稠密图，比如点只有一两百个但边接近全连，那邻接矩阵的Prim写起来很舒服；如果是稀疏图，比如几万条边分布在几千个点之间，直接用Kruskal排序合并会更稳。这两者的选择标准本质上就是稀疏和稠密的问题。

6. 实战避坑指南与常见问题排查

6.1 建图阶段最容易踩的坑

图论题的bug有相当一部分不在算法本身，而在建图。先说邻接表存图，如果有重边，一般要么取最小权值，要么直接把多条边全存进去让算法自行处理。如果是邻接矩阵，重边处理起来更麻烦，必须在读入时就做min操作。

还有无向图漏掉双向建边的问题。有些同学在写DFS模板题时记住要add(u,v)和add(v,u)，但一旦遇到复杂的题又重新犯错。无向图不建反向边，会直接导致所有后续算法跑出来的结果全是错的，而且这种错非常隐蔽，因为局部数据可能碰巧正确。

再提一个细节：如果题目给的是字符型节点，比如城市名是字符串，那最好先离散化成整数。否则每次比较字符串都会拖慢整个算法，而且一旦涉及数组大小，字符串做不了索引，很容易写出晦涩的代码。

6.2 搜索过程里的经典Bug

DFS最容易犯的错有两个：一是忘了在递归返回后恢复状态，导致后面的分支被前面分支的标记污染；二是搞错了结束条件，导致输出一堆重复或缺失的答案。

BFS则容易在dist数组上翻车：忘记把起点置0，或忘记把其他点初始化成无限大。还有一个常见问题就是队列无边界控制，导致访问越界，二维迷宫题里尤其多。我通常会在收尾处写好方向数组和越界判断，并且统一用函数封装，这样既不会漏判，也不会在某个方向写错正负号。多说一句，方向数组rowDir和colDir的对应关系一定要仔细，dir=0时走“上”，dir=1时走“下”，这个顺序在调试时是很折磨人的。

6.3 模板与板子之间搞混怎么办

我曾经见过有同学把Dijkstra的代码直接拿来做最小生成树的Prim，一开始长得很像，真跑起来结果全都错了。它们确实在结构上有相似之处，但更新逻辑不同：Dijkstra用“起点到当前点的距离”更新邻点，Prim用“当前生成树到邻点的最小边权”更新lowcost。把两个模板并排放在一起对比着学，比死背效果要好得多。

同样，Kruskal和最短路的Bellman-Ford也都是在处理边的循环，但Kruskal是先排序再挑边，Bellman-Ford是无序反复松弛。二者混乱的话，代码很容易在逻辑上拼出一些“四不像”。我的习惯是每学一个新算法，就把它和最相似的那个旧算法做一次对比分析，把差异写到注释里。这个习惯帮我省了非常多调试时间。

6.4 从题目限制来反推算法

面对一道图论题，我的破题顺序一般是：

1. 看数据范围，n、m分别到什么级别
2. 看权值是否可能为负，判断是否适用Dijkstra
3. 看题面问的是单源、全源还是全局连通
4. 再决定是搜索、最短路还是最小生成树

如果n只有几十，直接Floyd也行；如果n有十万，用堆优化Dijkstra是常规操作；如果n和m到百万，连Dijkstra堆优化都危险，这时就要考虑Johnson重标号之类更进阶的思路了，不过在算法基础阶段，能把上表里那些算法用对用熟已经足够应付绝大多数场景了。

7. 最后交个底：我自己的学习心得

这一讲的内容量确实不小，但你要是顺着“图的存储 → DFS/BFS → 最短路 → 最小生成树”这条线走下来，会发现它们不是孤立的考点，而是一套解决图问题的方法论。每次拿到新题，先想它是“问路”还是“连线”，再想它符不符合“无负权”的前提，最后套模板，思路会顺畅非常多。

在刚开始刷题的那些日子里，我其实特别容易被各种“优化技巧”带走，比如看到SPFA就觉得比Bellman-Ford高级，看到堆优化就觉得朴素Dijkstra没用。后来踩了些坑才发现：能用简单算法解决的问题就不上复杂的，代码短、逻辑清楚、不容易写错，才是第一位的。先把每一种基础算法写熟，再根据题目要求一点点升级，这条路走得最稳。希望这份总结能帮正在学图论的你少走一些弯路。