# 图论算法

> Edexcel 国际A-Level 数学 · IAL 数学 D1
> 来源: https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-algorithms-on-graphs/

本指南讲解Edexcel IAL D1要求的三种核心图算法：克鲁斯卡尔算法、普里姆算法（含网络版和矩阵版）、戴克斯特拉算法。你将完成多道考试风格例题，掌握符合评分标准的答题呈现方式，确保拿到全部分数。

**先修:** [基础图论术语（顶点、边、权重、环）](https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-graph-terminology/)

## 学习目标

- 应用克鲁斯卡尔和普里姆算法求加权网络的最小生成树
- 使用邻接矩阵表示正确执行普里姆算法
- 在图网络示意图和邻接矩阵之间完成相互转换
- 应用戴克斯特拉算法在非负权重图中求两个顶点之间的最短路径
- 按照Edexcel考试评分标准要求，按顺序呈现边/顶点选择过程和全部演算步骤

## 求最小生成树的克鲁斯卡尔算法

**克鲁斯卡尔算法** — 贪心算法，将所有边按权重升序排序后依次添加边，跳过任何会形成环的边，直到所有顶点都被连接，最终构造出最小生成树（MST）。

*例:* 对于一个有5个顶点的图，克鲁斯卡尔算法会选出4条边构成不含环的最小生成树。

> **tip**
>
> Edexcel要求你按选择顺序列出所有边，并且明确说明为了避免环而跳过的边，才能拿到全部过程分。

**例题:** 求下图的最小生成树及其总权重：顶点为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

*计算器:* allowed

## 求最小生成树的普里姆算法

**普里姆算法** — 贪心算法，从任意选定的顶点出发构建最小生成树，每次添加连接现有树内顶点和树外顶点的权重最小边，直到所有顶点都被纳入树中。该算法可以直接在网络示意图上执行，也可以基于邻接矩阵执行。

*例:* 对于4个顶点的图，普里姆算法会添加3条边，生成一棵合法的无环最小生成树。

> **info**
>
> 使用矩阵版普里姆算法时，每将一个顶点加入树中就划去它对应的行，之后每一步从剩余未划去的列中选择最小值即可。

**例题:** 从顶点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，和克鲁斯卡尔算法的结果一致

*计算器:* allowed

## 网络和邻接矩阵的相互转换

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之间没有边。最终得到的矩阵和普里姆矩阵例题中使用的矩阵完全相同。

*计算器:* allowed

## 求最短路径的戴克斯特拉算法

**戴克斯特拉算法** — 贪心算法，在所有边权重非负的图中，求出从单个起点顶点到其余所有顶点的最短路径。算法使用临时标签记录暂定距离，确认到该顶点的最短距离后，将临时标签更新为永久标签。

*例:* 戴克斯特拉算法可以用来求地图上两个城镇之间的最短行车路线，其中边代表道路，权重代表通行时间。

> **tip**
>
> Edexcel要求你展示所有临时标签，更新旧标签时将其划去，并且明确标记永久标签（通常用圈出或下划线标注）。你还需要写出最终路径和它的总权重才能拿到全部分数。

**例题:** 在下图中使用戴克斯特拉算法求从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。

*计算器:* allowed

## 常见错误

- **错误做法:** 在克鲁斯卡尔算法中添加会形成环的边
  - 原因: 边按权重排序后，你必须检查边的两个顶点是否已经连通。添加成环边会不必要地增大总权重，得到无效的最小生成树。
  - 正确做法: 排序完所有边之后，添加每条边之前先检查它的两个端点是否属于不同的连通分量。演算过程中要明确标注跳过的边，方便阅卷老师判分。
- **错误做法:** 使用矩阵版普里姆算法时忘记划去已加入顶点对应的行
  - 原因: 如果不划去已经加入树的顶点对应的行，你可能会误选连接两个已经在树内的顶点的边，从而形成环。
  - 正确做法: 每将一个顶点加入最小生成树，立刻在邻接矩阵中划去它对应的行，之后再选择下一条最小边。
- **错误做法:** 戴克斯特拉算法刚给终点打上标签就停止，没有确认该标签是永久标签
  - 原因: 临时标签之后可能通过其他顶点找到更短的路径，从而被更新为更小的值。
  - 正确做法: 只有当目标顶点获得永久标签，或者所有顶点都处理完毕时，才能终止戴克斯特拉算法。
- **错误做法:** 在存在负权重边的图上使用戴克斯特拉算法
  - 原因: 戴克斯特拉算法并非为负权重场景设计，如果图中存在负边，算法会返回错误的最短路径结果。
  - 正确做法: 应用戴克斯特拉算法之前确认所有边的权重都是非负的，Edexcel D1考试的所有相关题目都满足这个要求。
- **错误做法:** 答题时没有列出边/顶点的选择顺序
  - 原因: 即使你后续出现小的计算错误，Edexcel也会为正确的选择顺序给过程分。跳过这一步会白白丢失容易拿到的分数。
  - 正确做法: 对于克鲁斯卡尔/普里姆算法，始终按选择顺序清晰写出边的列表；对于戴克斯特拉算法，按顺序写出永久标签的列表。

## 速查表

| 算法 | 适用场景 | 核心步骤 | 考试要求 |
| --- | --- | --- | --- |
| 克鲁斯卡尔 | 求最小生成树 | 1. 将边按权重升序排序；2. 添加边，跳过成环边；3. 所有顶点连通后停止 | 按选择顺序列出边，标注因成环跳过的边 |
| 普里姆（网络版） | 求最小生成树 | 1. 选定起点顶点；2. 将连接树的最小相邻边加入树；3. 重复直到所有顶点连通 | 展示顶点/边的添加顺序 |
| 普里姆（矩阵版） | 从邻接矩阵求最小生成树 | 1. 选定起点顶点，划去它对应的行；2. 在剩余列中选择最小值；3. 划去新加入顶点的行，重复操作 | 展示每一步划去的行 |
| 戴克斯特拉 | 求两个顶点之间的最短路径 | 1. 给起点顶点标注永久标签0；2. 更新相邻顶点的临时标签；3. 将最小临时标签转为永久，重复直到目标顶点获得永久标签 | 展示所有临时/永久标签，写出最终路径和总权重 |

## 下一步

现在你已经掌握了Edexcel IAL D1的核心图算法，可以开始学习更进阶的决策数学内容。接下来你将学习路径检验问题和旅行商问题，这些内容都建立在你已经练习过的图论逻辑之上。你还应该多做这些算法相关的历年真题，提升解题速度和准确率，这类题目几乎出现在每一份D1试卷中，占卷面总分的15%-25%。请务必遵循Edexcel要求的演算格式，避免丢失过程分。

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/edexcel-ial-math-d1-algorithms-on-graphs/