图论算法
Edexcel 国际A-Level 数学· D1 §2.1, D1 §2.2 (2018 考纲第3版)· 25 分钟阅读
1. 求最小生成树的克鲁斯卡尔算法★★☆☆☆⏱ 5 min
✓ 计算器
克鲁斯卡尔算法
贪心算法，将所有边按权重升序排序后依次添加边，跳过任何会形成环的边，直到所有顶点都被连接，最终构造出最小生成树（MST）。
例:
对于一个有5个顶点的图，克鲁斯卡尔算法会选出4条边构成不含环的最小生成树。
求下图的最小生成树及其总权重：顶点为A、B、C、D，边为AB=3、AC=5、BC=1、BD=4、CD=2。
- 1
步骤1：将所有边按权重升序排序：BC(1)、CD(2)、AB(3)、BD(4)、AC(5)
- 2
步骤2：添加BC（权重1）：顶点B和C连通，没有形成环
- 3
步骤3：添加CD（权重2）：顶点B、C、D连通，没有形成环
- 4
步骤4：添加AB（权重3）：4个顶点全部连通，算法终止
- 5
步骤5：最小生成树总权重 = 1 + 2 + 3 = 6，选中的边为BC、CD、AB
2. 求最小生成树的普里姆算法★★★☆☆⏱ 7 min
✓ 计算器
普里姆算法
贪心算法，从任意选定的顶点出发构建最小生成树，每次添加连接现有树内顶点和树外顶点的权重最小边，直到所有顶点都被纳入树中。该算法可以直接在网络示意图上执行，也可以基于邻接矩阵执行。
例:
对于4个顶点的图，普里姆算法会添加3条边，生成一棵合法的无环最小生成树。
从顶点A出发，使用矩阵版普里姆算法，求以下邻接矩阵对应的图的最小生成树：行/列顺序为A、B、C、D，A行：-、3、5、-；B行：3、-、1、4；C行：5、1、-、2；D行：-、4、2、-。
- 1
步骤1：从A出发，划去A行。未加入树的顶点对应列中的最小值为3（边AB），添加AB，权重为3
- 2
步骤2：划去B行。未加入树的顶点对应列中的最小值为1（边BC），添加BC，权重为1
- 3
步骤3：划去C行。未加入树的顶点对应列中的最小值为2（边CD），添加CD，权重为2
- 4
步骤4：4个顶点全部加入，最小生成树总权重 = 3 + 1 + 2 = 6，和克鲁斯卡尔算法的结果一致
3. 网络和邻接矩阵的相互转换★★☆☆☆⏱ 4 min
✓ 计算器
Edexcel经常要求你先将图示意图转换为邻接矩阵，或者根据矩阵绘制网络，之后再应用普里姆算法。对于无向图，邻接矩阵是对称矩阵，对角线上的元素为短横线或∞（顶点到自身不存在边），两个顶点之间没有边的位置也填短横线或∞。
将之前克鲁斯卡尔算法例题中的4顶点网络转换为邻接矩阵。
- 1
步骤1：按相同顺序标记行和列为A、B、C、D
- 2
步骤2：将对角线元素填为"-"，因为不存在自环边
- 3
步骤3：填入每对顶点之间的边权重：AB=3、AC=5、BC=1、BD=4、CD=2
- 4
步骤4：将剩余的AD位置填为"-"，因为A和D之间没有边。最终得到的矩阵和普里姆矩阵例题中使用的矩阵完全相同。
4. 求最短路径的戴克斯特拉算法★★★★☆⏱ 8 min
✓ 计算器
戴克斯特拉算法
贪心算法，在所有边权重非负的图中，求出从单个起点顶点到其余所有顶点的最短路径。算法使用临时标签记录暂定距离，确认到该顶点的最短距离后，将临时标签更新为永久标签。
例:
戴克斯特拉算法可以用来求地图上两个城镇之间的最短行车路线，其中边代表道路，权重代表通行时间。
在下图中使用戴克斯特拉算法求从A到D的最短路径：A连接B（权重3）、A连接C（权重5）；B连接C（权重1）、B连接D（权重4）；C连接D（权重2）。
- 1
步骤1：给A标注永久距离0。临时标签：B=3、C=5、D=∞
- 2
步骤2：选择最小的临时标签B=3，标记为永久。更新相邻顶点：C = min(5, 3+1=4) → 4；D = min(∞, 3+4=7) →7
- 3
步骤3：选择最小的临时标签C=4，标记为永久。更新相邻顶点D = min(7, 4+2=6) →6
- 4
步骤4：选择最小的临时标签D=6，标记为永久。所有顶点处理完毕。最短路径：A→B→C→D，总权重为6。
5. 常见陷阱
错误做法:
在克鲁斯卡尔算法中添加会形成环的边
原因:
边按权重排序后，你必须检查边的两个顶点是否已经连通。添加成环边会不必要地增大总权重，得到无效的最小生成树。
正确做法:
排序完所有边之后，添加每条边之前先检查它的两个端点是否属于不同的连通分量。演算过程中要明确标注跳过的边，方便阅卷老师判分。
错误做法:
使用矩阵版普里姆算法时忘记划去已加入顶点对应的行
原因:
如果不划去已经加入树的顶点对应的行，你可能会误选连接两个已经在树内的顶点的边，从而形成环。
正确做法:
每将一个顶点加入最小生成树，立刻在邻接矩阵中划去它对应的行，之后再选择下一条最小边。
错误做法:
戴克斯特拉算法刚给终点打上标签就停止，没有确认该标签是永久标签
原因:
临时标签之后可能通过其他顶点找到更短的路径，从而被更新为更小的值。
正确做法:
只有当目标顶点获得永久标签，或者所有顶点都处理完毕时，才能终止戴克斯特拉算法。
错误做法:
在存在负权重边的图上使用戴克斯特拉算法
原因:
戴克斯特拉算法并非为负权重场景设计，如果图中存在负边，算法会返回错误的最短路径结果。
正确做法:
应用戴克斯特拉算法之前确认所有边的权重都是非负的，Edexcel D1考试的所有相关题目都满足这个要求。
错误做法:
答题时没有列出边/顶点的选择顺序
原因:
即使你后续出现小的计算错误，Edexcel也会为正确的选择顺序给过程分。跳过这一步会白白丢失容易拿到的分数。
正确做法:
对于克鲁斯卡尔/普里姆算法，始终按选择顺序清晰写出边的列表；对于戴克斯特拉算法，按顺序写出永久标签的列表。
6. 速查表
算法 | 适用场景 | 核心步骤 | 考试要求 |
|---|---|---|---|
克鲁斯卡尔 | 求最小生成树 |
| 按选择顺序列出边，标注因成环跳过的边 |
普里姆（网络版） | 求最小生成树 |
| 展示顶点/边的添加顺序 |
普里姆（矩阵版） | 从邻接矩阵求最小生成树 |
| 展示每一步划去的行 |
戴克斯特拉 | 求两个顶点之间的最短路径 |
| 展示所有临时/永久标签，写出最终路径和总权重 |
7. 常见问题
考试中做图算法题必须写出全部演算过程吗？
是的，Edexcel的评分标准给每一步都设置了分数：边/顶点的选择顺序、戴克斯特拉算法中临时/永久标签的标注、克鲁斯卡尔算法中环的检查过程都有对应分值。即使最终答案正确，跳过步骤也会失分。
如果题目没有指定使用矩阵版普里姆算法，我可以用网络版普里姆算法答题吗？
可以，除非题目明确要求使用矩阵法，否则两种版本的普里姆算法都可以使用。只要演算过程正确，两种方法得到的最小生成树完全一致。
深入阅读
下一步
现在你已经掌握了Edexcel IAL D1的核心图算法，可以开始学习更进阶的决策数学内容。接下来你将学习路径检验问题和旅行商问题，这些内容都建立在你已经练习过的图论逻辑之上。你还应该多做这些算法相关的历年真题，提升解题速度和准确率，这类题目几乎出现在每一份D1试卷中，占卷面总分的15%-25%。请务必遵循Edexcel要求的演算格式，避免丢失过程分。