最近在刷某高校《数据结构》慕课的编程练习题正好做到第八讲。这一讲在整门课里属于“承上启下”的位置——前面的线性表、栈队列、树都打完了基础后面还有查找排序等着而第八讲的内容通常落在图论或搜索这一大块是很多同学的分水岭会的人觉得代码就那么几套模板不会的人盯着题目半天不知道该建图还是该遍历。我当初自己刷这一讲的时候也踩了不少坑比如递归爆栈、邻接矩阵开太大直接段错误、BFS队列忘记判空导致死循环……这些问题不做一遍根本不会意识到。所以这篇就把我做编程练习题的过程、思路拆解和一些排查经验整理出来给正在跟这门课或者准备考研复试的人做个参考哪怕是完全没思路的小白照着这个框架慢慢啃也能把第八讲稳稳吃下来。1. 第八讲到底在考什么知识边界与题目风格1.1 这一讲的知识范围先说第八讲在整个课程体系里的定位。数据结构这门课前面的章节基本都在讲“线性结构”和“树形结构”而第八讲一般会把重心转到“图”以及基于图的搜索算法上部分版本还会捎带一点散列查找的入门。也就是说这一讲的编程题不像之前链表、栈那种“给你一个结构你实现几个函数”的写法而是更接近“给你一个现实问题你抽象成图再用算法解决”。这一讲典型的可考知识点包括图的两种存储结构邻接矩阵和邻接表图的深度优先搜索DFS和广度优先搜索BFS连通分量、连通图的判断最短路径的两种经典算法单源的Dijkstra、多源的Floyd最小生成树Prim和Kruskal两种思路拓扑排序、关键路径部分题目会以判断有向图是否有环的形式出现从编程练习题的分布来看最常出的是DFS/BFS遍历题然后是Dijkstra求最短路径的变体最小生成树和拓扑排序稍微少一点但也不是没有。有一点很关键这一讲的编程题几乎不会让你“默写算法”而是把算法嵌在一个具体的场景里比如“给定一张地图和若干条道路求从A到B的最短时间”“判断图中是否存在环”“找出所有连通块并统计个数”。所以单纯背模板是不够的得理解每个算法在解决什么问题、它的边界条件是什么。1.2 编程题的输入输出套路慕课的编程题通常采用在线评测方式输入输出格式写得很清楚但有几个隐藏的“坑”是新手容易忽视的。第一节点编号可能是从0开始也可能是从1开始。如果题目没有明确说“节点编号从1到N”那你建图的时候一定要先看样例输入。有的题目直接用节点编号作为数组下标有的则要整体减一。我见过很多人在这个地方翻车样例过了但提交全错就是因为数组开小了或者下标越界。第二输入里可能包含“多组测试数据”。评测系统一般会读到文件结尾EOF才停止处理你需要用循环读入并且在每一组数据开始时清空图结构。这个细节不处理好经常会出现“上一组数据残留节点导致连通分量数量算错”的问题。第三无向图需要双向建边有向图只建单向。听起来很简单但是很多人在处理“每条道路连接两个村庄”这类描述时下意识就只加了一条边导致后面的DFS遍历只能走到一半的点。2. 从题目到代码核心练习题的拆解与编码思路2.1 建图的两种姿势选对了省一半心第八讲的编程题第一步永远是“建图”。这一步没做好后面所有算法都是空中楼阁。我见过不少同学代码逻辑本身没问题结果vector用成map或者邻接矩阵开成int g[10005][10005]一跑就内存爆掉。邻接矩阵适合稠密图也就是边的数量接近顶点数的平方。它的优点是代码直观判断两个顶点是否相邻是O(1)操作缺点是空间占用是O(V^2)。如果题目给的顶点数在1000以内用邻接矩阵是没问题的但如果顶点数到了1万甚至10万矩阵根本存不下。邻接表适合稀疏图实际题目里绝大多数图都是稀疏的。用vectorint adj[N]或者链式前向星都行前者写起来方便后者在某些高性能场景下更快。我自己的习惯是先用vector如果题目数据范围特别大再换链式前向星。有一个实操小技巧如果边还带权重那就把vectorint改成vectorpairint,intsecond存权重。很多模板题里Dijkstra需要反复取一条边的终点和权重用pair比用两个平行数组清晰得多。2.2 DFS遍历的代码骨架与细节DFS的代码骨架很简单但真正写对的人不多。一个标准的DFS函数是这样void dfs(int u) { visited[u] true; // 标记当前节点已访问 for (int v : adj[u]) { // 遍历所有邻接点 if (!visited[v]) { dfs(v); // 递归访问 } } }看起来简单但有几个细节值得注意。第一visited数组的标记时机。我见过很多人写成进入循环之后再标记比如for (int v : adj[u]) { if (!visited[v]) { visited[v] true; // 这样写会导致重复访问 dfs(v); } }这样写的问题在于如果图中有环同一个节点可能被多个邻接点分别发现并重复递归轻则效率变慢重则直接栈溢出。正确做法是一进入递归就立刻标记不管这个节点是不是通过当前路径第一次被发现。第二递归深度。当图的顶点个数达到上千甚至上万时DFS的递归深度可能很深。C的默认栈空间一般只有几MB递归一万层基本就爆了。如果你在评测系统里看到“段错误Segmentation Fault”十有八九就是这里出了问题。解决办法有两个一个是在代码开头加上#pragma comment(linker, /STACK:1024000000,1024000000)但这个只对Windows下的某些编译器有效更稳妥的办法是手写栈模拟DFS不过实现起来稍微复杂一点。2.3 BFS遍历的队列写法与判空细节BFS比DFS更适合求“最短路径的跳数”因为它天然按照层数扩展。标准写法如下void bfs(int s) { queueint q; visited[s] true; q.push(s); 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的标记时机。如果等到弹出队列的时候才标记那同一个节点可能被多次入队队列里全是重复元素在某些极端情况下程序会超时甚至溢出。正确的时机是“第一次发现这个节点时立即标记并入队”。第二个坑是队列判空。很多人写着写着会忘了while (!q.empty())的条件或者把q.front()和q.pop()的顺序搞反。虽然这些都是小问题但在心情急躁的时候特别容易犯。2.4 最短路径问题的两种解法选择第八讲如果涉及最短路径最常见的是单源非负权重最短路径也就是Dijkstra。Dijkstra的朴素写法是O(V^2)每次在未访问节点里找距离最小的那个。对于顶点数在1万以内的题目这个复杂度可以接受。但如果顶点数到了10万就必须用优先级队列优化到O(E log V)。用优先级队列优化的Dijkstra写起来反而比朴素版更顺手因为不需要手动遍历找最小void dijkstra(int s) { vectorint dist(N, INF); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,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;这句话的作用是过滤掉那些已经被更新的旧数据。没有这句话程序也能跑但优先级队列里会有大量冗余元素性能会被明显拖慢。Floyd算法适合多源最短路径代码非常短三重循环就完事。但它的复杂度是O(V^3)所以在编程练习题里很少出现大数据量。如果题目里明确说“求任意两点之间的最短路径”而且顶点数不超过200那Floyd就是最合适的。2.5 连通性与拓扑排序的快速判断有些题的考点不是最短路径而是“这个图里有多少个连通块”。比如“给定一个城市地图求需要修建多少条道路才能让所有城市连通”本质就是找连通分量的个数然后用个数-1作为答案。实现方式就是遍历所有节点对每个未访问节点执行一次DFS/BFS统计执行次数即可。拓扑排序是一个容易被忽视的点它在有向无环图DAG中才有意义实现方式是用队列维护所有入度为0的节点不断弹出并减少邻接点的入度vectorint topoSort(int n, vectorvectorint adj, vectorint indegree) { 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; }这里的判环技巧就是最终result的长度是否等于节点数。如果不等于说明图里有环。很多“课程安排是否能完成”的题目本质上就是问“拓扑排序是否存在”把这个判断加上就对了。3. 实操复盘从读题到提交的完整流程3.1 拿到题目之后先做什么很多人的习惯是拿到题目后直接开始写代码我把这个习惯改了之后正确率提升非常明显。正确流程应该是读题三遍 → 手算一遍样例 → 设计测试数据 → 再动键盘。读题三遍不是夸张。第一遍像看小说一样通读知道这道题大概在说什么场景第二遍把关键条件圈出来包括顶点的范围、边的范围、权重是否有负数、是否需要输出路径本身第三遍专门看输入输出格式确认节点编号的起始值和多组数据的标志。手算样例的意思是在纸上或者注释里把题目的样例输入变成图然后自己走一遍算法看最终输出是否和题目给出的样例输出一致。这一步极其重要它能帮你确认自己对题目的理解没有偏差。我之前遇到过一个情况题目给的无向图我以为是单向边样例数据刚好在单向边的情况下也能输出同样的结果结果提交上去全错。手算一遍才能发现这种隐藏信息。3.2 测试数据的构造方法在线评测系统只给你一次提交机会如果你不想“罚时”就得自己在本地多测几组数据。但很多人的测试数据太弱了只测了题目自带的样例发上去就错了。我的经验是至少构造三类数据第一类是最小数据比如只有一个节点的情况。很多算法在只有一个节点时会触发边界条件的边缘情况比如Dijkstra里源点就是目标点拓扑排序里的队列只有一个元素这类数据最容易暴露初始化问题。第二类是链式数据也就是图形成一条长链1连2、2连3、3连4……这种方式用来测递归深度如果代码会爆栈链长几百就能看出来。第三类是空图或非连通图比如输入里没有任何边只有孤立节点。这时候用DFS/BFS遍历得到的连通分量个数应该是节点总数如果你把每个孤立节点也算成连通块而题目要求只统计有边的部分结果就会出错。3.3 一个完整的Dijkstra变体题实操示例我用一道典型的练习题作为示例题目描述大概是给定N个城市、M条公路每条公路有长度求从城市1到城市N的最短路径长度。这道题就是纯Dijkstra没有太多变形但它很适合拿来展示完整流程。首先建图。城市编号从1到N邻接表开vectorpairint,int adj[N1]因为是无向图公路是双向的所以每次输入一条边要加两次。然后跑标准Dijkstra。因为N可能比较大直接用优先级队列优化版。最后输出dist[N]如果dist[N]还是无穷大说明城市1和城市N不连通按题目要求输出-1。完整代码如下#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int main() { int n, m; cin n m; vectorvectorpairint,int adj(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } vectorint dist(n 1, INF); priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; dist[1] 0; pq.push({0, 1}); 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}); } } } cout (dist[n] INF ? -1 : dist[n]) endl; return 0; }这段代码我实际跑下来大部分评测点都能过。唯一的坑在N1的时候如果城市只有1个且没有边dist[1]就是0输出0这符合逻辑但如果题目把这种情况定义为“不连通”就得额外判断。所以做题的时候还是要回到题目本身看边界定义。4. 常见问题与排查技巧实录4.1 经典报错与解决思路我在刷第八讲的过程里遇到过不少报错把这些整理成了一张速查表方便大家对照排查现象可能原因排查方向编译错误用了C11之前的编译器却使用了auto结构绑定把auto [a,b]改成.first和.second运行时错误RE数组越界检查节点编号是否从0开始数组是否够大答案错误WA建图时只建了单向边确认无向图是否双向建边超时TLEDijkstra用了朴素写法没有堆优化数据量大时换成优先级队列内存溢出MLEint g[20005][20005]这类大矩阵换成邻接表多次输出多组测试数据未在循环内重置visited每组数据前重新初始化全局数组4.2 最常见的三个隐蔽坑先说第一个隐蔽坑vector的初始化问题。如果你在循环里每次都重新定义vectorvectorint adj(N)这行代码那没问题但如果你把adj定义成全局变量每读一组数据后却忘记clear()和resize()那上一组的残留数据会直接污染下一组的结果。第二个隐蔽坑是memset的使用。memset按字节填充所以对于整型数组通常用0或-1没问题但如果想填充成1结果会变成16843009而不是1。很多人喜欢memset(dist, INF, sizeof(dist))这里的INF如果是0x3f3f3f3f是可以的因为0x3f的每个字节都是0x3f填充后整个int就是0x3f3f3f3f。但如果你自己定义了INF 1e9直接memset(dist, INF, ...)就会出错正确做法是fill(dist.begin(), dist.end(), INF)。第三个隐蔽坑跟递归函数有关。如果你在主函数里定义了一个大数组再传到递归函数里每次递归都会复制整个数组导致时间和内存都爆炸。解决办法是把大数组定义为全局变量或静态变量或者传引用。这一点在DFS遍历邻接表时尤其常见因为vectorvectorint如果按值传参每一层递归都会复制一份完整的图结构数据一大就必挂。4.3 本地调试与在线评测的差异在线评测系统只检查你的输出不会给你任何中间过程的反馈所以在本地调试的时候很多人习惯加一大堆cout debug endl;。这在本地没问题但提交之前一定要把这些调试代码全部删掉。否则输出的内容多了哪怕逻辑全对评测也会判WA因为评测系统期望的是精确匹配的输出格式。另外一个很实用的调试技巧是构造“对拍器”。我一般会写一个暴力版本的解法比如用最朴素的DFS枚举所有路径再写一个优化版然后用随机数据生成器批量生成测试用例比较两个版本输出是否一致。在第八讲的练习里这个方法特别管用尤其是Dijkstra的变体题暴力版可以用Floyd或者直接DFS枚举虽然在大数据量下会超时但在小数据量下足够用来验证正确性。5. 复习节奏与练习建议5.1 做多少题才够很多人会纠结“第八讲到底要刷多少题才够”我的看法是不用贪多但一定要把每种题型都覆盖到。最少训练量是这样的邻接表建图练2题、DFS连通分量练2题、BFS最短跳数练2题、Dijkstra练3题、拓扑排序练2题。也就是说10到12题左右就能把这一讲的主流考点全部过一遍。再多的话边际收益会递减不如把时间留给后面的查找排序章节。做题顺序也有讲究我建议按照“建图→遍历→最短路径→拓扑”这个顺序推进不要一上来就做最短路径的综合题否则你在建图环节就卡住的话后面再怎么写都白搭。5.2 什么时候需要放弃看题解我见过两类极端的人一类是死磕型一道题想三个小时不放弃另一类是投机型看了十分钟没思路直接看题解。这两种都不太健康。死磕型的效率太低钻石级别的题就算最后做出来了你消耗的精力也足够你做两三条其他题目投机型的问题在于看题解得到的印象远不如自己推出来的深刻下次遇到稍微改一点就又不认识了。我的判断标准是如果卡了45分钟到1小时没有任何进展那就去看题解。但看题解不是直接看代码而是先看解题思路的一句话总结比如“这题本质是求连通分量”“这题可以用Dijkstra加一个小优化解决”然后合上题解自己重新写。如果这样还写不出来再看代码也不迟。这样做的效果比直接抄答案好得多因为你至少自己把思路转成了代码中间缺的逻辑你也能在对比代码时找到。5.3 这个能力能迁移到哪些场景第八讲练的不只是数据结构本身。我之前在准备某公司的笔试时发现有一道题跟这里的“课程安排”拓扑排序题非常像只是场景换成了“编译任务依赖关系”。第一道题跟“城市之间至少要修多少条路才能连通”也几乎是同构的只是换成了“社交网络里最少加多少好友才能让所有人间接认识”。这种迁移能力本质上是因为你在练习时掌握了“某类问题可以用某个算法”的元认知而不是背下了某个具体题目的代码。第八讲恰恰是帮你建立这种元认知最好的阶段因为图论问题的变体特别多但算法内核就那么几个。还有一个我自己感触很深的点第八讲的编程练习题里调试的时间往往比写代码的时间更长。当你花一个小时在找为什么Dijkstra会多输出一条边的时候你对数据结构本身的理解会比看书三小时还要深刻。这也是我写这篇博客的原因——把踩坑经历记录下来希望后来的人不用再在同样的地方浪费时间。