企业官网建设流程全解析

前阵子训练营有个同学跟我吐槽，说一看到"图论"两个字就头皮发麻，觉得那是ACM选手的专利。结果真跟着代码随想录走到day52，把图论专题5刷下来，他自己都没想到能被最短路问题虐得这么心甘情愿。今天这篇就想聊聊我在这个专题里的核心收获，包括建图选型、四种最短路算法的拆解、从题意到AC的完整链路，还有那些不写在模板注释里的坑。适合正在刷图论、准备面试或者被最短路径绕晕的朋友，老手也可以直接跳到后面看问题排查部分，应该能帮你少走几步弯路。

1. 图论专题5到底在练什么：先看懂这一部分的定位

1.1 一整条图论主线是怎么走到这里的

代码随想录的图论安排是有梯度的，不是上来就让你背Dijkstra模板。专题前面先解决的是"图怎么存、怎么遍历"，从邻接矩阵、邻接表到DFS和BFS，把最基础的东西夯实。后面又花时间讲了并查集和最小生成树，到专题5的时候，整个训练营已经把"静态的图"吃得差不多了，剩下的就是最短路问题——也就是动态求两点之间的最优路径。

到了day52这个节点，一个很现实的信号是：图论的基础模型你都已经见过了，卡哥的题单也刷到比较深的位置。这时候如果还不会建图、不会选算法，前面那些题等于白练。所以专题5的设计心思很明确，就是逼你把"图论抽象能力"和"算法选型能力"合二为一。说白了，前面是认识零件，这讲是组装整车。

最短路问题在面试里的出现频率有多高？字节、阿里、腾讯这些大厂主管面经常拿一个带权图的题出来，不看你会不会背代码，而是看你能不能把业务场景翻译成图，然后告诉面试官"这里该用Dijkstra，因为我们没有负权边"。

1.2 最短路问题的核心模型与思考框架

最短路问题的标准模型是：给定一个有向图（偶尔无向），每条边上有权重，求某个源点到其他所有点（单源最短路）或者任意两点之间（全源最短路）的最小权重和路径。

我建议大家先形成一个思考框架：拿到题先问三个问题——边的权重有没有负数？是单源查询还是多源全查？图的规模有多大？这三个问题的答案几乎可以直接决定你要用哪种算法。负权边直接排除Dijkstra，全源优先考虑Floyd，图特别大就要避开O(V^3)的Floyd。这个框架建立起来之后，图论专题5的题就不再是"背四种算法模板"，而是变成一个"条件匹配"的过程。

图论最短路这类题还有一个容易忽略的点：图不一定是为了最短路出现的。很多题目表面是二维网格、是迷宫、是换乘线路，剥开之后全是图模型。所以专题5真正的核心能力，不是记代码，而是"看穿伪装"的能力。

2. 建图选型：所有图论题的第一步都是这步

很多同学学最短路的时候有个通病，上来就背Dijkstra的二维数组写法，完全不知道代码里那个vector<pair<int, int>>是从哪来的。这里得先停下来好好讲讲建图，因为后面所有算法都是在"图已经建好"这个前提下跑的。

2.1 邻接矩阵：写起来爽，跑起来哭

邻接矩阵用一个二维数组来存边，代码最简单，判断两个点之间有没有边、边的权重是多少，都是O(1)时间。我最早学图论的时候特别喜欢用这个方式，因为初始化一个N*N的二维数组，把每条边填进去，就完事了。

可一旦图规模上来，邻接矩阵就变成了灾难。空间复杂度是O(V^2)，注意这里的V是点的数量。如果题目给了10万个点，你开一个10万乘10万的数组，至少是40G内存，直接爆掉。实际竞赛和面试题里，超过1000个点用邻接矩阵就已经很勉强了。而且遍历某个点的所有邻居需要O(V)，也就是说，哪怕这个点只有1条边，你也要扫一遍整个数组。

所以我现在对邻接矩阵的态度是：只用来解面试场景下明确告诉"这是一张稠密图"的题，或者数组规模特别小（比如小于200个点）的题。其余情况，一律看邻接表和链式前向星。

2.2 邻接表：工程实践的正确姿势

邻接表的核心思路是：只为每个点维护自己的邻居列表，谁有边就存谁的，没有边就空着。这样存图的总空间是O(V+E)，E是边数。对于稀疏图来说，这个存储量比邻接矩阵小好几个数量级。

在C++里我常用vector<vector<pair<int, int>>>，内层pair的第一个数是终点节点，第二个数是权重。比如graph[u].push_back({v, w})就是把一条从u到v、权重为w的边加入图。在Python里则用字典或者列表套列表，graph[u].append((v, w))就行。

邻接表另一个好处是遍历一个点的所有邻居特别自然，一个for循环拿到所有pair，直接读终点和权重。写Dijkstra、SPFA、拓扑排序的时候手感特别顺。用邻接矩阵写这些算法，每次遍历都要嵌套一层全量循环，既难看又容易超时。从我刷题经验来看，90%以上的最短路题用邻接表就够了，没必要再折腾更底层的存法。

2.3 链式前向星：竞赛玩家才懂的浪漫

链式前向星是C++竞赛圈很常用的一种静态数组存图方法，本质是用三个数组head、to、next来模拟链表，把所有边串起来。它比vector<vector >性能更好，因为vector在插入过程中会扩容，产生额外的动态分配开销。链式前向星所有空间一次开好，每个节点的邻居通过head[u]找第一条边，然后沿着next数组一条条摸下去。

有同学可能会问：面试题有必要用链式前向星吗？说实话绝大多数没必要，面试官更看重你的思路和代码可读性，vector版邻接表完全够了。但如果目标是打ACM、ICPC这种比赛，链式前向星必须会，因为比赛数据有时候会到百万级的边，vector扩容那点性能差距真的会影响能否卡过时限。

我自己的习惯是：日常训练和面试准备用邻接表，打周赛如果发现内存卡得死就用链式前向星。专题5的题练下来你会发现，大部分题邻接表都能过，链式前向星更多是手速和习惯问题。

3. 四种最短路算法逐个拆解：原理、代码与选中逻辑

最短路算法里大家接触最多的就是Dijkstra，但面试和竞赛往往会用Bellman-Ford、SPFA和Floyd来设坑。这里我按"算法原理-适用条件-代码注意事项"的结构分别拆一下。

3.1 Dijkstra：贪心思想为什么在这里就对了

Dijkstra解决的是单源最短路问题，要求图的边权重都是非负数。核心思路是贪心：维护一个"已经确认最短路的集合"，每次从还没确认的节点里挑一个距离源点最近的点，把它加入集合，然后用它去松弛（更新）它所有邻居的距离。

听着有点像BFS，但BFS只适用于无权图，Dijkstra通过优先级队列（Priority Queue）保证每次弹出的都是当前全局距离最小的点，这也是它能在O((V+E)logV)时间内跑完的关键。优先队列里同时存"当前距离"和"节点编号"，每次弹出来之后，要先判断这个pair是不是过期数据。

判断过期数据这个点我踩过坑。因为同一个节点可能被多次加入优先队列，比如第一次距离是5，后来被更新成3，队列里就会出现两个记录。处理方式是在弹出后检查一下：if (dist[node] < currentDist) continue;，如果dist数组里记录的距离已经比这个pair里的距离小，说明这是老数据，直接跳过。不写这个判断，性能会退化，甚至可能因为重复松弛导致逻辑错误。

Dijkstra模板代码基本长这样（C++邻接表版）：

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; void dijkstra(int s, vector<vector<pair<int, int>>>& graph, vector<int>& dist) { int n = graph.size(); dist.assign(n, INF); dist[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] < d) continue; // 跳过过期记录 for (auto [v, w] : graph[u]) { if (dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } } }

这里INF我习惯用0x3f3f3f3f，而不是INT_MAX。因为INT_MAX加上一个正数会溢出变成负数，导致松弛判断完全错乱。0x3f3f3f3f是十进制约10亿级别，足够大，而且两个0x3f3f3f3f相加不会溢出int范围，是一个在竞赛和面试里都很安全的"伪无穷大"。

3.2 Bellman-Ford：负权边的老实人解法

Dijkstra处理不了负权边的原因其实很有意思。因为贪心一旦确认某个点距离最小，就把这个点"定下来"了，以后不再更新。如果存在负权边，后面出现的更短路径完全可能绕到已经确认的点，所以贪心的前提就崩了。

Bellman-Ford用一个很老实的策略：没有"确认"这个操作，做V-1轮全量松弛。每一轮都遍历所有边，尝试用边的起点更新终点。为什么要做V-1轮？因为在一个没有负环的图里，从源点到任意点的最短路径最多包含V-1条边，所以V-1轮松弛之后，所有距离必然达到稳定状态。

Bellman-Ford的代码实现比Dijkstra还简单，三重循环改成两重就行：

void bellmanFord(int s, int n, vector<Edge>& edges, vector<int>& dist) { dist.assign(n, INF); dist[s] = 0; for (int i = 0; i < n - 1; ++i) { for (auto& e : edges) { if (dist[e.from] != INF && dist[e.from] + e.w < dist[e.to]) { dist[e.to] = dist[e.from] + e.w; } } } // 第V轮再松弛，如果还能更新，说明存在负环 for (auto& e : edges) { if (dist[e.from] != INF && dist[e.from] + e.w < dist[e.to]) { // 图中有负环，无法求出稳定最短路 } } }

注意第二段循环，这个就是负环检测。如果第V轮还能更新，说明图中存在一条负权回路，最短路径可以被不断缩减到负无穷。面试问Bellman-Ford的时候，十次里有八次要问负环检测，这个判断一定要能现场手写出来。

3.3 SPFA：队列优化与它的爱恨情仇

SPFA（Shortest Path Faster Algorithm）本质上是对Bellman-Ford的优化。Bellman-Ford每一轮都遍历所有边，但很多时候很多边根本不会引起松弛。SPFA的做法是：只把"成功更新了邻居"的节点加入队列，下一轮只从队列里取这些可能引起连锁反应的节点来处理。

SPFA的平均时间复杂度确实比Bellman-Ford好，很多稀疏图上接近O(E)，最坏情况下则退化到O(VE)。我对SPFA的使用建议是：能用Dijkstra优先用Dijkstra，SPFA只有在图里明确有负权边且没有负环时才考虑。还有一个点，如果面试官问"SPFA会死循环吗"，不是说代码写错，而是如果图里有负环，SPFA会因为距离不断变小而无限循环下去。所以SPFA也需要一个数组记录每个节点入队的次数，如果某个节点入队超过V次，就说明有负环。

SPFA核心代码片段：

void spfa(int s, vector<vector<pair<int, int>>>& graph, vector<int>& dist) { int n = graph.size(); dist.assign(n, INF); vector<int> cnt(n, 0); vector<bool> inQueue(n, false); queue<int> q; dist[s] = 0; q.push(s); inQueue[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for (auto [v, w] : graph[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (!inQueue[v]) { q.push(v); inQueue[v] = true; if (++cnt[v] >= n) { // 存在负环 return; } } } } } }

这里的inQueue数组很重要，它避免同一个节点同时出现在队列里多次，减少无效计算。cnt数组就是入队次数计数，超过n直接认为有负环，避免死循环。

3.4 Floyd：最简单的全源最短路

Floyd算法解决的是全源最短路，询问任意两点之间最短距离。它的思路可以用一句话概括：用每个节点当中转站，尝试把任意两点之间原有的路径变得更短。写成三重循环就是for k in 0..n: for i in 0..n: for j in 0..n: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

这个算法的时间复杂度是O(V^3)，空间复杂度O(V^2)。所以Floyd只适合点数量很小的场景，一般V在500以内可以考虑，再多就等着超时或者爆内存。

Floyd实现起来非常朴素，不需要建邻接表，直接维护一个二维距离矩阵就行。初始化时把每对点的距离置为INF，自己到自己置为0，有边就填权重，然后三重循环更新。它还有一个隐藏功能：可以在不额外写很多代码的情况下，通过更新过程顺带求出路径的前驱节点，方便恢复完整路径。

我用Floyd的场景不多，主要是一个图上反复询问任意点对最短路，且点数量少时才用。比如一些面试题给一个最多20个节点的图，问任意点对最短路，Floyd写起来比跑V次Dijkstra简单太多。

4. 实际操作：一道经典题从题意到AC的完整链路

光讲理论不够，这里我用一道在代码随想录图论专题里非常经典的问题来串一遍完整流程：求有向无环图中从一个源点出发到其余所有点的最短路径（这里还没引入负权或环的复杂性，后面再扩展）。

4.1 题目建模：把文字翻译成图

题目一般不会直接告诉你"这是一张图"，而是给你一段描述，比如"给定n个城市，m条航班线路，每条线路有飞行费用，求从城市A到城市B的最少费用"。拿到这样的题目，第一步就是建模。

我建模的一般步骤是：把"城市"抽象成节点，把"航班线路"抽象成带权有向边，把"飞行费用"抽象成边的权重，把"最少费用"翻译成求最短路。这一段听起来很简单，但很多同学就是栽在这里，因为题目可能会嵌套在其他语言外壳里，比如"某公司有n种操作系统，升级过程有依赖关系，每次升级消耗一定量子，求最小升级消耗"。不管壳怎么变，内部都是同一个图模型。

如果题目要求的是"从一个城市到另一个城市"，那就是单源单目标的最短路，Dijkstra跑完直接看dist[target]即可。如果题目说"要求从起点到所有城市"，仍然是用单源最短路算法，dist数组就是答案。

4.2 参数选择：为什么这张图要用Dijkstra

建模完成之后，我通常会列一个参数表快速判断算法：

上面这道题里，航班费用必然是正数，没有负权边，单源查询，所以Dijkstra是正确且效率最高的选择。时间复杂度O((V+E)logV)，完全够用。

另外补充一个细节：如果题目是无向图，Dijkstra同样可以用，把一条无向边当成两条有向边，分别插入两个节点的邻接表即可，这属于建图时的基本操作。

4.3 代码复现与调试实录

我在调试这道题的时候遇到过一个问题，很典型：我把所有节点的dist初始值都设成了INF，但忘记设置dist[source] = 0。当时的表现是，所有输出都是INF，完全没有距离被更新。排查方式很简单，先在入口处打印一下dist数组的初始值，马上就能看出来。

还有一次，我没有在优先队列弹出节点时跳过过期记录，导致同一个节点被反复松弛。结果在小数据样例上侥幸通过了，但换到大数据样例直接超时。后来养成一个习惯：写完Dijkstra先随手在一个有数十个节点的随机图上跑一遍，用暴力BFS对比结果，确保正确性。

刷题阶段我建议你准备一个模板文件，把上面提到的Dijkstra、Bellman-Ford、SPFA、Floyd都提前写好，带注释，然后在每一道新题上套模板。这不叫偷懒，相反，这是竞赛选手最常用的策略：算法模板固定化，把注意力放在建图和题意转化上，因为那才是题目的真正难点。

5. 顺带把最小生成树和并查集也串起来

代码随想录图论专题5之前，训练营里已经出现过并查集和最小生成树的内容。为什么会放在前面？因为图论是一个大体系，最短路并不是唯一"求最优"的问题。很多同学学到后面容易把最短路和最小生成树搞混，这里专门辨析一下。

5.1 Kruskal与Prim：最短路容易和谁搞混

最小生成树的目标是：在无向连通图中找到一棵包含所有节点的树，使得树的所有边权重之和最小。说白了，是找一个"连接所有点且总代价最小"的结构，而不是从某个点出发到另一个点的最短路径。

Kruskal算法的思路是贪心：把所有边按权重从小到大排序，用并查集维护节点是否已经连通，每次选一条不会形成环的边加入生成树，直到所有点连通。Prim则是从一个起点出发，不断把距离已选集合最近的节点拉进来。

这里把Dijkstra和Prim摆在一起看很有意思，两者代码结构看起来几乎一样，都是维护一个"到集合的距离"并用优先队列选最优，但Dijkstra比较的是到源点的累计距离，Prim比较的是到已选集合的直接边距离。面试官特别喜欢拿这个暗坑来考察你是真懂还是只背模板。

5.2 并查集实现细节：路径压缩与按秩合并

并查集不是一个具体的图算法，而是图论里高频使用的数据结构。在Kruskal里，它用来判断两个点是否已经在同一个集合，也就是判断加一条边会不会构成环。

核心操作就两个：Find找根节点，Union合并两个集合。基础实现不到十行，但要写对优化。路径压缩就是把find过程中遇到的所有节点都直接挂到根节点下，这样后续查询几乎是O(1)。按秩合并则是让树尽量矮，让"小树"合并到"大树"上，减少find的深度。两个优化加在一起，均摊复杂度可以认为是阿克曼函数的反函数，几乎常数时间。

写并查集最容易犯的错误是union的时候忘记先find。如果直接把一个节点的父指针挂到另一个节点上，很可能把非根节点当作根来连接，导致环的出现或者集合分裂。我建议所有union操作都这样写：rootX = find(x); rootY = find(y); if (rootX != rootY) parent[rootX] = rootY;，先统一拿根，再连接，不然排查起来非常痛苦。

5.3 从最短路到最小生成树：两种"最"的辨析

最短路关心的是"两点之间"，最小生成树关心的是"全图连通"。举个例子：一个城市有A、B、C三个区，最短路可以回答"从A到C最快怎么走"，最小生成树回答的是"要让三个区互相连通，修路最少要花多少钱"。

所以我做题时有个习惯，先看问题问的是"从一个点到另一个点的距离"还是"让所有点连通的最小总代价"。前者往最短路靠，后者往最小生成树靠。这个判断失误，比算法写不出来还要致命。

代码随想录把并查集和最小生成树放在最短路前面，就是希望你先建立"图结构"和"连通性"的直觉，再去做路径优化。到了专题5，你在脑子里已经有了一张完整的图论网络图，知道哪个知识挂在哪个节点下面，这对接下来的刷题帮助特别大。

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

图论专题5练到后半段，大家的代码都写得越来越快，但报错和超时的花样也越来越多。这里把我自己踩过和帮别人排查过的几个经典问题整理成速查表，基本都是高频坑。

6.1 死循环、超时、越界的经典死法

死循环最常见的原因是SPFA遇到负环，我之前已经说过解决办法是记录入队次数，超过V次直接退出。另一个死循环容易出现在BFS遍历图的时候——如果没有visited数组，一个无向图中两个节点之间会来回走，永远停不下来。BFS遍历图时必须每次入队就标记visited，而不是等到出队才标记，否则会出现重复入队，导致队列无限增长。

超时问题先别急着优化算法，先检查是不是邻接表写成了O(V)遍历。有些同学明明用的是邻接矩阵，却在外层套了两三层循环，一个上千个点的图直接就卡死了。改用邻接表之后，同样的逻辑可能快上百倍。如果确实需要更极致性能，再考虑链式前向星。

越界问题则主要集中在数组下标上。图的节点编号如果是1到n，你在初始化vector的大小时写成n而不是n+1，一跑就段错误或者读到非法内存。我自己一般统一用0-index或者1-index，然后所有循环都跟它对齐，写完之后数一遍"vector大小、for循环边界、输入读取方式"是否完全一致。这个习惯帮我少了很多半夜debug。

下面这张速查表建议存一下：

6.2 为什么Dijkstra在负权图上翻车

面试爱问的一个经典问题，也是训练营里讨论最多的：Dijkstra遇到负权边为什么会错？我用自己的话讲清楚：Dijkstra每次从优先队列里弹出的点是"当前已知距离最小的点"，它假设这个距离之后不会再变小。这个假设只在所有边权非负时成立，因为一个正权边不可能让某个点绕一圈后距离变得更小。

但图里有负权边的时候，完全可能出现一条"藏着的"更短路径。举个例子，源点s到a的距离是5，s到b的距离是3，b到a有一条-4的边。Dijkstra在第一轮就会选b作为确认节点，但真正到a的最短路径是s→b→a，总距离是-1，比直接s→a的5小太多。可惜的是，当Dijkstra确认b之后，它可能早就把a的距离设为5，并且以为那就是答案了，不会再去翻旧账。这就是贪心"提前确认"带来的漏洞。

理解这个原理之后，你就明白Bellman-Ford为什么要做V-1轮松弛——它不提前确认任何点，每一轮都可能推翻之前的结论。SPFA则是在Bellman-Ford基础上，只对被影响的节点做后续更新，同时仍然不预设任何"已确认点"。

6.3 建模能力的训练方法

有同学觉得"题意转成图"这个能力很玄学，其实它是可以刻意训练的。我自己的方法很简单：每次刷题之前，不管题目本身是不是图论题，都先在草稿纸上用笔画出"节点代表什么、边代表什么、权重代表什么"这三个问题的答案。如果画图的时候能5分钟内明确回答，就说明建模没跑偏。

练到中后期，我会专门挑一些不是图论标签的题目来反向练习。比如字符串转换、依赖调度、状态压缩类题目，看看它们能不能被抽象成最短路问题。比较典型的是"单词接龙"——单词是节点，单词间如果能转换就加一条权重为1的边，最短转换次数就是最短路长度。这种跨领域训练，才是图论专题5真正想带给你的能力。

另外，我还习惯把同种建模模板归类：网格图就直接把每个格子当成一个点，相邻格子之间连边；有向依赖图就注意处理环；拓扑排序与最短路结合时，要小心按照拓扑序来松弛。这些模板归纳多了，到考场上自然一眼就能看穿题目的本质。

写到最后，分享一个我自己的小习惯：从day52开始，我不再追求每道题AC之后立刻开下一题，而是花几分钟做个复盘，把题目的建模方式、陷阱、算法选择理由写进一个专门的本子。这样回头看时，图论专题5的题目能形成一张自己的知识地图，而不是零散的一百多道题名。下次某个朋友再跟我吐槽"图论好难"，我就直接告诉他：难的不是算法，是建模和选型的直觉，这两个东西靠刷题量堆出来，但更靠每次刷完题多问自己一句为什么。