企业官网建设流程全解析

先说结论：软考软件设计师的上午题里，图论这几块内容，尤其是最小生成树、拓扑排序、关键路径，属于典型的“看起来都会，一算就错”的题型。很多考友觉得它们不过是数据结构里“图”这一章的三个小应用，随便翻翻就过去了，结果到了考场上要么把Prim和Kruskal的选边逻辑搞混，要么把AOE网四个时间值算得七零八落，白白丢分。

我备考那会儿其实也栽过跟头。后来把这三块的原理、手算步骤、算法实现、考场套路完整梳理了一遍，发现只要形成一套固定的计算范式，它们就是上午题里性价比最高的得分点。这篇文章就是把我整理过的实战经验放出来，从概念到真题，从手算技巧到C语言实现，一次性讲透。不管你是刚开始复习软考中级，还是已经刷完真题准备查漏补缺，这三个算法都值得在考前再过一遍。

1. 图论三大算法：软设考试里“一看就会、一算就错”的送分题

1.1 为什么这三个算法值得你专门花时间

先看考情。软考软件设计师上午题一共75道选择题，数据结构和算法这块大概能占到5到7分，图相关的知识点差不多有1到3分。三选一或三选二出现的频率非常高，基本是年年见。关键是，图论这几分对多数考生来说是可以通过短期强化稳定拿下的，不像哈夫曼树、B树那些需要大量刷题堆积手感。

再看命题方式。最小生成树最常见的考法是给一张带权无向图或者邻接矩阵，让你求最小生成树的权值总和，或者让你判断按Kruskal算法第几步选哪条边。拓扑排序通常是给一个AOV网，让你判断哪个序列不是合法的拓扑序列，或者问图中是否存在环。关键路径则更直接，给出一张AOE网，要求计算事件最早发生时间、活动最迟开始时间，或者判断关键路径的构成。

你会发现，这些题目本质上不考高深理论，考的是手算熟练度和细节把控。也就是说，只要你在考前把计算流程练成肌肉记忆，考场上就能快到飞起。

1.2 看着简单却总丢分的四个原因

我自己复盘过，也帮不少考友诊断过错题，发现大家在这类题丢分的原因高度一致，就是下面四类：

一是概念混淆。比如把AOV网和AOE网搞反，不知道“顶点表示活动”和“边表示活动”的区别。还有人不清楚最小生成树是“带权连通无向图”特有的概念，拿到有向图也下意识去求，那就全错了。

二是手算步骤没有章法。Prim算法选边选到一半，忘了维护“当前已选顶点集合”和“候选边集合”，结果第二条边就选错了。Kruskal算法就更典型，选边时只看权重从小到大，却忘了检查会不会形成环。

三是不理解“解不唯一”。最小生成树的形态可能不唯一，但最小权值总和是唯一的。拓扑序列更是几乎每个图都有多种合法序列，很多人死记一个序列，看到其他选项就慌。

四是关键路径的四个时间值搞混。ve、vl、e、l这四个符号，分别对应事件最早、事件最迟、活动最早、活动最迟。只要有一个口径记错，后面的关键活动判断全完蛋。

这四类问题都是可以通过结构化训练解决的。下面我就按“原理—手算—实现—避坑”的顺序，把三个算法挨个拆开讲。

1.3 不只是为了考试：这三个算法在工程里都是真家伙

学这个还不光是为了应付考试。最小生成树本质上是解决“用最小成本把所有节点连成一个整体”，对应到实际就是通信网络铺设光缆、水电站建输电线路、城市间规划高铁网络，甚至机器学习里基于图的聚类，都能看到它的影子。

拓扑排序解决的是“有依赖关系的任务如何安排执行顺序”。你日常用的构建工具（比如Maven、Gradle）在解析依赖时就是拓扑排序的典型应用，Spring容器的循环依赖检测也是这个原理。当你启动一个大型系统时，如果一开机就报出循环依赖错误，背后就是拓扑排序发现图里有环。

关键路径则直接对应项目管理中的工期估算与资源调度。一个项目最少需要多少天完工？哪些活动一天都不能推迟？如果想压缩工期，应该优先缩短哪条路径上的哪些活动？这些在软考高级科目（比如信息系统项目管理师）里甚至要背公式去算。所以在软设阶段把这部分学透，属于一次投入、长期收益。

2. 最小生成树：Prim和Kruskal，手算十分钟不如套路三分钟

2.1 最小生成树的本质：n个顶点，n-1条边，总权值最小

先建立画面感。假设你们公司要在6个城市之间拉光缆，任意两个城市之间铺设光缆的成本不同，现在要求让所有城市都联网，且总成本最低。这就是最小生成树问题。

形式化地说，给定一个带权连通无向图G=(V, E)，其中|V|=n，最小生成树是一棵包含全部n个顶点、正好n-1条边、并且所有边权之和达到最小的生成树。注意三个关键词：连通、无向、带权。有向图不存在最小生成树，这一点选择题里偶尔会拿来挖坑。

还有一个很容易考的知识点：同一个图的最小生成树形态可能不唯一，但所有最小生成树的权值总和一定相同。如果题目问“最小生成树是否唯一”，那就要看是否存在权值相同的边引起多种选择。

2.2 Prim算法手算套路：每次挑“与当前树相连的最小边”

Prim算法的思想是“从点出发，逐点生长”。随便选一个起始顶点，把它加入已选集合，然后每一次从“连接已选集合和未选集合”的所有边中，挑权值最小的那条边，把对应的新顶点加入已选集合，重复直到所有顶点都被选入。

以我这篇文章要用的示例图为例，顶点为A、B、C、D、E、F，边和权值如下：

• A-B: 6
• A-C: 1
• A-D: 5
• B-C: 5
• B-E: 3
• C-D: 5
• C-E: 6
• C-F: 4
• D-F: 2
• E-F: 6

你画出来是一张很典型的带权图。假设从顶点A开始：

第一轮：已选集合为{A}，候选边有A-B（6）、A-C（1）、A-D（5），最小的是A-C，选中，权值累计1，把C加入集合。

第二轮：已选集合为{A, C}，候选边是所有“一端在集合内、另一端在集合外”的边。A-B（6）、A-D（5）、B-C（5）、C-D（5）、C-E（6）、C-F（4），最小的是C-F（4），选中，权值累计5，把F加入集合。

第三轮：已选集合为{A, C, F}，候选边为A-B（6）、A-D（5）、B-C（5）、C-D（5）、C-E（6）、D-F（2）、E-F（6）。注意D-F虽然是2，权值最小，但D还没被选，所以合法，选中D-F，权值累计7，把D加入集合。

第四轮：已选集合为{A, C, F, D}，现在有的边里，A-B（6）、B-C（5）、C-D（已选节点之间的边不能选）、C-E（6）、E-F（6），最小的是B-C（5），选中，权值累计12，把B加入集合。

第五轮：已选集合为{A, B, C, D, F}，只剩E没选，候选边为B-E（3）、C-E（6）、E-F（6），最小的是B-E（3），选中，权值累计15，所有顶点都进来了，结束。

最小生成树的权值总和是15。按Prim过程，依次选中的边可以是A-C、C-F、D-F、B-C、B-E。你会发现，因为有几条权值相同的边，中间某一步存在多种选法，但总权值不变。

注意：Prim算法每一轮选的边，必须是一端在已选集合、另一端在未选集合。千万不要盯着整个图里权值最小的边就选，那是Kruskal的思路。

2.3 Kruskal算法手算套路：全局按权值排序，选不成环的边

Kruskal算法的思路是“从全局出发，选最小的边，只要不成环就收下”。具体就是：把图中所有边按权值从小到大排序，然后从头开始逐条检查，如果加入这条边后不会形成环，就选它；如果会形成环，就跳过。选到n-1条边时结束。

还用上面这张图做一遍Kruskal：

按权值排序：A-C(1)、D-F(2)、B-E(3)、C-F(4)、A-B(6)先不说，实际上正确排序是A-C(1)、D-F(2)、B-E(3)、C-F(4)、A-D(5)、B-C(5)、C-D(5)、A-B(6)、C-E(6)、E-F(6)。这里有同权重边，顺序可以交换，但不影响最终结果。

• 第一步：A-C，权值1，不成环，收下。
• 第二步：D-F，权值2，不成环，收下。
• 第三步：B-E，权值3，不成环，收下。
• 第四步：C-F，权值4，不成环，收下。注意现在四条边把A、C、D、F、B、E已经牵起来了。
• 第五步：A-D，权值5，如果加入会形成A-C-F-D-A这样的环吗？F-D存在、C-F存在、A-C存在，A-D加进去确实形成环，跳过。
• 第六步：B-C，权值5，加入后不成环，收下。现在已经有5条边，6个顶点全部连通，结束。

累计权值：1 + 2 + 3 + 4 + 5 = 15。结果和Prim一样。

Kruskal在手算时最怕的就是“画着画着就蒙了”。我的建议是每选一条边，就在原图上用不同颜色标出来，然后专门检查这条边会不会和已有的边构成回路。尤其是当图里顶点较多、边也较多的时候，宁可多花十秒钟检查回路，也不要事后返工。

2.4 两种算法怎么选，以及考场上的高频坑

从时间复杂度的角度说，Prim算法（使用邻接矩阵实现）是O(V^2)，适合稠密图；Kruskal算法主要开销在排序上，是O(E log E)，适合稀疏图。软考上午题很少直接考复杂度，但下午题选算法设计策略时可能碰到，记住“稠密Prim、稀疏Kruskal”就够了。

代码层面，最小生成树的经典实现值得写一遍。用教材里最常见的邻接矩阵加lowcost数组就能实现Prim：

#define INF 0x3f3f3f3f #define N 100 int graph[N][N], lowcost[N]; int visited[N]; int n; int prim(int start) { int sum = 0; for (int i = 0; i < n; i++) { lowcost[i] = graph[start][i]; visited[i] = 0; } visited[start] = 1; for (int i = 1; i < n; i++) { int min = INF, k = -1; for (int j = 0; j < n; j++) { if (!visited[j] && lowcost[j] < min) { min = lowcost[j]; k = j; } } if (k == -1) return -1; // 不连通，不存在最小生成树 sum += min; visited[k] = 1; for (int j = 0; j < n; j++) { if (!visited[j] && graph[k][j] < lowcost[j]) { lowcost[j] = graph[k][j]; } } } return sum; }

Kruskal的实现要配合并查集，核心代码思路如下：

typedef struct { int u, v, w; } Edge; int parent[N]; int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; } int union_vertices(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return 0; parent[rx] = ry; return 1; } int kruskal(Edge edges[], int m, int n) { sort(edges, edges + m, cmp); // 按w升序 for (int i = 0; i < n; i++) parent[i] = i; int sum = 0, count = 0; for (int i = 0; i < m; i++) { if (union_vertices(edges[i].u, edges[i].v)) { sum += edges[i].w; count++; if (count == n - 1) break; } } return count == n - 1 ? sum : -1; }

考场上如果出了“Kruskal第几步选哪条边”这种题，我的建议是老老实实按权值排序后在草稿纸上列一个表，每选一条边就在表里做一次成环检查。只要你习惯了这个流程，3分钟之内一定能算完。真正让你失分的不是计算量，而是跳过检查直接选边，结果中了“成环陷阱”。

3. 拓扑排序：把“谁先谁后”理清楚，考的不是算法是细心

3.1 AOV网与拓扑序列：活动之间谁必须先做

拓扑排序处理的是有向无环图（DAG），具体场景就是AOV网——用顶点表示活动，用有向边表示活动之间的先后约束。比如做软件项目，需求分析完成后才能做设计，设计完成后才能编码，这种“做完X才能做Y”的约束关系，用一张AOV网表示就非常直观。

拓扑排序的全部意义，就是把这些带约束的活动排成一个线性序列，使得对图中任意一条有向边u→v，顶点u在序列里都必须出现在v之前。这样的序列就叫拓扑序列。

两个关键性质你一定要记住：

第一，拓扑序列不一定唯一。只要某个时刻有多个入度为0的顶点，选择任何一个作为下一个输出顶点都是合法的。因此，一个DAG往往存在多个拓扑序列。

第二，一个图存在拓扑序列的充要条件是它是有向无环图。如果图里有环，就意味着存在一组活动形成了循环依赖，谁也不愿意先执行，拓扑排序自然排不出来。考试里经常有一道判断题，问“以下哪个图不存在拓扑序列”，本质就是在问“哪个图有环”。

3.2 手算拓扑排序：删掉入度为0的顶点，循环往复

手算拓扑排序有一套非常固定且稳妥的流程：

第一步，扫描所有顶点，找出当前入度为0的顶点。如果没有入度为0的顶点，说明图中存在环，直接判定无拓扑序列。

第二步，输出这个顶点，然后把它所有出边都删掉。删边会引起它指向的顶点入度减少。

第三步，重复第一步和第二步，直到所有顶点都输出，或者找不到入度为0的顶点为止。

用一张具体的AOV网来演示。假设有6个顶点和这样的依赖关系：

• V1 → V2（V2依赖V1）
• V1 → V3（V3依赖V1）
• V2 → V4（V4依赖V2）
• V3 → V4（V4依赖V3）
• V3 → V5（V5依赖V3）
• V4 → V6（V6依赖V4）
• V5 → V6（V6依赖V5）

初始入度：V1是0，V2是1，V3是1，V4是2，V5是1，V6是2。

第一轮，入度为0的顶点只有V1，输出V1，删掉V1→V2和V1→V3，于是V2入度变0，V3入度变0。

第二轮，入度为0的顶点有V2和V3，可以选择V2，输出V2，删掉V2→V4，V4入度从2变1。此时剩余顶点V3（入度0）、V4（入度1）、V5（入度1）、V6（入度2）。

第三轮，输出V3，删掉V3→V4和V3→V5，V4入度变0，V5入度变0。

第四轮，输出V4或V5都可以。假设输出V4，删掉V4→V6，V6入度从2变1。

第五轮，输出V5，删掉V5→V6，V6入度变0。

第六轮，输出V6。

得到的拓扑序列是V1、V2、V3、V4、V5、V6。刚才第二轮如果先选V3，还能得到另一个合法序列V1、V3、V2、V5、V4、V6。这正好说明了拓扑序列不唯一。

考场上经常反过来出题，给你四个序列，问你哪个不是合法拓扑序列。这时不要真的把四个序列都验一遍，而是用排除法：先看序列里有没有违背某条直接依赖关系的。比如如果序列里V4出现在V2和V3之前，那必然不合法，因为这个图明确要求V4必须在V2和V3之后。

提示：手算时推荐在草稿纸上把每个顶点的当前入度列成一行，每次删掉入度为0的顶点后，只更新受影响顶点的入度，而不是重新去数整张图。这个方法能大幅降低出错率。

3.3 Kahn算法实现与复杂度：队列+BFS思路

拓扑排序的经典实现是Kahn算法。思想跟手算完全一致：借助队列维护当前入度为0的顶点，依次出队，删边，更新入度，再把新出现的入度为0顶点入队。以下是C语言实现的核心部分：

#define MAXN 105 int n, m; int indegree[MAXN]; int graph[MAXN][MAXN]; void topological_sort() { int q[MAXN], head = 0, tail = 0; for (int i = 1; i <= n; i++) { if (indegree[i] == 0) { q[tail++] = i; } } int count = 0; while (head < tail) { int u = q[head++]; printf("%d ", u); count++; for (int v = 1; v <= n; v++) { if (graph[u][v]) { indegree[v]--; if (indegree[v] == 0) { q[tail++] = v; } } } } if (count < n) { printf("存在环，无法完成拓扑排序\n"); } }

这里有个细节值得注意：如果最后输出的顶点数量小于总顶点数，说明图里有环。我把这个判断写在了代码末尾，因为考场上如果遇到“求拓扑序列是否能覆盖所有顶点”的变体题，本质就是检查count是否等于n。

Kahn算法的时间复杂度是O(V+E)，空间复杂度O(V)。这是一种线性时间算法，非常高效。

3.4 从拓扑排序到工程实践：为什么循环依赖这么招人恨

你可能好奇，学拓扑排序到底有什么用？最典型的例子就是构建工具。Maven在编译项目时，需要知道各模块之间的依赖关系，它内部维护的依赖图本质上就是AOV网，然后通过拓扑排序确定模块编译的先后顺序。如果pom.xml里A依赖B、B又依赖A，编译就会失败，报错信息通常就是“发现循环依赖”。你掌握了拓扑排序，理解这种错误就特别容易：循环依赖意味着图里有环，拓扑排序根本排不出来。

另外，拓扑排序在软考里还常和关键路径联动。如果你给AOV网的每个活动加上持续时间，让权值待在边上，AOV网就变成了AOE网，拓扑排序得到的顺序就变成后续计算事件最早发生时间的基础。所以，学拓扑排序不只是为了单独应付一道题，它还是关键路径计算的前置步骤。

4. 关键路径：AOE网四组值的完整手算流程

4.1 AOE网与关键路径：边表示活动，顶点表示事件

AOE网（Activity On Edge Network）用的是另一种建模方式：顶点表示事件，边表示活动，边的权值表示活动持续的时间。事件本身不消耗时间，它只是表示“到达这个状态”的时刻。

举个例子，V1表示项目开始，V7表示项目结束，从V1到V7的所有路径中，哪条路径的总耗时最长，它就决定了整个项目最短需要多少天完工，这条路径就是关键路径。

关键路径上所有的活动都叫关键活动。关键活动有一个重要特征：完全没有机动余地，活动最早开始时间等于活动最迟开始时间。只要关键活动延误一天，整个项目就延误一天。

软考对AOE网的考法集中在四组值：事件最早发生时间ve、事件最迟发生时间vl、活动最早开始时间e、活动最迟开始时间l。接下来我结合具体图完整算一遍。

4.2 四组值的定义与计算顺序：先拓扑序正向，再逆拓扑序反向

ve(j)：顶点Vj所代表事件能够发生的最早时间。它的计算方式是从源点出发，按拓扑顺序正向推导。源点V1的ve是0。对于任意顶点Vj，ve(j)=max{ve(i)+w(i,j)}，其中i是Vj的所有前驱，w(i,j)是活动(i,j)的持续时间。为什么取max？因为一个事件只有当它所有前驱活动都完成时才能发生，所以取最大值。

vl(j)：顶点Vj所代表事件在不拖延整个工期的前提下，最晚可以发生的时间。它的计算方式是从汇点反向推导。汇点Vn的vl等于它的ve。对于任意顶点Vi，vl(i)=min{vl(j)-w(i,j)}，其中j是Vi的所有后继。为什么取min？因为如果某个后继活动已经压到了最晚开始时间，前驱事件再迟就会拖累整个项目，所以要取最小值。

e(i)：活动i的最早开始时间。如果活动i是从顶点u到顶点v的边，那么e(i)=ve(u)，因为只有事件u发生了，这条活动才能开始。

l(i)：活动i的最迟开始时间。l(i)=vl(v)-w(u,v)，也就是说，活动最迟必须在事件v最迟发生前完成，减去活动本身耗时，就是它最迟开始的时间。

当l(i)=e(i)时，说明活动没有一点空余时间，它就是关键活动。所有关键活动连成的路径就是关键路径。另外，l(i)-e(i)的值也叫活动的松弛时间，表示这个活动最多可以推迟多久而不影响整个项目。

4.3 完整手算一个AOE网：7个顶点9条边的全过程

我用一张经典的AOE网来做完整演示，顶点记作V1到V7，9条活动边如下：

• a1: V1→V2，耗时5
• a2: V1→V3，耗时6
• a3: V1→V4，耗时3
• a4: V2→V5，耗时3
• a5: V3→V5，耗时6
• a6: V3→V6，耗时3
• a7: V4→V6，耗时4
• a8: V5→V7，耗时1
• a9: V6→V7，耗时4

这张图有两条主要分支：V1→V3→V5→V7 和 V1→V3→V6→V7，还有两条较短的支路。咱们先按正拓扑序算ve。

ve(V1)=0 ve(V2)=ve(V1)+5=5 ve(V3)=ve(V1)+6=6 ve(V4)=ve(V1)+3=3 ve(V5)=max(ve(V2)+3=8, ve(V3)+6=12)=12 ve(V6)=max(ve(V3)+3=9, ve(V4)+4=7)=9 ve(V7)=max(ve(V5)+1=13, ve(V6)+4=13)=13

所以整个项目最短工期是13，这个数字就是汇点V7的ve。

接着按逆拓扑序反向算vl。先把汇点V7的vl设为13。

vl(V7)=13 vl(V6)=vl(V7)-4=9 vl(V5)=vl(V7)-1=12 vl(V4)=vl(V6)-4=5 vl(V3)=min(vl(V5)-6=6, vl(V6)-3=6)=6 vl(V2)=vl(V5)-3=9 vl(V1)=min(vl(V2)-5=4, vl(V3)-6=0, vl(V4)-3=2)=0

到这里ve和vl就全出来了。然后算每个活动的e和l，我用一张表汇总：

看出来了吗？l-e等于0的活动正好是a2、a5、a6、a8、a9，它们连成的路径有两条：V1→V3→V5→V7 和 V1→V3→V6→V7，总耗时都是13。这两条就是关键路径。关键活动并不只落在一条路径上，这是很多初学者容易踩的坑。

注意：关键路径上的活动一定是关键活动，但整个项目的关键路径可能不止一条。只要a2这种公共活动延误一天，两条关键路径都会延误，项目整体就会延误。如果要缩短工期，一定要优先压缩“所有关键路径的公共部分”，而不是随便抓一个关键活动就压。

4.4 代码级别的实现思路：拓扑序DP求ve，逆拓扑序DP求vl

前面说了，ve的计算本质上是按拓扑顺序做动态规划，vl是按逆拓扑顺序做动态规划。所以代码实现可以非常干净。第一步对AOE网做拓扑排序并保存拓扑序列；第二步按拓扑序列正向遍历，对每条边u→v执行ve[v]=max(ve[v], ve[u]+w)；第三步按逆拓扑序列反向遍历，对每条边u→v执行vl[u]=min(vl[u], vl[v]-w)；第四步对每条活动边u→v计算e=ve[u]，l=vl[v]-w，判断e是否等于l。

伪代码如下：

topoOrder = topologicalSort(vertices, edges) // 正向求ve for each u in topoOrder: for each edge(u, v, w): ve[v] = max(ve[v], ve[u] + w) // 反向求vl vl[汇点] = ve[汇点] for each u in reverse(topoOrder): for each edge(u, v, w): vl[u] = min(vl[u], vl[v] - w) // 求活动e和l并判断关键活动 for each edge(u, v, w): e = ve[u] l = vl[v] - w if e == l: mark as critical activity

整个算法的时间复杂度是O(V+E)，空间复杂度也是O(V+E)。软考下午题一般不会让你直接写这个代码，但上午题经常考这些时间值的计算结果，所以手算流程一定要滚瓜烂熟。

4.5 关键路径的常见失分点：三道送命题的自检清单

我总结了三个考场上反复出现的错误，你复习时候一定要对着自检：

第一，ve和vl的计算方向搞反。ve从源点往汇点推，取的是max；vl从汇点往源点推，取的是min。很多同学把所有值都按max推，结果vl全变大，l-e自然全错。记住一句话：最早是从前往后取大，最迟是从后往前取小。

第二，把活动的e当成ve的起点值就直接用，忘记了l还要减活动耗时。你要是拿ve(arrive)当l去判断，那几乎所有活动都成了关键活动，因为区别全被忽略了。

第三，深挖一点点：如果要压缩工期，不能只看单个关键活动。因为可能有多条关键路径，如果它们不共享某个可压缩的活动，那么只压缩其中一条上的活动，工期不会变短。软考高级科目里这个点还会被扩展成“工期优化”问题，所以在软设阶段就要建立“所有关键路径公共部分才最值得压缩”的直觉。

说到底，关键路径题的难点不是算，而是别把定义和方向搞乱。一张表格按顺序把9条活动捋一遍，分数就到手了。

5. 真题视角：三大算法的考场应对与延伸价值

5.1 三种题型的“标准动作”总结

软考上午题是选择题，每题作答时间平均只有90秒左右。想在90秒内稳定输出，必须形成条件反射级别的标准动作。

遇到最小生成树题，先判断题目给的是Prim还是Kruskal。如果给的是邻接矩阵，通常用Prim从低序号顶点开始；如果给的是边集合或让你按权值排序选边，就用Kruskal。做题时在草稿纸上画一张小表，列轮次、候选最小边、累计权值三项，不要直接在选项里猜。

遇到拓扑排序题，第一件事就是检查图里有没有环。如果题目问“哪个不是拓扑序列”，那就先把图中能确定的直接依赖关系写出来，用排除法筛选项。如果题目问“可能的拓扑序列”，那就老老实实手算，但不必把完整序列算完，只需要验证选项是否符合每一步“当前入度为0”的要求即可。

遇到关键路径题，直接按ve正推、vl反推、e与l逐条算的顺序走表格。做题时不要试图心算，在草稿纸上画一张和我的示例一样的二线表，逐行填，又快又准。

5.2 考前三天怎么速记这三个算法

到了考前冲刺阶段，再去看繁琐的推导不如做减法。我最后一轮复习的方法是把三个算法的核心浓缩成三句话：

最小生成树：Prim从点生长，Kruskal从边生长；选n-1条边，不构成环，总权值最小。

拓扑排序：不停删去入度为0的顶点；删不完就有环；序列可能不唯一。

关键路径：ve是从前往后取大，vl是从后往前取小；e是起点的ve，l是终点的vl减耗时；l-e等于0的活动就是关键活动。

这三句话你在进考场前默背一遍，基本能把概念题的分拿到。剩下就是靠表格手算流程保底。

5.3 从软设到高项：这部分内容能帮你走得更远

软考软件设计师属于中级科目，图论考到关键路径计算一般就到“找关键路径、判断关键活动”为止。但如果你之后计划考信息系统项目管理师或者系统分析师，关键路径法就会从选择题变成案例分析题和计算题里的重要考点，要算总工期、算总时差、算自由时差，还要做工期压缩和资源优化。

所以我的建议是，在软设阶段就把AOE网的逻辑吃透，尤其是“事件最早/最迟发生时间”与“活动最早/最迟开始时间”的关系。等你后面学到项目进度网络图时，会发现整个知识体系是贯通的。最小生成树和拓扑排序也一样，前者在通信网络设计里高频出现，后者在软件架构和依赖管理里无处不在。

还有一个贴近实战的细节：软考下午题的数据结构算法题历年很少直接考“写一个完整的Prim或Kruskal”，但会考一些基于图遍历的算法设计，很多思路和最小生成树是一致的。你把图论的底层逻辑学扎实了，下午题遇到任何图的变体都能更快反应过来。

5.4 我踩过的坑：关于这三大算法复习的几点体会

最后聊点备考体会，可能比那些表格对你更有用。

第一个坑是只刷题不看原理。拓扑排序和关键路径这类题，如果你只是背题，碰到稍微变形的图就发懵。我复习第二轮时把三个算法的原理讲给一个完全不懂的同学听，讲的过程中才发现自己还有几个地方说不清楚，比如vl为什么要取min。能把别人讲明白，才算真的会了。

第二个坑是手算时图省事跳步骤。最小生成树的Kruskal算法如果你不写“是否成环”的判断步骤，极容易在权值相同的边那里踩坑。我见过有考友在模拟考时一口气选了三条权值一样的边，最后发现成环只能全盘重来，时间全浪费了。

第三个坑是忽略表格化的计算习惯。软考上午题要在这么短时间里保持计算准确率，草稿纸上的格式很重要。我后期练题，不管题多简单，都坚持把ve、vl、e、l四行表格画出来。这个习惯帮我保证了正确率，也让我养成了稳定的考场节奏。

说到底，最小生成树、拓扑排序、关键路径这三块内容是软考软件设计师考试里实实在在的“性价比之王”。它们不像编译原理那样需要大量记忆，也不像算法复杂度那样需要很强的数学直觉，只要你把原理理解到位、把手算流程练熟，拿到这几分几乎是板上钉钉的事。希望这篇文章能帮你扫清图论这部分最后的盲区，考场上遇到它们时，心里只有一个词：稳了。