★ FEATURED ARTICLE 这周把这门数据结构的MOOC课程第八讲练习重新刷了一遍。第八讲的内容是图从存储结构到遍历再到最短路径和拓扑排序覆盖面非常广。说实话课堂上的PPT看得明明白白一到上机做题就全是细节崩盘数组开小、初始化忘记、遍历层数控制错位、最短路径的附加条件没处理干净。这篇文章就把我做这一讲编程练习题时踩过的坑、总结出来的套路完整梳理一遍。适合正在学图论、准备刷题或者复习这门课的人参考。1. 图存储的那道题邻接表比邻接矩阵更容易在细节上翻车第八讲的第一道练习题通常是建图。题目大概是这样给定N个顶点和M条边每条边带权值要求构建一个带权有向图并输出每个顶点的出度和它所有出边的终点及权值。题目描述很朴素但隐藏了一个关键信息N的数据范围可能到10的5次方M到2×10的5次方。如果这里没留意直接用邻接矩阵那就是N的平方等于10的10次方个单元内存直接爆炸。所以这道题的核心考察点不是你会不会存图而是你知不知道什么时候该用邻接表。用邻接表时人教版教材和MOOC课件里最常见的写法是链表数组。我给出一个可以直接用的结构体设计#include stdio.h #include stdlib.h typedef struct AdjNode { int v; // 终点顶点编号 int weight; // 边权 struct AdjNode *next; } AdjNode; typedef struct { AdjNode *head; // 指向第一条出边 } VNode; int degree[100005]; // 出度统计数组 int main() { int n, m; scanf(%d %d, n, m); VNode *graph (VNode *)calloc(n 1, sizeof(VNode)); for (int i 0; i m; i) { int u, v, w; scanf(%d %d %d, u, v, w); AdjNode *node (AdjNode *)malloc(sizeof(AdjNode)); node-v v; node-weight w; node-next graph[u].head; graph[u].head node; // 头插法 degree[u]; } for (int i 1; i n; i) { printf(%d %d, i, degree[i]); for (AdjNode *p graph[i].head; p; p p-next) { printf( - %d(%d), p-v, p-weight); } printf(\n); } return 0; }这里我用了头插法。头插法的好处是插入时间是O(1)而且不需要维护尾指针代码简单。但要注意头插法会让出边的顺序和输入顺序相反。如果题目要求按终点编号升序输出头插法就不行了必须用尾插法或者在输出阶段对邻接表排序。实测中这类题目大多数不限制顺序但大多数不等于全部做题前一定要把输出要求看清楚。还有一个容易翻车的点无向图要建两条边。很多同学读题时只看到图字就默认是无向图或者默认是有向图结果有一半测试点不过。这题的题面里如果写明有向图那只需要建一条边如果没写明最好按有向图处理再看样例验证。我在第一次做这题时就是没注意带权有向图这几个字少建了一条边导致输出结果和样例对不上排查了二十分钟。另外内存分配也是一个坑。如果用malloc给每个邻接点单独分配空间M是2×10的5次方时malloc调用次数很多虽然没问题但效率不高。实测用calloc把整个顶点数组一次性清零比逐个初始化省事得多。动态分配时还要记得检查返回值为NULL虽然判题环境一般不会内存不足但在本地调试时如果分配失败程序会直接崩溃。这块还有一个容易被忽略的小点出度数组和邻接表的一致性。如果你在建边过程中同时维护degree[]那么后面遍历输出时就不需要再数一遍链表长度。不要临时抱佛脚等到输出时才回头统计出度那样不仅多写代码还容易数错。单独开一个数组在插入边的同时累加这也是后面几道题比如拓扑排序算入度的通用套路。2. 遍历应用题从关系传播圈这道题看BFS的层数控制第二道典型的编程题是遍历。我拿到的这道题是这样的某社交平台有N个用户用户之间存在M条关注关系现在从指定用户S出发统计通过最多K层关注关系能够触达多少个不同用户最后输出触达人数占总人数的百分比。K通常给6N和M的范围比较大。如果你之前接触过六度空间这个经典问题会发现这道题几乎是同一个思路只是换了个壳。这道题的核心是BFS限层遍历。我见过不少同学第一反应是用DFS递归层数限制但如果N到10的5次方、关注关系多递归深度可能很大容易爆栈。BFS天然按层扩展控制层数非常自然队列实现也更稳。我的写法是用一个数组模拟循环队列队列里存两个字段顶点编号和当前层数。出队以后如果当前层数已经等于K就不再扩展它的邻居否则把未访问过的邻居入队层数加1。访问计数从1开始因为起点S自己也算触达用户。#include stdio.h #include string.h #define MAXN 100005 typedef struct Node { int id; int level; } Node; int head[MAXN], to[MAXN * 2], nxt[MAXN * 2]; int edgeCnt; int visited[MAXN]; Node queue[MAXN]; void addEdge(int u, int v) { to[edgeCnt] v; nxt[edgeCnt] head[u]; head[u] edgeCnt; } int bfsLimit(int s, int n, int K) { memset(visited, 0, sizeof(visited)); int front 0, rear 0; queue[rear].id s; queue[rear].level 0; rear; visited[s] 1; int count 1; while (front rear) { Node cur queue[front]; if (cur.level K) { continue; // 当前节点已达层数上限不扩展邻居 } for (int e head[cur.id]; e; e nxt[e]) { int v to[e]; if (!visited[v]) { visited[v] 1; count; queue[rear].id v; queue[rear].level cur.level 1; rear; } } } return count; } int main() { int n, m, K; scanf(%d %d %d, n, m, K); for (int i 0; i m; i) { int u, v; scanf(%d %d, u, v); addEdge(u, v); addEdge(v, u); // 无向关系两条边都要建 } int s; scanf(%d, s); int reachable bfsLimit(s, n, K); printf(%.2f%%\n, reachable * 100.0 / n); return 0; }这段代码里最重要的一行是if (cur.level K) continue;。它的语义是当前节点已经达到了最大层数所以不去碰它的邻居。很多人的错误写法是在访问邻居时判断cur.level 1 K逻辑上也能实现但容易把边界搞混。比如当K等于6时从起点出发1层的节点level1扩展它们得到level2直到level6时停止这正好触达第6层。如果判断条件写错成cur.level K再入队效果其实一样但思维不清晰的时候很容易把等号丢错导致多算一层或少算一层。队列的数组模拟也值得说一下。queue的长度要有讲究最坏情况下所有节点都入队所以至少开N个长度。但为了保险我习惯开N5避免恰好满队列时出现边界问题。递归DFS做不到这种精细的层数控制而且对10的5次方级别的图不友好所以这一讲只要涉及大图遍历我无脑优先BFS。有同学可能会问visited数组为什么要提前置1而不是出队时置1这就涉及到BFS的一个经典bug如果等出队时再标记访问那同一个节点可能被多个邻居在入队前都判定为未访问从而被重复入队层数和计数都会乱。入队时就标记访问是BFS的通用铁律凡是计数类的BFS题目这句话能救你半条命。最后是一个来自实测的输入优化建议当N和M超过10的5次方时用scanf比cin快很多如果用C的cin不关同步很容易超时。我见过有人在这道题上用cin被卡到TLE换成scanf之后直接通过性能差异在数据量大的时候非常明显。3. Dijkstra变形题输出最短路径时反向记录前驱是最稳妥的做法最短路径题目在第八讲的练习题里占据了不小的比重。我遇到的这道题是一个城市的公交线路网络N个站点M条单向线路每条线路有一个行驶时间。给定起点和终点要求输出最短时间和具体路径。注意附加条件如果有多条最短时间的路线选择经过站点数最少的一条如果仍然不唯一选择路径序列字典序最小的那一条输出。这类最短路径附加条件的题是Dijkstra算法最常见的变体。基础部分没什么悬念维护dist[]数组表示起点到每个顶点的最短时间维护visited[]数组标记已确定的顶点。核心难点在于附加条件的实现。我的做法是维护三个数组dist[]、pre[]、cnt[]。pre[v]记录在最短路径上v的前驱顶点cnt[v]记录起点到v的路径上经过的站点总数。初始时dist[s]0cnt[s]1把起点本身算一个站点。路径输出时从终点开始沿着pre[]一直回溯到起点然后逆序打印。关键代码片段是这样的#define INF 0x3f3f3f3f int dist[MAXN], pre[MAXN], visited[MAXN]; int cnt[MAXN]; void dijkstra(int s, int n) { memset(dist, 0x3f, sizeof(dist)); memset(pre, -1, sizeof(pre)); memset(cnt, 0x3f, sizeof(cnt)); dist[s] 0; cnt[s] 1; while (1) { int u -1, minDist INF; for (int i 1; i n; i) { if (!visited[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) break; visited[u] 1; for (int e head[u]; e; e nxt[e]) { int v to[e]; int w weight[e]; if (visited[v]) continue; if (dist[v] dist[u] w) { dist[v] dist[u] w; pre[v] u; cnt[v] cnt[u] 1; } else if (dist[v] dist[u] w) { // 时间相同比较站点数 if (cnt[v] cnt[u] 1) { cnt[v] cnt[u] 1; pre[v] u; } } } } }这里有一个非常容易错的地方只有dist更新时才更新pre而dist相等时的处理要在原路径和新路径之间做条件判断。很多人做这类题时会把站点数最少这个条件直接加到主循环的松弛判断里也就是在dist[v] dist[u] w时直接比较cnt这样其实不会错但如果dist相同而cnt更优就需要另一个分支来处理。上面代码的写法比较清晰先看时间时间一样再看站点数。还有一个隐藏较深的坑如果站点数也相同需要比字典序。字典序的处理方式通常是当dist和cnt都相等时比较从起点到v的整条路径的字典序。一种比较方便的实现是不管pre数组怎么记录在需要输出路径时把所有候选最短路径找出来比较它们从起点到终点的序列。但这样复杂度过高。更实际的做法是逆向思维在松弛时候从终点方向往前推用某种规则更新pre。我在实际做题时发现一个规律——如果题目要字典序最小的路径从起点正向做Dijkstra配合pre记录很容易做反正确做法往往是从终点做一次反向Dijkstra或者把顶点编号的大小比较顺序反过来处理。如果这道题的数据范围较大比如N到10的4次方、M到10的5次方朴素O(N的平方)的Dijkstra会超时需要用优先队列优化。MOOC课件里也提过堆优化版本。核心改动就是用一个最小堆维护当前dist最小的未访问顶点每次弹出顶点u时如果u已被访问就跳过否则遍历它的出边松弛。在这种写法下dist数组中重复入堆的旧值不会造成逻辑错误只需要加一个if (visited[u]) continue;判断即可。我个人做Dijkstra变体题的心得是先把无附加条件的基础版本写对再增量加pre、cnt这些数组。一上来就同时处理时间、站点数、字典序三个条件思维负担太重容易把数组维护混乱。先用一个简单样例把最短时间算对了再逐步增加附加条件每增加一个就用对应的测试点验证这样定位bug会快很多。另外INF的选取也有讲究。用0x3f3f3f3f是经典做法因为两个INF相加不会溢出int而且memset直接按字节填充很方便memset(dist, 0x3f, sizeof(dist))就能把所有距离设为INF。如果用INT_MAX在计算dist[u] w时可能溢出变成负数然后被当成更短路径这个问题在新手代码里非常常见。4. 拓扑排序题判断回路、合法输出顺序以及队列还是栈的选择第八讲的最后一类核心题是拓扑排序。我遇到的题是这样的一个项目有N个任务任务之间有M个依赖关系每条依赖关系用u-v表示任务u必须在任务v之前完成。要求判断整个依赖关系是否存在环如果无环输出一个合法的任务完成顺序。拓扑排序的标准做法是Kahn算法思路直白统计每个顶点的入度把入度为0的顶点全部入队每次从队头取出一个顶点并输出把它所有出边的终点入度减1如果某个终点的入度减到了0就把这个终点入队。最终如果输出的顶点数量等于N说明拓扑排序成功如果少于N说明图中存在环。#include stdio.h #include string.h #define MAXN 100005 int head[MAXN], to[MAXN], nxt[MAXN]; int edgeCnt; int indegree[MAXN]; int queue[MAXN]; void addEdge(int u, int v) { to[edgeCnt] v; nxt[edgeCnt] head[u]; head[u] edgeCnt; indegree[v]; } int topologicalSort(int n) { int front 0, rear 0; for (int i 1; i n; i) { if (indegree[i] 0) { queue[rear] i; } } int count 0; while (front rear) { int u queue[front]; printf(%d , u); count; for (int e head[u]; e; e nxt[e]) { int v to[e]; indegree[v]--; if (indegree[v] 0) { queue[rear] v; } } } return count n; // true表示无环 }这段代码里indegree[]的维护在建边时完成。每次读入u-v都要对indegree[v]。有一个细节很容易疏忽当题目中可能存在重复边时入度会被重复累加。比如给了两条相同的u-v如果直接累加那么删除u的出边时会把v的入度减两次正好抵消理论上没问题。但如果其中一条边因为某种原因没有被正确加入邻接表入度统计就会对不上导致拓扑排序失败。所以保险做法是在建图时对边去重或者至少在头脑里确认输入里没有重复边。另一个常被忽略的问题是输出顺序的确定性。Kahn算法用普通队列时只能保证输出一个任意合法拓扑序但不同测试点可能要求特定顺序。我遇到过一道变体题要求输出所有合法拓扑序里字典序最小的那个那就不能再用普通队列了要换成优先队列每次从入度为0的顶点里挑编号最小的先输出。这种变体在MOOC练习里偶尔会出现认真读题很重要。关于队列还是栈这里有个经典讨论拓扑排序如果用一个栈来存放入度为0的顶点得到的序列会是一个逆拓扑序吗其实不会栈只是改变了同层顶点的输出顺序本质上和队列一样都是输出某个合法拓扑序。真正得到逆拓扑序的是DFS后序的逆过程。如果题目要求输出任意一个合法拓扑序队列和栈都可以如果题目要求按编号从小到大就用优先队列。反正我在做题时默认先看题目对输出顺序有没有特殊要求有要求再改数据结构别一上来就默认队列。判断回路还可以用DFS的思路维护一个有未访问/在递归栈中/已访问完三色标记的数组如果在递归过程中遇到还在栈中的节点说明有环。但Kahn算法实现起来更短、更不容易出错而且可以顺便输出拓扑序。所以我更推荐Kahn方法。这道题我最开始做的时候忽略了一个边界情况如果图中所有顶点入度都是0程序应该直接输出所有顶点也就是1到N的某种排列。如果N特别大这个输出本身也可能是一个性能瓶颈。不过这题N通常不大printf逐行输出没问题。还有一个来自实测的教训当N个顶点的编号不是连续的1到N而是从0开始或包含孤立节点时入度为0的判断范围也要跟着调整。MOOC练习题一般约定编号从1到N但以后工作中处理真实数据时经常出现编号稀疏的情况那时候就不能简单用数组下标对应顶点编号了通常需要先做离散化。竞赛和课程练习里可以先不用考虑但心里要有这根弦。5. 这一讲做题最容易踩的五个坑我从实测里总结出来的做完第八讲所有练习题我整理了一下自己和其他同学最容易踩的五个坑每一个都是真实的DEBUG经历放在这里供大家参考。第一个坑是数组开太小。图论题的N和M范围往往不同N可能只有10的5次方但M可能到2×10的5次方。无向图建边时要存两条边如果你照着M的大小开to[]和nxt[]就会数组越界。我的建议是统一开成MAXM * 2如果图是带权的再加一个weight[]数组同样开成边数的两倍。还有一个细节如果边集数组的下标从1开始计数初始化时edgeCnt要为0然后edgeCnt再使用这样第一个有效下标是1能够和0区分开避免和没有边搞混。第二个坑是多组测试数据的处理。MOOC有些题目会连续给多组输入以某种特殊标记结束。比如题目说读到0 0结束那读入循环就要写成while (scanf(%d %d, n, m) 2 (n || m))。很多人没有处理多组输入只处理了一组就输出结果导致只对一半测试点。这个问题的隐藏点在于多组输入之间所有全局数组都需要重新初始化memset或者循环置零都不能漏。我建议把每个测试用例的逻辑封装成一个函数每组输入都重新调用这样局部变量的状态天然是新的不容易残留上次的数据。第三个坑是memset的使用误区。很多同学知道用memset把dist[]或visited[]清零但对结构体数组或指针数组用memset就很危险。比如邻接表数组VNode graph[MAXN]如果直接用memset(graph, 0, sizeof(graph))能够把head指针清成NULL这没问题但如果VNode里还有其他字段就要确认memset的字节数填对了。我在实践中更倾向于用calloc分配图结构因为calloc会把分配的内存自动清零。如果你已经用malloc分配了再想清零需要memset(graph, 0, (n 1) * sizeof(VNode))这里的(n 1)千万别漏否则只清了一部分。第四个坑是递归DFS的栈溢出。图论的深度优先遍历在顶点数超过10的5次方、并且图退化成一条长链时递归深度就是N系统栈很容易爆掉。第八讲的题目有些虽然用BFS更合适但总有人喜欢用DFS。如果你的代码在本地小数据一切正常一交上去就RE很可能是递归栈的问题。解决方案有两个一是把DFS改成显式栈的迭代写法用数组模拟栈来遍历二是如果题目允许直接换成BFS。我是建议能用BFS解决的尽量用BFS不仅省栈思路也清晰。第五个坑是输出格式的细节。图论题的输出格式往往比题目本身更烦人。比如要求每个顶点的输出占一行或者百分比保留两位小数并带百分号再比如路径中相邻顶点之间用-连接。这些细节错了判题系统直接给格式错误而格式错误的提示通常不会告诉你具体错在哪只能自己对着样例比对。我在这讲就栽过一次Dijkstra那题要求路径输出为起点-中间顶点-终点我在最前面多打了一个空格结果整个测试点全挂。后来学乖了提交之前先用题目给的样例做逐字符比对尤其是行尾空格、换行、空行这些细节肉眼比对不放心的话可以用diff命令对比自己的输出文件和样例输出文件。6. 一些做题节奏上的个人体会前五节已经把这一讲的题型和代码细节都过了一遍。最后聊点实际的做题思路不算总结就当是同行之间的经验交换。我自己的习惯是拿到一道图论题先花两分钟在草稿纸上画出样例对应的图手动跑一遍答案确认自己对题目的理解没错再动手写代码。这个习惯帮我避免了很多题意理解偏差导致的返工。特别是图论的题面里有向/无向连通/非连通权值可负/不可负这些词每个都直接影响算法选型看漏一个就得推倒重来。Dijkstra不能处理负权边拓扑排序只能用于有向图这些边界条件一定要和题面逐字对照。代码写完以后我还会故意构造几组边缘测试单个顶点的图、两个顶点一条边的图、完全图、带重边的图、自环的图、N取最大值时的时间性能。这些边缘用例能暴露很大一部分隐藏bug。MOOC的判题系统虽然会给比较全面的测试点但它不会告诉你哪个测试点错了自己先用边缘数据验证能省很多次无效提交。图论这一讲是整门课里我觉得含金量最高的一块。存储是骨架遍历是血液最短路径和拓扑排序都是在骨架上跑起来的逻辑。第八讲练习做完一遍之后后面再遇到什么关键路径AOE网络其实都是从这些基础模型延伸出来的。把这一讲的题吃透图论就算真正入门了。希望这些踩坑记录能帮你少走点弯路。
阅读完成 · 觉得有帮助？
