1. 从一个排期翻车现场说起为什么必须算关键路径去年我接了个内部工具的小项目功能拆完大概七八个模块大家估完都觉得两周肯定能干完。结果到了第十三天核心模块还在联调整个组干到凌晨两点最后还是延期两天交付。复盘的时候发现一个问题所有人都盯着要做的活但没有人算过哪条链路决定总工期。你要是也在学AOE网络、准备数据结构的课程设计或者刷到翁恺老师C语言练习题里那几道图算法题那关键路径就是绕不开的一关。我个人的体会是用C语言亲手实现一遍远比在草稿纸上画图理解得深。因为你要自己处理建图、拓扑排序、正向推最早时间、反向推最迟时间还要把哪些活动一秒钟都不能拖正确打印出来每一个环节都含糊不得。这篇文章从为什么要算讲起然后用一个具体的项目排期例子把AOE网络建模、ve/vl计算、关键活动判定完整走一遍最后给出可以直接跑的C语言代码并附上我实测中踩过的几个坑。代码基于标准Cstdio.h、stdlib.h编写适合正在学数据结构的同学当答案加理解手册用。2. 先把项目排期翻译成一张AOE网络2.1 事件、活动和权值的分工关键路径算法处理的对象叫AOE网络Activity On Edge也就是边表示活动的带权有向图。乍一听有点绕其实拆开看很简单顶点代表事件某个时间点前面的活都干完了后面的活可以开始。比如需求评审通过是一个事件编码完成也是一个事件。有向边代表活动从一个事件到另一个事件的整个动作比如从需求完成到编码完成之间有一条边表示编码这个动作。边上的权值代表活动持续时间单位可以是天、小时无所谓只要统一就行。为什么要用边表示活动而不是顶点表示活动因为网络计划里一个关键信息是先后约束编码必须在需求完成之后测试必须在编码之后。用边把事件串起来每个活动有了明确的起点事件和终点事件你才好回答某件事最晚什么时候开始这种问题。顶点表示活动的AOV网络适合做拓扑排序判断先后但算不了工期关键路径必须用AOE。2.2 一个能跑出结果的示例网络光讲概念容易飘我直接用一个简化版软件项目排期做例子。一共5个事件、6个活动活动内容起点事件终点事件工期天a1需求分析V0开始V1需求完成6a2业务模块开发V1V3编码完成9a3方案设计V1V2设计完成4a4核心模块开发V2V37a5预研模块单独交付V1V4测试交付12a6整体测试V3V43V0是项目启动V4是最终测试交付。注意V4有两个来源一条是V1直接做预研模块单独交付另一条走V1→V2→V3→V4的完整链条。这就是AOE网络有意思的地方——两条路在抢时间最终哪条路决定了总工期正是算法要回答的。3. 算法核心ve、vl和拖不得的活动3.1 正向拓扑求ve最早发生时间算出网络上所有路径后第一步是求每个事件的最早发生时间记作veearliest occurrence time。直觉上很简单一个事件要发生它前面所有活动都得完成所以取所有前驱路径中耗时最大的那个。计算过程必须沿着拓扑序列走原因在于拓扑序保证每个顶点处理时它的所有前驱都已经处理完了ve值才可靠。具体递推式是ve[j] max(ve[i] weight(i, j))对所有边 i→j 成立初始时源点ve为0。拿示例网络来说ve[0] 0ve[1] 0 6 6ve[2] 6 4 10V3有两条入边1→3给92→3给10717取大17V4也有两条入边1→4给612183→4给17320取大20。总工期就是汇点的ve也就是20天。3.2 反向拓扑求vl最迟发生时间ve是最早vl是最迟。事件最迟发生时间的意思是为了不耽误总工期这个事件最晚什么时候必须完成。计算方向正好反过来从汇点往源点推递推式是vl[i] min(vl[j] - weight(i, j))对所有边 i→j 成立初始时汇点的vl等于其ve。为什么取最小因为从事件i出发可能有多条后续边每条边都对i有一个不得晚于的约束i必须满足最苛刻的那个。继续算示例汇点V4的vl20V3后续只有3→4vl[3]20-317V2后续只有2→3vl[2]17-710V1有三条后续边1→4给20-1281→3给17-981→2给10-46取最小6V0后续只有0→1vl[0]6-60。反向计算依赖逆拓扑序。因为拓扑序列里汇点永远排最后倒着遍历天然保证每个顶点处理时它的所有后继都已经算完。3.3 松弛时间为零关键活动的判定事件的最早和最迟都知道以后活动就好办了。对于一条边i→j活动最早开始时间eteearliest time of edge ve[i]因为i一发生就能开工。活动最迟开始时间ltelatest time of edge vl[j] - weight因为必须在j最迟发生之前把活动干完。松弛时间就是lte - ete。松弛时间大于0说明该活动可以晚点开始、可以磨蹭一阵不影响总工期。松弛时间等于0说明这个活动一点缓冲都没有晚了就全线崩溃。这些松弛时间为0的活动串在一起就是关键路径。示例网络计算结果我从头验算过a1的ete0、lte0关键a3的ete6、lte10-46关键a4的ete10、lte17-710关键a6的ete17、lte20-317关键。而a2的lte17-98ete6能松2天a5的lte20-128ete6也能松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代码里我返回0main函数就会提示图中有环无法计算关键路径。这个检查非常重要很多简化实现直接忽略返回值导致后续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检查内存问题。编译时加-fsanitizeaddress -g运行时有越界、泄漏、重复free都会直接报出来。我每次写完图算法都会跑一遍比瞪眼找半天强太多了。友情提醒一句关键路径算法在真实排期里并不是万能的。它假设资源无限、活动之间只有先后约束没有资源争抢实际上人力、设备冲突到处都是算出来的关键路径只能作为基线参考。不过作为理解图论、锻炼C语言指针操作和数据结构的经典题目它依然是性价比极高的一道练习题。你把这套代码吃透拓扑排序、邻接表、动态内存、贪心思想基本就都串起来了应对翁恺老师练习题或者期末卷子里的图算法题底气会足很多。