企业官网建设流程全解析

图，是数据结构这门课里让不少人栽跟头的坎。前面我们聊完了数组、链表，又啃完了树和二叉树，靠着递归思想把一个又一个节点串起来，结果一遇到图，很多人的脑子就变成了一团乱麻。因为图太灵活了：节点之间谁跟谁连、边有没有方向、边上带不带权重，全都说不准。今天这篇是系列教程的3.7节，我专门把图的相关算法从头到尾捋一遍——怎么存图、怎么遍历、怎么求最短路径、怎么生成最小生成树、怎么处理有向无环图的拓扑关系，到最后刷题怎么练、Debug怎么查。目标读者是正在学数据结构、准备考研或算法面试的朋友，如果你已经会写DFS和BFS但没系统梳理过图论全家桶，这篇也能帮你把知识点串起来。

我不是按教科书的方式讲，而是站在一个刷过大量图论题目、在工程里也处理过图数据的人的角度，把那些真正用得上的套路和踩过的坑拿出来说。图算法不只是面试题，现实里的地图导航、任务调度、社交网络推荐，底层全是这些算法在跑。所以你只要把这篇啃完，后面看到任何图相关的题，基本都能找到下手点。

1. 先解决存储问题：图不是抽象的，是存的

很多人学图算法时犯的第一个错，就是跳过存储结构直接看算法。图本身是抽象的，但代码里必须把它具体地存下来，你的遍历和最短路径全都建立在存储方式之上。存法选错了，后面再好的算法也跑不出效率。

1.1 邻接矩阵：代码最直观，但别滥用

邻接矩阵就是用二维数组存图，graph[i][j]表示节点i和节点j之间是否有一条边，或者这条边的权重是多少。比如有向带权图，graph[i][j] = w就表示i到j有一条权值为w的边；如果没有边，用无穷大或者-1占位。

// 邻接矩阵，以n个节点的带权有向图为例 const int INF = 0x3f3f3f3f; // 代表无穷大，常用这个值防止加法溢出 vector<vector<int>> graph(n, vector<int>(n, INF)); // 添加一条从u到v、权值为w的边 void addEdge(int u, int v, int w) { graph[u][v] = w; } // 判断u和v之间有没有直接相连的边 bool hasEdge(int u, int v) { return graph[u][v] != INF; }

邻接矩阵最大的优点是写起来无脑，判断任意两个节点是否相连是O(1)的时间复杂度。但它的问题也很致命：空间复杂度是O(V²)，V是节点数。节点数一上5000，二维数组就有点吃不消了，上万直接内存爆炸。我在实际刷题中，遇到节点数超过2000的题，几乎不考虑邻接矩阵，不是因为写不出来，而是多余的空间浪费让人心里没底。

邻接矩阵还有一个好处是对稠密图很友好。什么叫稠密图？就是边数接近V²这种极限的图，比如一个朋友圈里人人互关的社交网络，每条关系都存进矩阵反而稠密而均匀，浪费不多。但现实中这种图很少，绝大多数图都是稀疏的，节点很多、每个节点的邻居没几个。

1.2 邻接表：刷题和工程的默认选择

邻接表的思路很朴素：对每个节点，只存它"真正的邻居"。常见的实现是数组套数组，或者用链表、vector嵌套。每个节点i维护一个列表，里面装着所有从i出发能直接到达的节点。

// 邻接表，带权的写法 vector<vector<pair<int, int>>> adj(n); // {目标节点, 边权} void addEdge(int u, int v, int w) { adj[u].push_back({v, w}); } // 遍历节点u的所有邻居 for (auto& [v, w] : adj[u]) { // v是邻居节点，w是u到v的边权 }

如果边不需要权重，vector<vector<int>>就够了。邻接表的好处是空间只跟边数相关，O(V+E)，对于稀疏图非常节省。刷题平台上的图论题，百分之九十以上都是稀疏图，邻接表天然就是默认选择。

还有一种更"比赛向"的存法叫链式前向星，本质是一个模拟链表的结构，用数组存边、用head数组记录每个节点的第一条边。这种方法比vector更省内存，因为vector本身有扩容的开销。当年我在写Blue Bridge Cup刷题的时候就经常用链式前向星，因为它对空间极限抠得比较死。不过现在刷LeetCode或者日常做工程，vector版本的邻接表已经完全够了，没必要自己造轮子。

1.3 存储方案的实战选择标准

我自己的选型逻辑很简单，总结下来就是三条：节点数少且图稠密，用邻接矩阵；节点多且稀疏，用邻接表；如果是算法面试场景，优先邻接表，万一题目变了想换存储也容易。

还有一个细节值得提：使用邻接表时，如果涉及删除边，vector删起来麻烦。这时候可以用set或者unordered_set替代内部列表，代价是空间更多、常数更大。工程里有动态删边的场景就需要这样做，刷题时极少遇到。

存储结构搞定后，你手里的"图"才有了具体的形状。接下来的遍历和所有算法，都是在这个形状上动手脚。

2. 遍历是地基：DFS和BFS必须手到擒来

图算法里面，遍历是最基础也是最高频的操作。最短路径要遍历、判断连通要遍历、拓扑排序也要遍历。可以说，DFS和BFS没练扎实，后面全是空中楼阁。我见过不少同学一上来就学Dijkstra，结果连最基础的遍历模板都写不利索，最后代码乱成一锅粥。

2.1 DFS：递归、栈、回溯的三角关系

DFS（深度优先搜索）的思想是：从一个节点出发，往一条路走到黑，走不动了再回头，换个方向继续走。代码实现上通常是递归，递归天然就带着栈的结构，系统休眠帮你压栈，你不需要自己管理栈。

// DFS遍历，用一个visited数组记录哪些节点已经访问过 vector<bool> visited(n, false); void dfs(int u) { visited[u] = true; // 在这里处理当前节点的业务逻辑，比如打印或计数 for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } }

这个模板极简，但藏着不少细节。visited必须在进入递归前就标记，而不是在递归开头再标记，否则可能重复遍历节点，极端情况下递归栈直接爆炸。我曾经在写一个迷宫变形的题时，因为visited标记位置放错，导致同一个节点被压入栈无数次，最后栈溢出。

再说回溯。回溯是DFS的一种策略，区别在于，回溯在退出某个节点时会"撤销"选择。比如求全排列、走迷宫找所有路径这种题目，节点可能会以不同路径多次访问，visited就不能全局固定，而是进入时标记、退出时取消。

void dfs(vector<int>& path, int u) { if (path.size() == targetSize) { // 找到一条可行路径，记录结果 return; } for (int v : adj[u]) { // 尝试选择v path.push_back(v); if (!visited[v]) { visited[v] = true; dfs(path, v); visited[v] = false; // 回溯关键 } path.pop_back(); } }

回溯的代价往往是指数级的，所以很多题目需要"剪枝"。剪枝就是提前判断这条路走下去不可能有解，直接跳过。比如搜索路径时发现当前长度已经超过最优解，就不再往下递归。我在刷暴力枚举类题目时，剪枝用得好不好，直接决定代码是超时还是秒过。

2.2 BFS：队列与"层次"的力量

BFS（广度优先搜索）跟DFS完全是两种遍历节奏。它从起点开始，先访问所有距离为1的节点，再访问所有距离为2的节点，一层一层往外扩。实现上靠队列，天然适合求最短路径、最少步数这类问题，因为BFS搜到某个节点的第一遍，就是从起点到它的最短步数（在所有边权为1的前提下）。

// BFS模板，从start出发 queue<int> q; vector<bool> visited(n, false); q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); // 在这里处理当前节点 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } }

BFS有一个极易忽略的细节：节点在入队那一刻就要标记visited，而不是出队时标记。否则队列里会塞进大量重复节点。我自己犯过这个错误，在一个网格图最短路径题里，出队才标记，结果队列膨胀到几万节点，程序卡成了PPT。

如果BFS要记录路径长度，可以多存一个dist数组，并且用多层循环来控制"每一层"的边界。还有一种常见做法是队列里存pair，一个节点一个步数，代码写起来更直观。

queue<pair<int, int>> q; // {节点, 步数} q.push({start, 0}); vector<bool> visited(n, false); visited[start] = true; while (!q.empty()) { auto [u, dist] = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push({v, dist + 1}); } } }

2.3 遍历题目的现场经验

掌握DFS和BFS的模板后，你在图论题里就站住脚了。但要提醒一句：很多题目外表看起来是数组题，实际是图题。比如岛屿数量问题，它给的是二维网格，每个格子就是图的一个节点，相邻接的格子之间就是边。这时候DFS和BFS都能做，区别只是遍历的写法。

我自己刷题时的偏好是：求连通性、求所有路径、做回溯时用DFS；求最短步数、求最小层数、求扩散效果时用BFS。DFS代码短，BFS逻辑直白。遇到二维网格类的图，建议直接上手画一画，把网格坐标映射成节点编号，思路会清晰很多。

小技巧：二维网格的DFS/BFS中，常用四个方向数组dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}，遍历四个方向相当于枚举当前节点的四个邻居。这个写法非常常见，建议直接背下来。

3. 最短路径：图论里考得最多的那一块

如果说遍历是图算法的基础，那最短路径就是图算法真正的重头戏。地图导航、网络路由、航班调度，到处都在用最短路径算法。面试中对这部分考察频率极高，我把它拆成几个算法逐个讲。

3.1 Dijkstra：贪心在正权图上的胜利

Dijkstra算法解决的是"单源最短路径"问题——给定一个起点，求它到所有其他节点的最短路径长度。它只适用于边权全部非负的图。

它的核心思路很像是"扩散式"的贪心：维护一个dist数组，dist[i]表示从起点到i的当前已知最短距离。一开始除了起点本身dist为0，其他都是无穷大。然后不断取出当前距离最小且没确定最短路的节点，用它去更新邻居的距离。这个"取出当前距离最小的节点"的操作，就是贪心的体现。

// 堆优化Dijkstra模板 const int INF = 0x3f3f3f3f; vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> dist(n, INF); dist[start] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.push({0, start}); 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}); } } } return dist; }

这里的if (d > dist[u]) continue;非常关键。因为优先队列里同一个节点可能被多次压入，取出来发现是旧数据就直接跳过。我见过很多新手不写这个判断，结果算法虽然正确但会多做很多无用的松弛，效率大打折扣。堆优化后的Dijkstra时间复杂度是O((V+E)logV)，在稀疏图上跑得非常快。

Dijkstra的局限也很明显：只要出现负权边，贪心前提就崩了。正权图里，当前距离最小的节点以后不可能被更新出更小的距离；但有负权边时，一个暂时距离大的节点可能通过负边变近。所以遇到负权图，一定要换思路。

3.2 负权边怎么处理：SPFA与Bellman-Ford

如果图中存在负权边，甚至存在负权回路，Dijkstra就彻底失效了。这时候要用Bellman-Ford或者它的优化版SPFA。

Bellman-Ford的思路是：对所有边做V-1轮松弛。每一轮，都尝试用当前已知的最短距离去更新每个节点。因为一条最短路径最多经过V-1条边，所以V-1轮后一定能得到答案。如果第V轮还能松弛，说明存在负权回路。

SPFA是对Bellman-Ford的队列优化。它不是傻傻地把所有边扫V-1遍，而是只把"距离被更新过、可能影响别人"的节点放进队列，反复拿出来松弛。

// SPFA模板 vector<int> spfa(int start, vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> dist(n, INF); vector<bool> inQueue(n, false); queue<int> q; dist[start] = 0; q.push(start); inQueue[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for (auto& [v, w] : adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!inQueue[v]) { q.push(v); inQueue[v] = true; } } } } return dist; }

SPFA的代码比Dijkstra还好写，但它的复杂度不稳定，最坏情况下会退化到O(VE)。面试或比赛里，如果图中没有负权边，我更推荐Dijkstra而不是SPFA，因为Dijkstra的复杂度是稳定有保障的。SPFA只有在确实存在负权边、又不需要判负环时才值得用。

3.3 Floyd：多源最短路径的"暴力美学"

Dijkstra和SPFA都是单源算法，问的是"从某个起点出发到所有点的距离"。如果题目要的是"任意两点之间的最短距离"，那直接上Floyd算法最简单。

Floyd的核心是一个三层循环，不断尝试用中间节点k来松弛i到j的距离：如果i经过k再到j比原来i直接到j更短，就更新。

// Floyd算法，二维dist[i][j]初始化为i到j的直接距离 vector<vector<int>> dist(n, vector<int>(n, INF)); for (int i = 0; i < n; i++) dist[i][i] = 0; for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][k] != INF && dist[k][j] != INF) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } }

这段代码短到不可思议，但背后的原理值得琢磨。k循环在最外层，它保证了递推的正确性：当外层循环到k时，内层用到的dist[i][k]和dist[k][j]都已经是"只经过编号不超过k的中间节点"的最短路径了。这是典型的动态规划思路。

Floyd的时间复杂度是O(V³)，空间O(V²)，所以只适合节点数几百以内的小图。不过它的优点是实现简单、不易写错，很多需要求全源最短路的题目，直接Floyd一把梭。我记得有个多源最短路+枚举的题，用Floyd十几行就写完了，换成反复调Dijkstra反而麻烦。

3.4 最短路径算法怎么选

为了让你一眼看明白这几个算法的区别，我整理了一个对比表，都是我实际使用中总结出来的选型标准。

我在实际刷题中，如果是单源最短路径，没有负权边，百分之九十的情况直接写Dijkstra；如果题目明确说可能负权边，就写SPFA或Bellman-Ford；如果题目问任意两点距离，先看节点数，少于300就直接Floyd，超过300再考虑多跑几次Dijkstra。

这里有一个预防针要打：判断负权边时，别把题目中"距离为负数"当成必然错误。负数只是边的权重，不是逻辑错误。真正的禁忌是负权回路——如果有负权回路，最短路不存在，因为你可以绕圈绕到负无穷。Bellman-Ford第V轮还能松弛就说明存在负环，这时候要果断输出不可达或者报错。

4. 最小生成树：联通所有节点的最省钱方案

最短路径讨论的是"两点之间怎么走最近"，而最小生成树讨论的是另一个问题：如果一张图的所有节点都必须连通，怎么选边使得总边权最小？这个"选出的边"刚好构成一棵树，叫最小生成树（MST）。它在网络布线、电路设计、公路规划里都有实际应用场景。

4.1 Prim算法：从一个点慢慢长大

Prim算法的思路很像"局部扩张"：从任意一个节点开始，不断把距离当前生成树最近的节点加入树中，直到所有节点都被覆盖。

实现上需要维护两个数组：一个记录某节点是否已经进入生成树，另一个记录它到当前生成树的最短距离。每次找出"不在树中且距离最小"的节点，加入树，然后用它的所有边去更新别的节点的距离。

// Prim算法（朴素版） const int INF = 0x3f3f3f3f; int prim(vector<vector<pair<int, int>>>& adj) { int n = adj.size(); vector<int> key(n, INF); // 到生成树的最短距离 vector<bool> inMST(n, false); key[0] = 0; int result = 0; for (int cnt = 0; cnt < n; cnt++) { // 找不在树中且key值最小的节点 int u = -1, minKey = INF; for (int i = 0; i < n; i++) { if (!inMST[i] && key[i] < minKey) { minKey = key[i]; u = i; } } if (u == -1) return -1; // 图不连通 inMST[u] = true; result += minKey; // 用u更新邻居的key值 for (auto& [v, w] : adj[u]) { if (!inMST[v] && w < key[v]) { key[v] = w; } } } return result; }

朴素版Prim的复杂度是O(V²)，不用堆优化，因为它在稠密图上反而有优势。当然也可以用优先队列优化到O(ElogV)，但代码会复杂不少。我在刷题时，只有当题目明确给的是稠密图时才写Prim，否则更倾向Kruskal。

4.2 Kruskal算法：并查集+排序的组合拳

Kruskal的思路非常朴素：把所有边按权重从小到大排序，然后从最小的边开始一条条尝试加入。如果加入这条边后不形成环，就保留；如果形成环，就丢弃。最终留下的边就是最小生成树。

"判断是否形成环"这一步用并查集（Union-Find）来搞定。并查集核心就两个操作：查某个节点属于哪个集合，合并两个集合。如果一条边的两个端点已经在同一个集合里，说明它们早就连通了，这条边再加进去就成环了。

// Kruskal模板 struct Edge { int u, v, w; bool operator<(const Edge& other) const { return w < other.w; } }; vector<int> parent; int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩 return parent[x]; } bool unionSets(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return false; parent[ra] = rb; return true; } int kruskal(vector<Edge>& edges, int n) { sort(edges.begin(), edges.end()); parent.resize(n); for (int i = 0; i < n; i++) parent[i] = i; int result = 0, edgeCount = 0; for (auto& e : edges) { if (unionSets(e.u, e.v)) { result += e.w; edgeCount++; if (edgeCount == n - 1) break; // 已经形成生成树 } } if (edgeCount != n - 1) return -1; // 图不连通 return result; }

Kruskal算法的复杂度主要是排序，O(ElogE)。它的优势是写起来不需要维护复杂的邻接结构，把边存下来排序即可。实际操作中，很多题目给的边数不多，Kruskal跑起来又快又稳。

4.3 什么时候用Prim，什么时候用Kruskal

我这里的取舍标准很直接：稀疏图用Kruskal，稠密图用Prim。稀疏图的边数少，排序的开销小，Kruskal天然适合；稠密图的边数接近V²，排序开销大，Prim的O(V²)反而更快。

还要提一句连通性问题。两个算法在返回结果前都要判断一下最终生成树里的边数是不是V-1，如果不是，说明原图不连通，不存在最小生成树。这个问题很多人忽略，结果遇到非连通图就莫名其妙报了错。

最小生成树里还有一个衍生考法叫"次小生成树"，就是除了最小的那棵，第二小的生成树。它的做法通常是先求MST，再枚举不在MST里的边加进来形成环，删掉环上最大的边，取最优。这种升级题在竞赛里很常见，面试中出现频率倒不高。

5. 有向无环图的玩法：拓扑排序与关键路径

有向无环图，缩写叫DAG，是图论里一类特殊的图。这种图没有环，天然适合描述依赖关系。比如课程之间的先修关系、项目任务的执行顺序、编译器的依赖解析，全都是DAG。处理DAG的两个核心问题就是拓扑排序和关键路径。

5.1 拓扑排序：依赖关系的线性化

拓扑排序要做的事情是：把DAG的节点排成一个线性序列，使得每条边的起点都在终点前面。如果有环，就不存在拓扑排序。所以拓扑排序也常用来判断有向图有没有环。

Kahn算法是最容易实现的方案，思路像"剥洋葱"：先把所有入度为0的节点入队，这些节点没有任何依赖，可以先处理。出队一个节点，就把它指向的所有节点的入度减1，如果某个节点的入度变成0，就把它入队。最终如果出队的节点数等于节点总数，说明拓扑排序成功；否则说明图里有环。

// Kahn算法求拓扑排序 vector<int> topologicalSort(vector<vector<int>>& adj, vector<int>& indegree) { int n = adj.size(); queue<int> q; vector<int> result; for (int i = 0; i < n; i++) { if (indegree[i] == 0) q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); result.push_back(u); for (int v : adj[u]) { indegree[v]--; if (indegree[v] == 0) q.push(v); } } if (result.size() != n) return {}; // 存在环 return result; }

注意，拓扑排序的结果不一定唯一。如果希望输出字典序最小的拓扑排序，把队列换成优先队列即可。这个细节在一些要求输出特定顺序的题目里会用到。

我印象很深的一道题是"课程表"系列，给定课程数量和先修关系，问能不能修完全部课程。乍一看是逻辑题，实际上就是在问有向图里有没有环。用Kahn算法统计能完成拓扑排序的节点数，一比对就出答案了。

5.2 关键路径：AOE网里的最长路径问题

拓扑排序只是把依赖关系理清，而关键路径问题是更进一步：如果每个活动（边）都有持续时间和前置依赖，整个项目从开始到结束的最短时间是多少？哪些活动不能拖延，一拖延整个项目就延期？

这里用到的是AOE网，边表示活动，节点表示事件。关键路径就是从源点到汇点的最长路径，路径上的活动叫关键活动。为什么是最长路径？因为一个项目的总工期取决于所有并行活动中耗时最长的链，其他路径跑得再快也得等这条最慢的链走完。

求关键路径最常用的方法是先做拓扑排序，再用动态规划求最早发生时间。一个节点v的最早发生时间是它所有前驱节点的"最早发生时间+边权"的最大值。

// 求最早开始时间（配合拓扑排序结果使用） vector<int> earliest(n, 0); for (int u : topoOrder) { for (auto& [v, w] : adj[u]) { earliest[v] = max(earliest[v], earliest[u] + w); } }

关键路径问题在数据结构课本里看挺复杂，但实际上会拓扑排序就能上手。它的问题是代码比较长，要同时维护最早和最晚时间，还要判断哪些边是"最早=最晚"的关键活动。面试中直接考关键路径的频率远低于拓扑排序，但一旦考到，就是拉开差距的题。

我在实际处理异步任务编排时，也用过类似的思路：把每个服务调用当成一个节点，调用延迟当边权，算出一条链路中最耗时的部分，再针对性地做优化。图算法的思想用在实际系统里，就是这么直白。

6. 刷题经验、常见错误与Debug实录

图算法的理论部分讲完了，最后分享点真正让我"从会写到熟练"的经验。这部分内容不是哪本教科书里有的，全是我刷题和带人过程中积累出来的。

6.1 图算法通用的"三板斧"

无论什么图算法题，我拿到手都会先做三件事。第一，明确图的类型：有向还是无向，带权还是无权，有没有负权边，有没有环。第二，确定存储结构：节点数和边数的关系，稀疏还是稠密。第三，把问题的本质映射到经典算法上：是求最短路，还是求连通块，还是判断环。

这三板斧看起来简单，但能解决大半问题。很多人一上来就写代码，结果写到一半发现存储不对、算法不对，全部推翻重来。我更建议先用两分钟在草稿纸上画图、标数据，把问题从文字描述变成图的结构，再动手写。

6.2 我踩过的高频坑与排查方法

第一个高频坑是数组越界。图论题里节点的编号经常是1到n，而不是0到n-1。如果你用0到n-1建数组，输入的数据却是从1开始，访问邻接表时必然越界。我的做法是统一在下标上做偏移：读入节点号后减1再存，或者干脆把数组长度开成n+1，下标从1开始用。

第二个高频坑是visited标记时机不对。前面提到过，BFS必须在入队时标记，DFS必须在进入递归时标记。延迟标记的后果轻则重复计算，重则栈溢出。排查这一步时，最简单的办法是在visited赋值的代码行打一个断点，跑一个简单的小图，看看每个节点是不是只被访问了一次。

第三个坑是INF值设置不当。很多图论题用0x3f3f3f3f作为无穷大，为什么选这个值？因为它大约等于10亿，比一般答案大得多，而且两个0x3f3f3f3f相加是0x7e7e7e7e，也就是约21亿，还在int范围内，不会溢出成负数。如果你用INT_MAX当无穷大，两个无穷大相加直接溢出成负值，dist数组就会变成负的，整个算法直接崩掉。这个坑我见过好多次，特别隐蔽。

第四个坑是重边和自环。题目没说没有重边的时候，存图必须考虑多重边。比如邻接矩阵存重边时，要取最小值；邻接表存重边时，Dijkstra和SPFA会自动取最优解，不受影响。自环在一些算法里影响不大，但在判断环、拓扑排序时要特别注意。

我Debug图论题的习惯是：先用小规模数据手算，再用代码输出中间状态。比如Dijkstra每轮弹出的节点和dist值都打印出来，跟手算结果对照，很容易发现问题在哪个环节。

6.3 刷题顺序与进一步扩展

如果你准备系统地练图算法，我的建议不是按教科书顺序刷，而是按"高频到低频"刷。最优先的是图的遍历类题目，然后是Dijkstra和拓扑排序，接着是最小生成树，再然后是Floyd和SPFA。遍历类题目建议刷至少10道，直到闭着眼能写出来。

更进一步的扩展方向包括：二分图的匈牙利算法（最大匹配）、强连通分量的Tarjan算法、网络流最大流、二分答案+图论验证。这些属于进阶内容，不在3.7节的基础范围内，但如果你在图论这条路上走得深，迟早会碰到。

最后分享一个我常用的学习技巧：每次做完一道图论题，在题解旁边写一句"这题本质上考的是XXX"。比如一道题本质是"BFS求无权图最短路+状态压缩"，另一道题本质是"Dijkstra+枚举答案"。这样积累一段时间后，你看到新题就能快速归类，解法自然就出来了。

我个人带新人时发现一个规律：图论学得好的人，不是记的模板多，而是对每一种算法的"适用边界"特别敏感。他们知道什么时候该用DFS、什么时候该用Dijkstra、什么时候该换SPFA，这种判断力完全靠刷题和复盘堆出来。你现在看这篇文章花了半小时，真正把这些算法变成本能，还需要你亲手写完这十道题。动手吧。