企业官网建设流程全解析

这周把这门数据结构的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通常给6，N和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层的节点level=1，扩展它们得到level=2，直到level=6时停止，这正好触达第6层。如果判断条件写错成cur.level < K再入队，效果其实一样，但思维不清晰的时候很容易把等号丢错，导致多算一层或少算一层。

队列的数组模拟也值得说一下。queue的长度要有讲究，最坏情况下所有节点都入队，所以至少开N个长度。但为了保险，我习惯开N+5，避免恰好满队列时出现边界问题。递归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]=0，cnt[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网络"，其实都是从这些基础模型延伸出来的。把这一讲的题吃透，图论就算真正入门了。希望这些踩坑记录能帮你少走点弯路。