1. 从一个排期翻车现场说起：为什么必须算关键路径

去年我接了个内部工具的小项目，功能拆完大概七八个模块，大家估完都觉得两周肯定能干完。结果到了第十三天，核心模块还在联调，整个组干到凌晨两点，最后还是延期两天交付。复盘的时候发现一个问题：所有人都盯着"要做的活"，但没有人算过"哪条链路决定总工期"。

你要是也在学AOE网络、准备数据结构的课程设计，或者刷到翁恺老师C语言练习题里那几道图算法题，那"关键路径"就是绕不开的一关。我个人的体会是：用C语言亲手实现一遍，远比在草稿纸上画图理解得深。因为你要自己处理建图、拓扑排序、正向推最早时间、反向推最迟时间，还要把"哪些活动一秒钟都不能拖"正确打印出来，每一个环节都含糊不得。

这篇文章从"为什么要算"讲起，然后用一个具体的项目排期例子，把AOE网络建模、ve/vl计算、关键活动判定完整走一遍，最后给出可以直接跑的C语言代码，并附上我实测中踩过的几个坑。代码基于标准C（stdio.h、stdlib.h）编写，适合正在学数据结构的同学当答案加理解手册用。

2. 先把项目排期翻译成一张AOE网络

2.1 事件、活动和权值的分工

关键路径算法处理的对象叫AOE网络（Activity On Edge），也就是"边表示活动"的带权有向图。乍一听有点绕，其实拆开看很简单：

• 顶点代表事件：某个时间点，前面的活都干完了，后面的活可以开始。比如"需求评审通过"是一个事件，"编码完成"也是一个事件。
• 有向边代表活动：从一个事件到另一个事件的整个动作，比如从"需求完成"到"编码完成"之间，有一条边表示"编码"这个动作。
• 边上的权值代表活动持续时间：单位可以是天、小时，无所谓，只要统一就行。

为什么要用边表示活动而不是顶点表示活动？因为网络计划里一个关键信息是"先后约束"：编码必须在需求完成之后，测试必须在编码之后。用边把事件串起来，每个活动有了明确的起点事件和终点事件，你才好回答"某件事最晚什么时候开始"这种问题。顶点表示活动的AOV网络适合做拓扑排序判断先后，但算不了工期，关键路径必须用AOE。

2.2 一个能跑出结果的示例网络

光讲概念容易飘，我直接用一个简化版软件项目排期做例子。一共5个事件、6个活动：

V0是项目启动，V4是最终测试交付。注意V4有两个"来源"：一条是V1直接做预研模块单独交付，另一条走V1→V2→V3→V4的完整链条。这就是AOE网络有意思的地方——两条路在抢时间，最终哪条路决定了总工期，正是算法要回答的。

3. 算法核心：ve、vl和"拖不得"的活动

3.1 正向拓扑求ve：最早发生时间

算出网络上所有路径后，第一步是求每个事件的最早发生时间，记作ve（earliest occurrence time）。直觉上很简单：一个事件要发生，它前面所有活动都得完成，所以取所有前驱路径中耗时最大的那个。

计算过程必须沿着拓扑序列走，原因在于：拓扑序保证每个顶点处理时，它的所有前驱都已经处理完了，ve值才可靠。具体递推式是：

ve[j] = max(ve[i] + weight(i, j))，对所有边 i→j 成立，初始时源点ve为0。

拿示例网络来说：ve[0] = 0；ve[1] = 0 + 6 = 6；ve[2] = 6 + 4 = 10；V3有两条入边，1→3给9，2→3给10+7=17，取大17；V4也有两条入边，1→4给6+12=18，3→4给17+3=20，取大20。总工期就是汇点的ve，也就是20天。

3.2 反向拓扑求vl：最迟发生时间

ve是最早，vl是最迟。事件最迟发生时间的意思是：为了不耽误总工期，这个事件最晚什么时候必须完成。计算方向正好反过来，从汇点往源点推，递推式是：

vl[i] = min(vl[j] - weight(i, j))，对所有边 i→j 成立，初始时汇点的vl等于其ve。

为什么取最小？因为从事件i出发可能有多条后续边，每条边都对i有一个"不得晚于"的约束，i必须满足最苛刻的那个。继续算示例：汇点V4的vl=20；V3后续只有3→4，vl[3]=20-3=17；V2后续只有2→3，vl[2]=17-7=10；V1有三条后续边，1→4给20-12=8，1→3给17-9=8，1→2给10-4=6，取最小6；V0后续只有0→1，vl[0]=6-6=0。

反向计算依赖逆拓扑序。因为拓扑序列里汇点永远排最后，倒着遍历天然保证每个顶点处理时，它的所有后继都已经算完。

3.3 松弛时间为零：关键活动的判定

事件的最早和最迟都知道以后，活动就好办了。对于一条边i→j：

• 活动最早开始时间ete（earliest time of edge） = ve[i]，因为i一发生就能开工。
• 活动最迟开始时间lte（latest time of edge） = vl[j] - weight，因为必须在j最迟发生之前把活动干完。
• 松弛时间就是lte - ete。

松弛时间大于0，说明该活动可以晚点开始、可以磨蹭一阵，不影响总工期。松弛时间等于0，说明这个活动一点缓冲都没有，晚了就全线崩溃。这些松弛时间为0的活动串在一起，就是关键路径。

示例网络计算结果我从头验算过：a1的ete=0、lte=0，关键；a3的ete=6、lte=10-4=6，关键；a4的ete=10、lte=17-7=10，关键；a6的ete=17、lte=20-3=17，关键。而a2的lte=17-9=8，ete=6，能松2天；a5的lte=20-12=8，ete=6，也能松2天。四个关键活动正好连成一条拓扑链：a1→a3→a4→a6，也就是"需求分析→方案设计→核心模块开发→整体测试"，总工期20天。项目想压缩工期，只能在这条链上想办法，动a2、a5都没用。

4. C语言数据结构选型：为什么我坚持用邻接表

4.1 邻接表 vs 邻接矩阵的取舍

很多教材图算法默认用邻接矩阵，代码写起来确实直观，两层for循环遍历所有点对。但关键路径在实际使用中涉及的图往往很稀疏——几十个顶点，几十条边，邻接矩阵动辄几百个int的存储，大半都是0，纯属浪费。更重要的是，算法频繁需要"遍历某个顶点的所有出边"，邻接表天然支持这个操作，沿着链表走一遍就行，复杂度只和出度相关。

我自己写的时候用过一次邻接矩阵，原因很实在：V1有三个后继，矩阵里得for j from 0 to n判断是否连通；邻接表里直接拿三个节点挨个处理，代码少、语义清晰，排查问题也痛快。所以这里坚决用邻接表。

4.2 结构体设计与三个辅助数组

我的C语言实现分三层：

• EdgeNode：边的结构体，记录边编号edgeId、终点adjVertex、工期weight、下一条边指针next。
• VertexNode：顶点的结构体，记录入度inDegree和出边链表头指针firstEdge。入度必须存，拓扑排序要反复用，每次现算太蠢。
• Graph：整个图，用固定数组存所有顶点，再加一个vertexNum记录顶点数量。图规模不大时用静态数组最省心，不需要动态分配两重指针。

算法用三个int数组贯穿始终，这是全程序的灵魂：

• ve[]：事件最早发生时间，正向拓扑排序过程中填充。
• vl[]：事件最迟发生时间，逆拓扑序填充。
• topo[]：记录拓扑序列。光有ve不够，算vl必须逆序遍历topo，所以这个序列得存下来。

你可能会问，ve不也能存成顶点结构体的字段吗？可以，但用独立数组更符合"算法辅助数据"的定位，后面freeGraph释放边节点时不涉及数组，逻辑更干净。

5. 手写C代码：从建图到输出关键路径

5.1 建图与入度初始化

建图的第一步是初始化顶点数组，把所有inDegree置0、firstEdge置NULL。然后是addEdge函数，这里有个细节值得注意：我用了尾插法，让出边链表顺序和输入顺序一致，这样后面输出关键活动时长边编号是有序的，肉眼对结果方便。

void addEdge(Graph *g, int from, int to, int weight, int edgeId) { EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode)); e->edgeId = edgeId; e->adjVertex = to; e->weight = weight; e->next = NULL; if (g->vertices[from].firstEdge == NULL) { g->vertices[from].firstEdge = e; } else { EdgeNode *p = g->vertices[from].firstEdge; while (p->next != NULL) { p = p->next; } p->next = e; } g->vertices[to].inDegree++; }

你可能忍不住想用头插法，几个malloc就完事，还少一个while循环。确实省事，但头插会让邻接表完全倒序，比如输入顺序是1→3、1→2、1→4，遍历出边时先看到1→4。算法没错，可你调试时按原始边编号核对数据，输出乱序会非常烦躁。我在真实项目里吃过这个亏，后来统一尾插。

5.2 拓扑排序的同时计算ve

拓扑排序的标准做法是栈或者队列维护入度为0的顶点。栈的好处是实现简单，数组加一个top变量就够。代码里我用静态数组模拟栈，初始把所有入度为0的顶点压栈，然后循环弹栈，每弹出一个顶点v就做两件事：把v记入topo序列，遍历v的所有出边，更新终点的ve，并把终点入度减1，减到0就压栈。

int topoSortAndComputeVe(Graph *g, int *ve, int *topo) { int stack[MAX_VERTEX], top = -1; int count = 0; for (int i = 0; i < g->vertexNum; i++) { ve[i] = 0; if (g->vertices[i].inDegree == 0) { stack[++top] = i; } } while (top != -1) { int v = stack[top--]; topo[count++] = v; EdgeNode *e = g->vertices[v].firstEdge; while (e != NULL) { int u = e->adjVertex; if (ve[v] + e->weight > ve[u]) { ve[u] = ve[v] + e->weight; } g->vertices[u].inDegree--; if (g->vertices[u].inDegree == 0) { stack[++top] = u; } e = e->next; } } return count == g->vertexNum; }

当然，这里遍历出边时，除了更新ve还要扣入度，两个操作放同一个循环里完成就行。注意一点：ve的更新条件必须是>而不是>=，虽然效果一样，但前者逻辑更清晰——一旦出现了更长的路径就更新，别人看代码能立刻明白你是在取最大值。

5.3 逆拓扑序计算vl

算vl前，先把所有顶点初始化为汇点的ve值，也就是总工期。然后从拓扑序列倒数第二个开始往前遍历，对每个顶点v，遍历它的所有出边i→j，用vl[j] - weight尝试更新vl[v]，取最小值。

void computeVl(Graph *g, int *ve, int *vl, int *topo) { int sink = topo[g->vertexNum - 1]; for (int i = 0; i < g->vertexNum; i++) { vl[i] = ve[sink]; } for (int i = g->vertexNum - 2; i >= 0; i--) { int v = topo[i]; vl[v] = ve[sink]; EdgeNode *e = g->vertices[v].firstEdge; while (e != NULL) { int u = e->adjVertex; if (vl[u] - e->weight < vl[v]) { vl[v] = vl[u] - e->weight; } e = e->next; } } }

这里有个隐含的单汇点假设：拓扑序最后一个是唯一汇点。如果图里有多个出度为0的顶点，直接用最后一个顶点当sink是不对的，我在第7节详细说。日常练习和课程设计里，绝大多数数据都是单源单汇，这段代码可以直接用，但作为负责任的实现，你心里得有这根弦。

5.4 判定并输出关键活动

最后一个函数最轻松，遍历所有边，算ete和lte，相等就打印。因为关键活动往往不止一个，我习惯按边编号打印，方便和原始输入对应。

void findCriticalActivities(Graph *g, int *ve, int *vl) { printf("\n关键活动（松弛时间为0）：\n"); for (int v = 0; v < g->vertexNum; v++) { EdgeNode *e = g->vertices[v].firstEdge; while (e != NULL) { int u = e->adjVertex; int ete = ve[v]; int lte = vl[u] - e->weight; if (ete == lte) { printf("活动a%d: V%d -> V%d, 历时%d\n", e->edgeId, v, u, e->weight); } e = e->next; } } }

完整代码里还包含initGraph和freeGraph，前者初始化顶点数组，后者释放所有边节点的内存。跑完程序别忘调用freeGraph，虽然操作系统会回收，但一个动辄几百行、反复malloc的C程序，形成释放习惯能帮你少掉很多内存相关的隐蔽bug。

6. 实测结果分析：用示例网络验证算法

6.1 跑出来的ve/vl表

用第2节的示例数据运行程序，main函数里按顺序把6条边加进去。编译命令很常规：

gcc critical_path.c -o critical_path && ./critical_path

实际输出如下：

拓扑序列: 0 1 2 3 4 顶点最早发生时间ve: V0: 0 V1: 6 V2: 10 V3: 17 V4: 20 顶点最迟发生时间vl: V0: 0 V1: 6 V2: 10 V3: 17 V4: 20 关键活动（松弛时间为0）： 活动a1: V0 -> V1, 历时6 活动a3: V1 -> V2, 历时4 活动a4: V2 -> V3, 历时7 活动a6: V3 -> V4, 历时3 总工期: 20 天

把这个输出和手算结果对比，完全一致。这就是好的算法实现应有的状态——代码跑出来的每一步，都能在手动推导里找到对应。

6.2 关键路径为什么是那一条

再看这个结果，你会发现一个有意思的现象：ve和vl在这个例子里完全相同。这说明其实每个事件都没有任何缓冲空间，V1必须第6天发生，V2必须第10天发生，整条主链锁得很死。而a2、a5这两个活动不算关键，但它们所在的路径也不影响总工期，原因在于它们对应的目标事件V3、V4的最迟时间还有"水位线"可以压。

关键活动a1、a3、a4、a6串起来，就是V0→V1→V2→V3→V4这条唯一的全程关键路径。你想给项目减工期，压缩a2、a5毫无意义，得对a1、a3、a4、a6其中任何一个动刀才见效。这就是关键路径最大的实战价值：它告诉你钱和精力该往哪花。

还有人以为关键路径只有一条，实际图里可能有多条关键路径并存。比如两拨活动都松弛时间为0但走的是不同分支，总工期相同。这种时候任何一条分支上的关键活动延期，总工期都跟着延。输出代码里我只是打印了活动，你如果想把路径整条打印出来，思路是沿着"松弛时间为0的边"做DFS回溯，但要注意别把不同分支串成一条假路径。

7. 真实项目里最容易踩的坑

7.1 有环图：拓扑排序直接给出答案

关键路径建立在DAG（有向无环图）基础上，可现实里的项目依赖偶尔会出现循环引用，比如模块A依赖B、B依赖C、C又依赖A。你要是傻乎乎直接跑程序，拓扑排序count永远到不了vertexNum，代码里我返回0，main函数就会提示"图中有环，无法计算关键路径"。

这个检查非常重要，很多简化实现直接忽略返回值，导致后续ve、vl数组里有垃圾值，输出结果莫名其妙。你的代码里topoSortAndComputeVe最后一句return count == g->vertexNum，就是一道安全闸。在main里判断并友好退出，比debug到半夜才发现是有环强太多了。

7.2 多汇点：vl初始化不能想当然

我前面说了computeVl假设单汇点。可你遇到的实际数据，比如期末考试题或者课程设计给的测试数据，可能不止一个出度为0的顶点。比如一个项目拆成两条完全独立的线，每条线各有各的终点。这时topo[vertexNum - 1]只代表拓扑序里最后那个，另一个终点的ve可能更小，你把所有vl都初始化为这个值，非汇点路径上就会算出错误的vl。

解决办法有两种：一是建图时增加一个超级汇点，把所有出度为0的顶点统一连到超级汇点，边权设0，这样图变成单汇点，原算法不用改；二是在computeVl里先扫描所有出度为0的顶点，取ve最大值当总工期，并且逆序计算时跳过那些没有出边的顶点，或者把它们单独初始化。第二种更通用，我建议正式代码里用这种。

7.3 指针操作与内存管理

C实现图算法，绕不开malloc和free。我的代码里addEdge每次malloc一个新节点，freeGraph负责把这堆节点全部释放掉。有个经验：释放边节点时必须先保存next指针再free，否则你free完当前节点，next指针已经属于一块可能被回收的内存，读它就是未定义行为。

void freeGraph(Graph *g) { for (int i = 0; i < g->vertexNum; i++) { EdgeNode *e = g->vertices[i].firstEdge; while (e != NULL) { EdgeNode *tmp = e; e = e->next; free(tmp); } g->vertices[i].firstEdge = NULL; } }

另外，动态内存不是唯一选择。如果你知道顶点数上限，比如题目保证不超过100个，完全可以用静态数组实现整个邻接表，用int数组模拟指针索引，连malloc都省了。那种写法更适合在线判题系统，能避免内存碎片和泄漏问题。不过那套代码可读性差一些，我日常做课程设计或给别人讲原理时，还是习惯指针版。

最后再提一个实操小技巧：用Valgrind或者AddressSanitizer检查内存问题。编译时加-fsanitize=address -g，运行时有越界、泄漏、重复free都会直接报出来。我每次写完图算法都会跑一遍，比瞪眼找半天强太多了。

友情提醒一句：关键路径算法在真实排期里并不是万能的。它假设资源无限、活动之间只有先后约束没有资源争抢，实际上人力、设备冲突到处都是，算出来的关键路径只能作为基线参考。不过作为理解图论、锻炼C语言指针操作和数据结构的经典题目，它依然是性价比极高的一道练习题。你把这套代码吃透，拓扑排序、邻接表、动态内存、贪心思想基本就都串起来了，应对翁恺老师练习题或者期末卷子里的图算法题，底气会足很多。