企业官网建设流程全解析

1. 图的定义与存储结构：先搞清楚图长什么样

1.1 图的逻辑结构：从“朋友圈”到“路线图”

很多初学者听到“图”这个数据结构，第一反应是“是不是就是画一张图？”其实这里的图（Graph）跟画在纸上的图完全不是一回事，它是一种描述对象之间关系的抽象模型。我用一个最直观的例子来解释：把你的手机通讯录打开，每个人是一个节点（顶点），两个人如果互相认识，那就在这两个节点之间连一条线（边），这么一整张关系网，就是一个图。再比如地图导航，每个路口是一个节点，两条路之间的连接是边，然后给每条边标上“距离”这个权重数字，就变成了带权重的图。

那树跟图有什么区别呢？树是一种特殊的图，它满足两个硬性条件：一是连通的，也就是任意两个节点之间都能找到路径走通；二是没有环，不能出现“走一圈又绕回原点”的情况。而一般的图没有这么严格的限制，它可以有环，可以不连通，甚至可以有自环（自己连自己）。理解这个区别非常关键，因为很多算法对树的假设和对图的假设完全不一样，比如树上的DP（动态规划）可以直接递归做，但图上的算法就要考虑环和负权边的存在。

图的存储有几种主流方式，我在实际学习和做题过程中，最常用的是三种：邻接矩阵、邻接表和链式前向星。邻接矩阵用一个二维数组a[i][j]表示顶点 i 到顶点 j 之间是否有边（或者边的权重），它的优点是查询任意两点之间是否相连的时间复杂度是 O(1)，缺点是空间占用是 O(n²)，顶点一多就爆内存，比如 10000 个顶点，光是二维数组就要开 1 亿个 int，内存直接爆炸。邻接表用“数组+链表”或者“vector 数组”的方式来存储每个顶点的邻居列表，空间复杂度只有 O(n+m)，其中 m 是边的数量，这在稀疏图（边很少的图）里优势巨大。链式前向星本质上是用数组模拟链表的一种方法，效率更高，适合在算法竞赛中追求极致性能时使用。

1.2 建图的三个细节：无向边、重边与自环的处理

我见过太多人在建图这一步就写错了，后面所有算法跟着全错。这里我重点提醒三个细节。第一，无向图的边要存储两次。比如输入是“1 2”表示顶点 1 和顶点 2 之间有一条无向边，那么你需要同时添加add(1,2)和add(2,1)两条记录。很多新手只加一条，结果遍历的时候只能从 2 走向 1，不能从 1 走向 2，BFS（广度优先搜索）和 DFS（深度优先搜索）的结果完全不对。第二，重边的问题。题目里可能输入两条完全一样的边“1 2”出现两次，如果你的算法需要求最短路径，重边不影响正确性（取最短的那条即可），但如果是计数或者拓扑排序，就要格外小心是否需要去重。第三，自环，也就是add(i,i)，这在某些算法（比如拓扑排序）中需要特殊判断，因为自环会导致入度计算出现问题。

建图选哪种方式，取决于题目给的数据范围。如果 n 在 100 以内，邻接矩阵随便用，写起来最直观；如果 n 达到 10⁵ 级别，邻接矩阵必死，必须用邻接表或者链式前向星。我个人习惯在学习阶段用 vector 动态数组实现邻接表，理解清楚之后再去接触数组模拟的写法。

// 邻接表建图标准写法（C++ 为例） const int MAXN = 100005; vector<int> G[MAXN]; // 存储每个顶点的邻居编号 void addEdge(int u, int v) { G[u].push_back(v); } // 无向图需要调两次 addEdge

2. 图的遍历：DFS 与 BFS 的底层逻辑和进阶用法

2.1 深度优先搜索 DFS：一条路走到黑，撞了南墙就回头

DFS 的思想极其简单，一句话概括：从起点出发，选择一个邻居走进去，然后从这个新节点继续选择它的邻居深入，直到走不下去，再回溯到上一个分叉口，继续尝试其他方向。这个过程和我们平时玩迷宫的策略完全一致。在算法实现上，DFS 有两种写法：递归和显式栈。递归写法最简洁，代码只有几行：

bool visited[MAXN]; // 防止重复访问 void dfs(int u) { visited[u] = true; // 处理当前结点，比如打印、计数等 for (int v : G[u]) { if (!visited[v]) dfs(v); } }

但我要提醒一点，递归 DFS 在图上如果深度特别大（比如一条链状图有 100 万层），会栈溢出。这时候需要把递归改成显式栈的迭代写法。还有一个细节：visited 标记的位置极其关键。一棵树不会有环，所以树上的 DFS 不需要每次进入都判断 visited；但图有环，如果不标记，DFS 会陷入死循环。我第一次写带环图的 DFS 就吃过这个亏，跑起来程序一直不结束，还以为是数据量太大，后来调试半天才发现是环的问题。

2.2 广度优先搜索 BFS：一圈一圈往外扩散

BFS 的核心特征是“分层扩散”。它使用队列这种数据结构，先把起点放进去，然后取出队首元素，访问它的所有邻居并把这些邻居放入队尾，接着再取出下一个队首元素，继续访问……由于先进先出的特性，距离起点近的节点一定先被访问到。正因为这个特性，在无权图（每条边权都为 1）中，BFS 求最短路径是天然正确的。

我之前用 BFS 做“从起点到终点的最少步数”的迷宫题，把数组dist[u]记录为“从起点到 u 的最短步数”，然后每访问一个新节点 v，就令dist[v] = dist[u] + 1。这里有一个特别容易犯的错误：同一个节点可能被多个不同节点同时访问到，需要确保只在第一次发现它时才更新距离。用visited数组或者dist初始化为 -1 都可以解决。我在实际调试时更推荐dist初始化为 -1 的方法，因为这样调试时直接看数组值就能知道哪些节点还没被访问过。

queue<int> q; int dist[MAXN]; memset(dist, -1, sizeof(dist)); dist[S] = 0; q.push(S); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : G[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } }

2.3 遍历在实际场景中的应用：连通分量与二分图判定

学遍历不是单纯为了遍历，它在实际问题中有一堆直接应用。第一个应用是连通分量计数：你只需要对每个未访问过的节点执行一次 DFS 或 BFS，执行了几次就说明图中有几个连通块。这个思路在社交网络分析里很实用，比如判断这个社交网络中有多少个小圈子。第二个应用是二分图判定：二分图就是“所有节点可以被分成两个集合，任何一条边的两端都在不同集合里”的图。怎么判断？染色法——从起点开始给节点交替染上颜色 0 和 1，如果遍历过程中发现某个节点已经被染过色，且颜色和当前想染的颜色冲突，那就说明图中存在奇数长度的环，这张图就不是二分图。

还有一点我想多说两句：DFS 和 BFS 在不同题目里的选用策略。如果题目要求输出“一条从起点到终点的路径”（不要求最短），DFS 更容易实现。如果需要“最少步数”或“最短路径长度”，BFS 是首选。如果要对全图进行某种递归性质的判断（比如拓扑排序、强连通分量），DFS 更强。

3. 最短路径算法全解析：Dijkstra、Floyd、Bellman-Ford 与 SPFA

3.1 Dijkstra 的正确定位：贪心思想处理非负权边的利器

Dijkstra（迪杰斯特拉算法）是求解“单源最短路径”最常用的算法。它解决的核心问题是：给定一个起点，求它到图中其他所有顶点的最短路径长度。算法的思路用一句话讲就是：维护一个当前已知的最短距离集合，每次从未确定的节点中选一个当前距离最小的节点，把它确定为“已经找到最短路径”的节点，然后从这个节点出发松弛它的所有邻居。

为什么能贪心？因为如果所有边权非负，当前距离最小的那个节点，不可能再通过其他路径变得更短了——其他路径至少要先经过另一个节点，而那个节点到起点的距离都已经不小于当前值了，再加上非负的边权，总和只会更大。这个逻辑很重要，理解了它你就明白为什么 Dijkstra 不能处理负权边：一旦出现负权边，当前距离最小的节点可能通过一条“先走一个稍大的正边、再走一个很大的负边”的路径变得更短，贪心就不成立了。

代码实现上，朴素版本的时间复杂度是 O(n²)，用优先队列（堆）优化后可以降到 O(m log n)。我在写堆优化版本时踩过一个坑：priority_queue默认是大顶堆，取出来的是最大值，所以需要自定义比较器或者把距离存成负数。更简单的做法是直接存储pair<距离, 节点编号>，因为 pair 的比较默认先比较第一个元素，而小顶堆需要用greater。

// 堆优化 Dijkstra 核心代码 using PII = pair<int, int>; // {距离, 节点} priority_queue<PII, vector<PII>, greater<PII>> pq; int dist[MAXN]; bool done[MAXN]; // 标记是否已确定最短路 dist[S] = 0; pq.push({0, S}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (done[u]) continue; // 惰性删除，很重要 done[u] = true; for (auto [v, w] : G[u]) { if (dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } }

done[u]这个标记不能省，否则同一个节点可能被松弛多次，时间复杂度会退化。同时“惰性删除”这种写法务必掌握：因为优先队列里可能存储了同一个节点的多条记录，当你取出一个节点时，如果它已经被标记为 done，就直接跳过，不需要在更新 dist 时手动删除旧记录，这是工程上最省事的策略。

3.2 Floyd-Warshall 的多源最短路径：三重循环的暴力美学

Floyd 算法解决的是多源最短路径问题，也就是求任意两点之间的最短路径。它的实现极为简单，核心就是一个三重循环：

int d[MAXN][MAXN]; // d[i][j] 初始为 i 到 j 的边权，无路记为 INF for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (d[i][j] > d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j];

很多人不理解为什么中间循环变量 k 必须放在最外层。我当年也困惑过。这里的逻辑是：d[i][j]在循环过程中，计算的是“只允许经过前 k 个节点作为中转点”的最短路径。第 k 轮循环时，d[i][j]有机会通过新加入的节点 k 作为中转来缩短距离。如果你把 k 放在最内层，就相当于你在更新 i 和 j 的过程中才肯使用 k，这会导致很多需要多个中转点的路径计算不完整。实际上，这个三重循环等价于动态规划的状态转移，k 是阶段变量，必须按阶段顺序推进。

Floyd 的时间复杂度是 O(n³)，空间复杂度 O(n²)，所以 n 超过 500 就基本玩不转。但它的优势是代码极短，思路简单，不容易写错，而且天然可以处理负权边（只要没有负环）。在 n 比较小、需要多次查询任意点对距离的场景下，直接 Floyd 是最舒服的选择。

3.3 Bellman-Ford 与 SPFA：负权边的处理与负环判定

Bellman-Ford 算法的思想更朴素：对所有边进行 n-1 轮松弛操作。第 i 轮结束后，可以保证所有不超过 i 条边的最短路径已经正确求出。为什么是 n-1 轮？因为一条最短路径最多包含 n-1 条边，再多就必然经过环了。如果经过一个环能缩短路径，说明存在负环，而这其实意味着不存在所谓“最短路径”——可以无限绕环把路径压到负无穷。

那么怎么判断负环？很简单：在第 n 轮时如果还能进行松弛操作，说明图中存在负权环。这个判定在 ACM 竞赛和实际工程中非常重要，比如金融领域里寻找套利机会就是是“检测是否存在负环”的经典应用。

SPFA 是 Bellman-Ford 的队列优化版，它的核心思想是：只有被松弛过的节点，才可能引起它邻居节点的距离更新，所以用一个队列来维护这些“待处理节点”。SPFA 的实现比 Bellman-Ford 更短，平均复杂度表现也更好，但它在最坏情况下（比如精心构造的网格图）会退化到 O(nm)，所以很多严谨的竞赛选手会直接放弃 SPFA 改用堆优化的 Dijkstra。我的建议是：如果题目中有负权边，先判断有没有负环，没有负环再考虑 SPFA；如果边权非负，无脑用堆优化 Dijkstra，稳定高效。

3.4 题目中的常见变式：路径计数、最短路树与分层图

最短路径算法的应用远不止求一个距离值。比赛里常见的第一种变式是“求最短路径有多少条”，这时候维护最优解的同时还需要维护一个计数数组，松弛成功时cnt[v] = cnt[u]，二者相等时cnt[v] += cnt[u]。第二种变式是“最短路树”，即在所有最短路径构成的子图中选出一棵树，这在层次图分析中很有用。第三种变式是“分层图最短路”，比如你可以最多免费乘坐 k 次飞机，要求从甲地到乙地的最少花费。这种题把图复制成 k+1 层，每层之间用“免费边”连接，转换后就是一个普通最短路问题。我在处理这类题目时的心得是：把“使用掉一次特权”看成移动到另一层图的动作，建模思路就通了。

4. 拓扑排序与有向无环图：把复杂的先后依赖关系理顺

4.1 拓扑排序的本质：找一种“合法”的顺序

拓扑排序只适用于有向无环图（DAG），它的核心目标是：把图中所有顶点排成一个线性序列，使得对于每一条有向边 u→v，u 都排在 v 的前面。我用一个生活场景来解释：大学课程里，你要学“高等数学”才能学“线性代数”，要学“线性代数”才能学“概率论”，拓扑排序就是要找出一个不违反任何先修条件的选课顺序。

实现拓扑排序有两种方法，我在实际中更常用 Kahn 算法（基于入度）。它的步骤是：先统计每个节点的入度，把入度为 0 的节点全部入队，然后不断弹出队首节点 u，输出 u，同时把 u 的所有邻居 v 的入度减 1，如果 v 的入度变为 0，再把 v 入队。如果最终输出的节点数量等于 n，说明图中没有环；否则输出数量少于 n，说明存在环。

int indeg[MAXN]; queue<int> q; for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i); int cnt = 0; while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (int v : G[u]) { if (--indeg[v] == 0) q.push(v); } } // 如果 cnt < n，说明存在环

这里有一个细节容易被忽略：入度为 0 的节点可能一开始有多个，这时不同的弹出顺序会得到不同的拓扑序列，但只要题目没有额外要求，任意一个都合法。如果题目要求“字典序最小的拓扑序”，只需要把普通队列换成优先队列即可。

4.2 拓扑排序的实际应用：任务调度、编译依赖与课程安排

在实际工程项目里，拓扑排序的应用极为广泛。比如构建工具（Makefile、Gradle）需要根据文件依赖关系决定先编译哪些模块、再编译哪些模块；再比如在项目排期软件中，多个任务之间有严格的先后依赖关系，拓扑排序可以帮助自动生成一个可行的执行计划。当然，如果依赖图中出现了环，就意味着存在循环依赖，这时系统必须报警提示开发者检查设计。

在算法竞赛里，拓扑排序经常和其他知识点结合考。一种常见题型是“给定若干场比赛的胜负关系，求最终排名”，把胜者指向败者建图，然后拓扑排序即可。另一种是和动态规划结合：在 DAG 上求最长路径，因为 DAG 上不存在环，所以可以按拓扑序进行 DP，每个节点的状态只依赖于它的前驱节点。这比在普通图上做 DP 简单得多，因为普通图可能有环，DP 会陷入循环依赖。

4.3 拓排序排不出来的情况：检测 DAG 是否真的无环

如果题目给你的图不确定是不是 DAG，拓扑排序本身就是最好的检测手段。排完序后如果输出的节点数量小于 n，说明有环。但我提醒你，这个结论是“存在环”的充分必要条件，如果你的代码里有重边或者自环，要小心它们对入度的影响。自环会让节点入度永远无法归零，从而被“卡”在队列外，这实际上也是正确的——因为自环本身就是环。

我还遇到过一种情况，题目要求输出拓扑排序的每一步操作内容，这就要在循环里临时保存当前队列的所有元素，而不是一次性弹出。我记得在做课程设计“自动排课系统”时，用了拓扑排序生成一个基础开课顺序，然后结合每门课的学分进行加权排序，最后效果还不错。这种把算法应用在工程中的经验，比单纯刷题更能加深理解。

5. 最小生成树：Kruskal 与 Prim 的选型指南

5.1 最小生成树到底是什么：用最小代价连通所有节点

最小生成树（Minimum Spanning Tree, MST）解决的是这样一个问题：给定 n 个城市和一些可修建的道路以及各自的造价，请选择其中的 n-1 条道路把所有城市连通起来，使得总造价最小。注意，最小生成树不一定唯一，但所有最小生成树的总权重一定是相同的。

求解 MST 有两个经典算法：Kruskal 和 Prim。Kruskal 的核心思想是贪心选边：把所有边按权重从小到大排序，然后依次尝试把每条边加入生成树中，如果加入后不产生环，就保留（用并查集来判断）。这个算法优势在于实现简单，而且特别适合边稀疏的图。Prim 的核心思想是加点：维护一个已经加入生成树的节点集合，每次从连接集合内与集合外的所有边中，选一条权重最小的边，然后把该边连接的集合外节点加入集合。Prim 适合稠密图，但用朴素实现是 O(n²) 时比较简单，堆优化后是 O(m log n)，不过通常不如 Kruskal 好写。

我的个人建议是：默认写 Kruskal。因为并查集操作简单、容易调试，而且排序的时间复杂度 O(m log m) 在绝大多数题目中可以接受。只有 n 很大但 m 不太大且图特别稠密时，我才考虑朴素 Prim。

5.2 并查集在 Kruskal 中的核心作用：连通性判断

Kruskal 最核心的辅助数据结构是并查集。它支持两个操作：查找某个节点的根（以便判断两个节点是否在同一集合中），以及合并两个集合。我在写并查集时遵循两个优化原则：路径压缩（在 find 时把路过的节点直接挂到根上）和按秩合并（让较矮的树挂到较高的树上）。路径压缩几乎是必加的，代码只有一行：

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

这里有一个容易踩的坑：如果只使用路径压缩，不按秩合并，在极端情况下并查集的查询复杂度会升到 O(log n)，但大多数题目是可以通过的。不过为了求稳，我还是建议同时维护一个rank数组用于按秩合并。

5.3 最小生成树的题目变式：次小生成树与最大生成树

比赛里常见的变式有三个。第一个是“最小生成树是否唯一”：可以先求一次最小生成树，然后枚举树上边，看能不能找到一条非树边替换它且保持总权重不变。第二个是“次小生成树”：在最小生成树基础上，用一条非树边替代一条树边，使得总权重尽量小，但比最小生成树大。实现上需要维护树上任意两点之间的最大边权，可以用倍增 LCA 预处理，复杂度 O(m log n)。第三个是“最大生成树”：只需要把 Kruskal 中的排序改为从大到小排列即可。我在实际工程中遇到过“通信网络铺设光纤，要求使总造价最小”，这就是标准的最小生成树问题，直接套 Kruskal 就能解决。

6. 进阶实用技巧：强连通分量、二分图匹配与基环树

6.1 强连通分量：把复杂有向图压缩成 DAG

有向图中，如果两个顶点可以互相到达（即从 u 到 v 有路径且从 v 到 u 也有路径），就说它们在同一个强连通分量中。Tarjan 算法是求解强连通分量的经典方法，它基于 DFS 过程中维护时间戳和低链接值来实现。基本思路是：每个节点在 DFS 时有一个发现时间dfn[u]，同时维护一个low[u]表示该节点通过其子树中的边所能回溯到的最早时间点。当dfn[u] == low[u]时，说明 u 是其所在强连通分量的根，可以将栈中弹出直到 u 的所有节点合并成一个强连通分量。

为什么强连通分量很重要？因为它有一个超级有用的性质：把一个有向图的所有强连通分量分别缩成一个点之后，得到的图一定是一个 DAG。而 DAG 上很多问题变得非常简单（比如最长路径、拓扑排序）。我遇到过一个经典的题目叫做“传递闭包”或者叫“受欢迎的牛”：给定若干条“A 认为 B 很受认可”的有向关系，求被其他所有牛都认为受认可的牛的数量。这题的做法就是把图缩点后，在 DAG 上找“出度为 0”的唯一强连通分量。实用价值非常高。

6.2 二分图最大匹配：匈牙利算法的贪心回溯

二分图匹配问题的典型场景是“n 个职位、m 个求职者，每个求职者只能去某些特定职位，问能安排的职位数最多是多少”。匈牙利算法是求解二分图最大匹配的经典算法，它的核心思想可以用一句话概括：为左边每个节点尝试找一个右边节点匹配；如果右边节点已经被匹配，则尝试让已匹配的左边节点“换一个配对”。这个逻辑用递归实现非常简单：

bool dfs(int u) { for (int v : G[u]) { if (vis[v]) continue; vis[v] = true; if (match[v] == 0 || dfs(match[v])) { match[v] = u; return true; } } return false; } int hungarian() { int res = 0; for (int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); if (dfs(i)) res++; } return res; }

这里vis数组的作用是防止递归中重复访问同一个右边节点，每次尝试匹配一个新左侧节点时需要清空。这个算法最需要注意的地方是递归深度：如果匹配链过长，递归可能很深，虽然一般 n 不大不至于爆栈，但心里要有数。另外，二分图匹配不仅用于题目，在调度问题、任务分配、标注对齐等工程场景中都能用上。

6.3 基环树：树上多一条边之后怎么办

基环树（也称环套树）是指在一棵树上添加一条边形成的结构：图中正好有一个环，环上的每个节点可以长出一棵子树。处理基环树问题的经典思路是：先找到环，然后断开环上的每一条边，把问题转化为树上问题逐一解决。找环的方法可以借助拓扑排序：把所有叶子节点（度为 1）不断删除，剩下的节点就是环上的节点。

基环树在题目中并不少见，比如“骑士问题”“岛屿问题”，都是先找环再分类讨论。我在处理这类问题时，通常会在找环时把环上节点标记出来，然后分别以每个环节点为根对其子树做树形 DP，最后再对环上的决策枚举讨论一次。这种做法虽然代码量大，但思路清晰，基本不会出错。

6.4 竞赛实战中的图论模型：从题干中提取图的影子

在蓝桥杯、ACM 和 LeetCode 等刷题平台上，图论题目的核心难点往往是“怎么把现实问题抽象成图”。我给你总结一个快速建模的思路：看题干中是否存在“对象”和“关系”。如果存在，对象就是节点，关系就是边。然后看关系是否有方向（有向图还是无向图）、是否有权重（带权图还是无权图）、是否有约束条件（有环还是无环）。判断之后再来选择算法，是 BFS/DFS/H最短路径/拓扑还是 MST，思路就通了。

比如“找下一个身高更高的小朋友”这类题，其实可以抽象成单调栈问题，但如果你把它看成图上的依赖关系（每个人找右边第一个更高的），也可以用树的方向来理解。再比如“函数调用关系分析”可以建图后做拓扑排序，判断是否存在递归调用（环）。总之，把描述性语言翻译成图的节点与边的过程，是图论算法应用的关键一步。

7. 图论题目调试与避坑的九条心得

我刷图和做图相关应用题这几年，踩过的坑加起来可以写满一页纸。以下九条是我认为最重要、也最容易踩雷的心得，每条背后都是一段辛酸调试史。

第一，初始化数组别偷懒。全局变量在 C++ 中默认清零，但局部数组和 vector 不会自动清零。我曾经在一个函数内部定义了一个局部数组，忘了 memset 清零就直接用，结果 BFS 的访问标记错乱，查了一个多小时才发现。我自己调试时坚持一个原则：每个测试用例开始前，所有关键数组一律先初始化一遍。

第二，注意点编号从 0 开始还是从 1 开始。很多题目描述里顶点编号从 1 开始，但代码里数组长度开的是 n，导致访问G[n]越界。我的习惯是看输入样例第一行给的是什么，如果样例里出现顶点 0，那就一律按从 0 开始处理。

第三，多组输入的题目记得清理全局变量。如果你把图定义成全局的 vector，多组数据之间没有清空之前的数据，会导致上一次的边残留在当前图中。在循环内部使用G[i].clear()，或者在每组数据中新建局部 vector。

第四，Dijkstra 处理不了负权边，SPFA 可能被卡到超时。我遇到负权边时，先判断负环，没有负环再用 SPFA；如果题目数据量很大且没有负权，不管别人怎么说，直接堆优化 Dijkstra。

第五，BFS 求最短路径时，刚开始的入队点距离必须设置为 0。如果忘了设置起点距离，或者设置成 -1，第一次更新时dist[u] + 1会变成 0，导致结果错乱。

第六，DFS 递归过深导致栈溢出。当你遇到一张很深的链式图时，递归写法直接爆栈。换成显式栈模拟递归，或者思考是否能改用 BFS。C++ 在 Linux 下可以通过设置编译选项扩大栈空间，但不能总依赖这个。

第七，用邻接矩阵时注意 INF 的设置。如果你用memset把距离数组设为0x3f，那么两个 INF 加在一起就溢出了。建议用const int INF = 0x3f3f3f3f;，这样 INF + INF 在 int 范围内仍是一个很大的负数，但不会溢出到你意想不到的值。更稳妥的做法是在松弛和比较前先判断是不是 INF。

第八，并查集fa数组的初始化。并查集在 Kruskal 中充当核心工具，而fa[i] = i的初始化必须在读入所有边之前完成。我见过有人读边的时候顺手调用了 find 函数，结果 fa 全是 0，造成查找时无限递归。

第九，用long long存储大图的路径长度。图论的很多题目中边权之和很容易超过 int 范围（特别是 n 和 m 达到 10⁵ 时），我一直建议大图题目直接把距离存成long long，避免后期数据溢出再返工。

8. 从刷题到建模再到工程实战的综合建议

如果从零开始学图论算法，我建议按这样的路线推进：先花时间把图的三种存储方式彻底搞懂，每种都手写一遍，然后做 5 道 BFS 和 DFS 的水题，接着攻克最短路算法（先从朴素 Dijkstra 开始，再优化成堆版本，再学 Floyd），之后是拓扑排序和最小生成树，再往后是强连通分量和二分图匹配。每学一个算法，不要只背模板代码，一定要亲手调试带有变式的题目，比如“带打印路径的最短路”“求方案数的最短路”，否则真正开赛时会发现自己只会模板，稍微变个形就懵了。

工程实战又是另一套思路：引擎里加载路网数据需要建立图结构然后做最短路径查询，自动排课系统用拓扑排序安排课程依赖，社交网络的关系推荐用 BFS 计算六度分隔。这些场景除了算法本身，更看重数据结构的存储效率和内存占用。

在维护和扩展一个图算法模块时，我摸索出一个小经验：尽量把图的构建、遍历、最短路计算拆成独立函数，每个函数只负责一件明确的事情，出问题时按函数排查。尤其是大型项目里，把这个模块做成“输入图数据，输出结果”的黑盒，调用方根本不用关心内部怎么保存图，这能大幅降低模块间的耦合度。

图论算法最有魅力的地方就在这里，它表面上是一堆代码和定理，实际解决的是生活中形形色色的关系问题。只要你把“对象”和“关系”这两样东西想明白了，一个具体业务再怎么翻花样，背后的图模型都万变不离其宗。