从存储到遍历再到最短路径：十天吃透图算法核心

1. 为什么要把十天押在“图”这个硬骨头上日撸代码这件事坚持到第30天的时候我心里其实是有落差的。前面线性表、树玩得再溜遇到真正的复杂问题总感觉手上缺一张地图。尤其是在LeetCode刷到一些中等难度的题比如拓扑排序、连通分量、最短路径一看题解就懂一关掉页面自己写就卡壳。问题不在于某个具体算法记没记住而在于我对“图”这个东西本身缺乏一种肌肉记忆——图该怎么存、怎么遍历、怎么在不同的场景里换着花样用对我来说始终隔着一层。所以第31天开始之前我给自己定了一个很具体的目标用十天时间把图这块系统地啃一遍。这里说的“系统”不是把教材上的定义抄一遍而是从最基础的存储结构开始到遍历、拓扑排序、最小生成树、最短路径、强连通分量每一块都亲手实现一遍再用真实场景里的问题去做验证。之所以说它是硬骨头是因为图跟前几章的内容有本质区别。数组、链表、树本质上都还是“线性分层的结构”你脑子里始终能画出一个相对规则的形状。但图不一样它允许任意两个节点之间有连接而且连接可以带方向、带权重甚至可以存在环。这种自由度带来的第一个冲击就是你不再能用一种“默认顺序”去处理数据了必须在设计之初就想清楚数据结构和算法之间的配合。这个阶段我选择的任务清单是这样的第31天图的存储结构——邻接矩阵和邻接表的完整实现第32天DFS深度优先遍历以及基于递归和显式栈两种写法第33天BFS广度优先遍历配合最短路径的朴素理解第34天拓扑排序用Kahn算法实现同时讲清楚为什么有环就没法排第35天最小生成树之Prim算法第36天最小生成树之Kruskal算法顺带重造一遍并查集第37天Dijkstra最短路径先写朴素版再上堆优化第38天Floyd多源最短路径理解动态规划在图上是怎么跑的第39天Tarjan算法强连通分量的判定与缩点第40天综合实战用LeetCode和实际场景把前九天串起来下面我把每一天最核心的收获和踩过的坑原原本本写出来尤其是那些看教材根本看不出来的选择逻辑。2. 图的存储邻接矩阵和邻接表到底该选谁很多人学图的时候第一个碰到的问题不是遍历也不会是路径算法而是根本不知道图应该用什么结构存进计算机。我见过不少初学者兴致勃勃开始写Dijkstra结果卡在“怎么把一个图输入到程序里”这一步半天没进展。存储搞不定后面全是空中楼阁。2.1 邻接矩阵的实现与适用边界邻接矩阵的思路非常直接如果图里有N个顶点就开一个N乘N的二维数组matrix[i][j]表示顶点i到顶点j有没有边。无向图是对称的有向图不需要对称有权图存权值无权图存1或0。// 邻接矩阵的C实现骨架 #define MAXN 1000 int graph[MAXN][MAXN]; // 默认全0 int n, m; // n个顶点m条边 void addEdge(int u, int v, int w) { graph[u][v] w; // 有向图 // graph[v][u] w; // 无向图加上这一行 }这段代码写起来确实爽查任意两点之间有没有边时间复杂度O(1)一句话的事。但它的代价也摆在那里空间复杂度O(N^2)。如果图里有1万个顶点光矩阵本身就要用掉100万乘以4字节差不多400MB内存这在大部分OJ和工程场景里是直接爆掉的节奏。所以邻接矩阵真正的适用场景是稠密图——顶点不多但边特别多多到接近N^2级别。我的判断标准很简单顶点数在1000以下且边数超过N^2/4优先考虑邻接矩阵涉及Flyod这类需要频繁访问任意两点间距离的算法邻接矩阵是命根子图以稀疏为主老老实实上邻接表2.2 邻接表与链式前向星工程里到底怎么写邻接表的思路是用一个“每个顶点挂一条链表”的方式只存实际存在的边。在C里最舒服的写法是用vectorint adj[MAXN]一条边就是一个整数简单直接。但如果要处理带权图并且代码要跑出高性能我强烈建议掌握一种叫做链式前向星的写法。第一次看到这个名字的人可能会被吓到其实它就是一个数组模拟的邻接表用数组下标代替指针避免动态分配内存带来的开销。const int MAXN 10005; const int MAXM 200005; // 注意无向图要开两倍 struct Edge { int to, w, next; // 终点、边权、下一条相同起点的边的编号 } edges[MAXM]; int head[MAXN], ecnt 0; void init() { memset(head, -1, sizeof(head)); ecnt 0; } void addEdge(int u, int v, int w) { edges[ecnt].to v; edges[ecnt].w w; edges[ecnt].next head[u]; head[u] ecnt; }遍历顶点u的所有邻居时写法长这样for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; // 这里拿到了u的一个邻接点v权重是edges[e].w }这里有个很关键的细节addEdge里新边是插在链表头部的所以遍历顺序和插入顺序相反。这个特性在做某些需要倒序处理的图论题时反而是优势但如果你依赖遍历顺序就需要注意。链式前向星最大的优点就是省空间且高效。N个顶点、M条边的有向图只需要两个长度为N的数组加一个长度为M的结构体数组完全不用管动态内存。对于我这种习惯用C语言刷OJ的人来说这套写法能应付绝大多数题目。还有一个补充方案是直接用vectorpairint,int adj[MAXN]存带权图第二个int表示边权。工程上写起来快、可读性好只是性能稍微逊色一点点。我个人在代码诊断插件和CLI工具这种“图数据没那么大”的场景里就常用的vector版本一到算法竞赛或性能敏感的处理任务就切回链式前向星。2.3 存储结构选错引发的典型事故第31天我做自测的时候用邻接矩阵存了一个2万个顶点的稀疏图程序一运行直接卡死内存报了OOM。那个瞬间我才真正体会到什么叫“图算法的瓶颈往往不在算法本身而在数据结构的修为上”。从那以后我每开始一个图相关的任务第一件事就是估算顶点数和边数把这两个数字乘以对应的存储开销算一遍再决定用哪种结构。先定存储再谈算法这是一条铁律。3. DFS和BFS不只是遍历它们决定了后面所有算法的手感遍历是图算法的基础操作但它的重要性往往被低估。实际上拓扑排序基于DFS的变形Dijkstra本质是BFS的加权版本判断二分图、找环、求连通分量全都离不开这两种遍历能力。3.1 递归版DFS与显式栈版DFSDFS的思路是“一条路走到黑走不动了再回头”。递归写法是最好理解的const int MAXN 10005; vectorint adj[MAXN]; bool visited[MAXN]; void dfs(int u) { visited[u] true; // 处理当前节点 for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } }递归写法简洁但它有一个隐藏的雷当图的深度比较大时函数调用栈会飞快增长。默认栈空间在Windows下大约是1MB在Linux下通常是8MB如果遇到一条链状的图动辄几万层递归直接栈溢出。我第32天用递归DFS跑一个深度为10万的长链图程序当场崩溃报Segmentation fault。这种情况必须改用显式栈。void dfsIterative(int start) { stackint 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); } } } }请注意显式栈版的顺序和递归版不一样。递归版在深入一个分支时先处理完再回退显式栈因为后进先出实际遍历顺序取决于邻居的入栈顺序。如果题目的结果依赖遍历顺序就需要好好设计入栈次序。很多人在这个阶段开始混淆DFS和BFS就是因为控制结构变了导致行为变了。3.2 BFS队列、层数与最短路径的直觉BFS用队列实现天然按照“离源点近的先访问”这个顺序推进。void bfs(int start) { queueint q; vectorint dist(MAXN, -1); dist[start] 0; q.push(start); 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数组就是无权图中从start出发到每个点的最短路径长度。BFS之所以能求最短是因为队列按层级扩展第一次到达某个点时必然经过最少条数的边。我在代码诊断插件里做过一个非常有意思的实践把项目文件之间的依赖关系建模成一个图用BFS计算“某个文件改动后影响范围有多大”。从被改的文件出发逐层扩散把受影响的模块按距离分层列出然后按照依赖深度安排回归测试优先级。这个应用本质上就是在无权图上运行BFS代码量不超过50行。3.3 实战中容易被忽略的访问标记问题写遍历代码时最常见的bug不是递归写错而是访问标记的位置放错了。对BFS来说正确的做法是入队时就标记visited[v] true而不是出队时再标记。原因很简单如果出队时才标记同一个节点可能被多个父节点同时入队多次造成大量重复计算甚至在极端情况下导致队列膨胀到内存爆炸。我亲眼见过一个新手用Python写BFS因为标记放错位置导致同一个节点被入队了几十万次跑一个200个节点的图都要好几秒。对DFS来说递归调用的前一行标记是常规操作但如果你需要记录“递归路径上的节点”而不是“所有访问过的节点”就得用另一个数组来模拟路径栈并且在递归返回时清除标记。这个技术在判断有向图是否有环、求欧拉路径时尤为重要。3.4 遍历思想如何移植到“图神经网络”和“图计算”的直觉里这里说一个很多人没意识到的点你今天在算法题里磨的DFS/BFS实际上就是图神经网络里消息传递机制的雏形。图神经网络里每个节点要聚合邻居的特征本质上就是一层BFS——从目标节点出发向邻居搜集信息更新自己的状态。多层的GNN就是多轮BFS扩展只是每轮迭代还会做特征变换。明白了这个联系以后再接触图计算、图神经网络这些偏研究的领域你至少不会觉得完全陌生。我在更新技术博客的时候经常用这个类比帮读者打通“经典算法”和“现代方向”之间的障碍。4. 拓扑排序依赖关系的破局者从任务调度到构建系统都在用它拓扑排序解决的问题很朴素有一堆任务部分任务必须在另一些任务完成之后才能开始请你给出一个合法的执行顺序。如果建模成图每个任务是一个节点A必须在B之前就画一条从A指向B的边。拓扑排序要做的就是找出一个满足所有边方向的线性序列。4.1 Kahn算法不用递归直观且好写Kahn算法的核心是逐步删除入度为0的节点统计每个节点的入度把所有入度为0的节点放进队列队首出队把它加入结果序列然后“删掉”它的所有出边——体现在入度更新上就是邻居节点的入度减1如果某个邻居入度降到0就把它也加入队列重复直到队列为空vectorint topoSort(int n) { vectorint indegree(n, 0); for (int u 0; u n; u) { for (int v : adj[u]) { indegree[v]; } } queueint q; for (int i 0; i n; i) { if (indegree[i] 0) q.push(i); } vectorint result; 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 result; }这段代码最后那个if非常关键。如果结果长度不等于顶点总数说明有节点永远无法入队。为什么因为它们被环挡住了环上每个节点的入度至少为1永远不可能降到0。所以拓扑排序的副产品就是环检测这一点在实际工作中价值极高。4.2 课程表、编译依赖与Makefile拓扑排序的三个真实场景第一课程表问题。LeetCode 207和210就是典型的拓扑排序题。输入是课程的选修关系输出要么是能否学完要么是具体的学习顺序。用Kahn写一遍之后我对这类题基本形成条件反射。第二编译器依赖。我在做一个代码诊断相关的功能时需要分析头文件的包含关系找出来哪些头文件存在循环包含。这个场景本质上就是在一个“头文件依赖图”上做环检测拓扑排序一次搞定。之前有人直接用正则去匹配include语句费劲不说还容易漏掉条件编译产生的路径而用图建模就优雅得多。第三Makefile和构建系统。构建工具计算构建顺序用的就是依赖图的拓扑排序。你改了一个底层的.c文件构建系统要决定哪些上层文件需要重新编译背后的算法逻辑跟这里写的Kahn几乎一模一样。只是工业级构建系统还加入了时间戳判断、并行调度等细节但核心思想没变。4.3 拓扑排序的字典序变体什么时候需要优先队列Kahn算法的队列换成优先队列就可以在入度为0的多个节点中优先选择“编号最小”或“字典序最小”的那个。这个技巧在要求输出字典序最小的拓扑序列时非常管用。LeetCode 210的进阶版有时候就会用这个思路。实现上只需要把queueint换成priority_queueint, vectorint, greaterint其他逻辑完全不变。我在准备面试的时候总结过一个判断标准只要题目里有“字典序”“编号最小”“按顺序”这类字眼就要立刻想到优先队列版本。5. 最小生成树Prim和Kruskal分别什么时候用最小生成树解决的问题是给定一个带权无向图选择若干条边把所有点连通并让边的总权值最小。这个问题的应用极广比如设计成本最低的通信网络、铺设电缆、规划交通路线等。两条经典算法路径分别是Prim和Kruskal它们看上去都能求出答案但思考方式完全不同。5.1 Prim像BFS一样“长”出树来Prim的出发点是“一个点一个点往外扩展”。初始时选定一个起点把它加入生成树集合然后不断在与树相连的边里选一条权值最小的把这条边连到的新点也加入树集合重复直到所有点进树。朴素版每次找最小值要遍历所有点复杂度O(N^2)适合稠密图。优化版用优先队列维护“连接树内和树外”的边可以把复杂度降到O((NM)logN)但要注意防止出现“树内到树内”的冗余边。int prim(int start) { priority_queuepairint,int, vectorpairint,int, greater pq; vectorint key(n, INF); vectorbool inMST(n, false); key[start] 0; pq.push({0, start}); int total 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (inMST[u]) continue; inMST[u] true; total d; for (auto [v, w] : adj[u]) { if (!inMST[v] w key[v]) { key[v] w; pq.push({w, v}); } } } return total; }这个逻辑和Dijkstra长得很像唯一的区别是Dijkstra的key记录的是“到源点的距离”Prim的key记录的是“到当前生成树集合的最短边”。两段代码放一起对比着记是我觉得最有效率的学习方法。5.2 Kruskal边排序加并查集简单粗暴但优雅Kruskal的思路反过来不看点只看边。把所有边按权值从小到大排序从最小的开始尝试加入。加入一条边时用并查集判断它的两个端点是否已经连通如果没连通就加入这条边并合并两个集合否则跳过。直到所有点都在同一个集合中。struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; vectorEdge edges; // 并查集核心find和union int find(int x) { return parent[x] x ? x : (parent[x] find(parent[x])); } void unionSet(int a, int b) { a find(a); b find(b); if (a ! b) parent[a] b; } int kruskal() { sort(edges.begin(), edges.end()); for (int i 0; i n; i) parent[i] i; int total 0, cnt 0; for (auto e : edges) { if (find(e.u) ! find(e.v)) { unionSet(e.u, e.v); total e.w; cnt; if (cnt n - 1) break; // 已经形成最小生成树 } } return total; }Kruskal的时间主要花在排序上整体复杂度O(M log M)适合边稀疏的图。相比之下Prim更适合稠密图。我在实际项目中的经验是大部分真实网络比如社交关系、城市路网、代码依赖图都非常稀疏Kruskal在这种场景下通常更顺手。5.3 并查集路径压缩与按秩合并的实战意义写Kruskal绕不开并查集。这里最值得投资的是把find写对。路径压缩的核心是递归回溯时把路径上的节点直接指向根节点。如果只写循环版本而漏掉压缩并查集在多次查找后会退化成长链复杂度上升到O(N)整个Kruskal会被拖垮。我习惯用递归写法加路径压缩再配上按秩合并int parent[MAXN], rankArr[MAXN]; void init(int n) { for (int i 0; i n; i) { parent[i] i; rankArr[i] 0; } } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void unionSet(int a, int b) { a find(a); b find(b); if (a ! b) { if (rankArr[a] rankArr[b]) swap(a, b); parent[b] a; if (rankArr[a] rankArr[b]) rankArr[a]; } }按秩合并的思路是让“矮的树”挂到“高的树”下面从而控制树的高度。只用路径压缩的并查集平均复杂度已经是O(alpha(N))级别加上按秩合并后理论更稳。虽然实际性能差距对大样例没那么明显但工程上写完整版本的习惯值得养成。6. 最短路径Dijkstra和Floyd复杂度不是一个量级最短路径是图算法里应用最广的一类问题。地图导航是它网络路由是它游戏中的路径搜索也是它。根据图的规模和类型我会在Dijkstra和Floyd之间做选择偶尔还要考虑SPFA或Bellman-Ford。6.1 为什么Dijkstra不能处理负权边Dijkstra的核心逻辑是贪心每次从“未确定最短路的点”里选出距离最小的那个认定它的最短路已经确定然后松弛它的所有出边。这个逻辑建立在“所有边权非负”的前提下既然边权不是负数已经选出的最小距离点就不会再被其他点更新得更小了。一旦出现负权边这个前提就塌了。一个看起来距离较大的点完全可能通过一条负权边后来居上把之前已经“确定”的点的距离变得更小。所以遇到负权边必须改用Bellman-Ford或SPFA。我在第37天的打卡笔记里特意写了一句“Dijkstra不是不能用负权而是它的正确性证明依赖于非负性别拿贪心去挑战数学假设。”6.2 朴素版到堆优化版到底优化了什么朴素版Dijkstra每轮要遍历所有点找最小值复杂度O(N^2)。堆优化版本用优先队列维护“候选最小距离点”免去遍历查找最小值的过程整体复杂度降到O((NM)logN)这是处理大规模稀疏图的常用版本。vectorint dijkstra(int s, int n) { priority_queuepairint,int, vectorpairint,int, greater pq; vectorint dist(n, INF); dist[s] 0; 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}); } } } return dist; }这行if (d ! dist[u]) continue;是堆优化的灵魂所在。因为同一个节点可能被入队多次当它下一次被弹出时如果队列里的记录值和dist数组当前值不一致说明这条记录已经过期没必要再松弛。很多初学者漏掉这行结果程序变慢甚至死循环。堆优化看起来代码不长但藏着不少细节比如pair在C里默认按first排序所以把距离放第一位、节点放第二位这个顺序不能写反。6.3 Floyd用动态规划理解多源最短路如果说Dijkstra是单源最短路那Floyd就是一股脑把所有点对之间的距离全算出来。Floyd的核心代码极其简洁三层循环中间层是“中间点k”int dist[MAXN][MAXN]; // 初始时 dist[i][i]0有边存权值无边存INF 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][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } }我学Floyd时总觉得这个三重循环像个魔术后来用动态规划的眼光看才真正明白外层循环枚举的是“可以使用的前k个点”内层是“从i到j经由前k个点的最短距离”。换句话说dist[i][j]在循环到第k层时允许路径经过编号不超过k的中间节点。正因为每个点都可能成为中间点所以必须是三层循环而且k必须在外层。需要注意的是Floyd的复杂度是O(N^3)N一旦超过500就要非常小心——500的三次方是1.25亿次循环C/C勉强可跑Python基本喘不过来。所以Floyd适合顶点数很小、但需要频繁查询任意点对距离的场景。完整算法实现后我还额外存了一个path矩阵用来回溯具体路径这样在调试带权图问题时能直观看到最优路线的中间节点。6.4 真实场景一个基于地图数据的路径规划测试第37天我做了一个测试用模拟的城市路网数据顶点数4000边数12000起点到终点的最短路用堆优化的Dijkstra跑耗时在毫秒级别。换成朴素版Dijkstra试了同一个样例立刻飙升到秒级。这个测试给我的冲击很直接同一个算法数据结构和优化手段不同性能差距是几个数量级的。从那之后写任何Dijkstra我都会下意识确认自己用的是不是堆优化版本。7. 强连通分量Tarjan一眼看穿有向图的内部结构对有向图来说强连通分量是最核心的结构性概念之一。一个强连通分量是“任意两点互相可达”的最大子图。把每个强连通分量缩成一个点原来的有向图就会变成一个DAG有向无环图很多原本复杂的问题会瞬间简化。这就是为什么缩点是一个在竞赛和工程里都极其常用的手法。7.1 Tarjan算法的核心DFS树、low值和dfn值第一次看Tarjan算法的时候绝大多数人会卡在dfn和low这两个数组的理解上。我的经验是别急着背代码先理解三个问题dfn[u]是节点u第一次被DFS访问到的时间戳也就是它在DFS树里的编号。low[u]是u在不经过“已经入栈但不属于当前DFS早期祖先”的情况下能回溯到的最早的dfn值。当dfn[u] low[u]时说明u是它所在强连通分量的“根”此时弹栈就能把这个分量全部拿出来。Tarjan算法的过程可以看作一次DFS同时维护一个手写栈记录当前DFS路径上尚未归类的节点。每访问一个节点就给它分配dfn和初值对每一条出边如果邻居未被访问过递归访问然后更新low[u] min(low[u], low[v])如果邻居已经在栈中说明找到了一条后向边更新low[u] min(low[u], dfn[v])如果邻居已访问过但不在栈中说明它是已经归类的其他分量忽略当所有邻居处理完如果dfn[u] low[u]就不断从栈里弹出节点直到弹出u为止这些节点组成一个强连通分量。vectorint G[MAXN]; int dfn[MAXN], low[MAXN], belong[MAXN]; bool inStack[MAXN]; stackint st; int timer 0, sccCnt 0; void tarjan(int u) { dfn[u] low[u] timer; st.push(u); inStack[u] true; for (int v : G[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (inStack[v]) { low[u] min(low[u], dfn[v]); } } if (dfn[u] low[u]) { sccCnt; while (true) { int x st.top(); st.pop(); inStack[x] false; belong[x] sccCnt; if (x u) break; } } }7.2 代码诊断里的“循环依赖检测”是怎么用Tarjan的我之所以对Tarjan特别有感情是因为在做代码诊断相关功能时遇到过一个典型的循环依赖问题。一个项目里有几百个模块模块之间互相引用我想找出哪些模块构成了循环依赖。如果用“全局DFS回溯检测”逐层排查思路也能做但代码量大且速度慢。用Tarjan之后每个强连通分量只要大小大于1就必然包含环找出来以后直接输出分量里的模块列表瞬间完成诊断。这个方案的另一个好处是强连通分量自带编号我可以把整个依赖图缩成DAG后再做拓扑排序从而给出“移除了循环依赖之后应该按什么顺序编译”的建议。把原本一个非常头疼的工程问题简化成“跑一次Tarjan 跑一次拓扑排序”代码量不到两百行。7.3 缩点之后图一下子变得清爽很多算法题的套路都是“Tarjan缩点 新图处理”。缩点后强连通分量内部的细节不再重要我们关心的是分量之间的边这时图变成了DAG后面接的通常就是拓扑排序、DP最长路等问题。比如问“整个有向图里最长能走多远”原图可能充满环DP会无限循环但缩点成DAG之后就可以放心地在分量上做DP。这一步的工程价值极高我在LeetCode的Hard题里也常看到这种组合考法。8. 第40天综合实战把十天内容串成一条线最后一天我没有学新算法而是把前九天的内容用三道题串了起来顺带模拟了一次“接到真实需求之后从建模到实现的完整过程”。第一道题是“课程表 II”输入课程序列和依赖关系输出学习顺序。这道题本质是拓扑排序我用邻接表存储Kahn求解然后在最后的地方检查结果长度是否等于课程数用来判断是否存在环。代码量不大但把存储、遍历、拓扑排序、环检测全部串了一遍。第二道题是“网络延迟时间”给定一个有向带权图求从K点发出信号到所有节点都收到信号所需的最短时间。我的解法是堆优化的Dijkstra跑完一遍后取dist数组的最大值如果有节点距离还是INF就返回-1。这道题把前面学的存储和最短路径揉在一起更能检验对堆优化细节的掌握程度。第三道题是自己设计的一个“城市公交规划”模拟输入站点、线路和各线路的费用要求判断哪些站点之间可达并给出最低花费。我试着同时用Prim和Kruskal算最小生成树做对比验证再用Dijkstra求任意两个站点的最低出行费用。做完这个综合实验之后我对选哪一种算法、选哪一种存储结构有了更直觉的判断。这三道题做完已经是第40天晚上。回看这一个阶段最大的感受是很多算法单独看都不难但组合起来用才是真正的考验。比如你不知道“拓扑排序的输出长度可以判断是否有环”那你可能在处理依赖关系时绕圈子你不知道“Dijkstra的堆优化要跳过过期节点”那你跑大数据可能被卡到怀疑人生。这些细节教科书不会替你划重点只有手写过一遍甚至撞过一遍才能沉淀成自己的判断力。9. 十天下来我总结出的几条实战经验最后写几条普适的干货不管你是刚开始学数据结构还是已经在准备面试刷题都应该能从中找到一点参考价值。第一先定存储再写算法。任何一个图相关的问题动手写代码前先搞清楚顶点数与边数的量级再决定用邻接矩阵、邻接表还是链式前向星。判断失误会导致空间爆炸或时间退化。即便是写原型验证的代码也要先问自己这个问题不要偷懒。第二访问标记的位置比遍历本身更重要。BFS在入队时标记Dijkstra在出队时用“距离判断”跳过过期节点Tarjan的inStack只标记当前递归栈内的节点。标记错了要么重复运算要么逻辑直接错误。调试图算法时我通常会先怀疑标记逻辑再怀疑邻接关系。第三把算法当成解决问题的工具来学而不是背模板。拓扑排序不是考点而是依赖分析工具Tarjan不是炫技的硬核算法而是循环依赖检测利器Dijkstra不是面试题而是路径规划里的常客。我在这十天里做得最值得的一件事就是几乎每天都把当天算法映射到一个具体场景里——不管是编译器依赖、代码诊断还是公交规划——用真实感驱动代码的实现而不是只看抽象的教材写法。第四动手写代码的时候最好给自己加一道“极端输入”测试。比如长链图让DFS爆栈、2万顶点稀疏图让邻接矩阵爆内存、带负权边让Dijkstra出错。只有亲自踩过这些坑才会在以后设计系统时自然而然地避开它们。第41天开始我打算进入更进阶的图论专题网络流那边还等着我去啃。如果你也正在日撸代码的路上请一定相信图这块硬骨头越早啃完以后遇到复杂系统问题的时候手里能用的工具就越锋利。