Applying Prim’s Algorithm to a Distance Matrix | 在距离矩阵上应用普里姆算法

📚 Applying Prim’s Algorithm to a Distance Matrix | 在距离矩阵上应用普里姆算法

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a weighted undirected graph. At A-Level, Edexcel frequently assesses your ability to apply Prim’s algorithm directly to a distance matrix, rather than to a drawn graph. This skill tests both your understanding of the algorithm and your accuracy with tabular data.

普里姆算法是一种贪心算法，用于为带权无向图寻找最小生成树（MST）。在 A-Level Edexcel 考试中，经常直接考查你如何在距离矩阵上应用普里姆算法，而不是在图形上操作。这项技能同时检验你对算法的理解程度以及处理表格数据的准确性。

---

1. Understanding the Distance Matrix | 理解距离矩阵

A distance matrix is a square table where rows and columns represent vertices. Each cell stores the weight of the edge between the vertex in its row and the vertex in its column. Cells on the main diagonal are typically left blank or marked with a dash, because a vertex has no edge to itself.

距离矩阵是一个正方形表格，行和列分别代表顶点。每个单元格存储对应行顶点与列顶点之间边的权重。主对角线上的单元格通常留空或用短横线标记，因为顶点与自身之间不存在边。

• For an undirected graph, the matrix is symmetric: the value in row X, column Y equals the value in row Y, column X.

• 对于无向图，矩阵是对称的：第 X 行第 Y 列的值等于第 Y 行第 X 列的值。

• If two vertices are not directly connected, the cell may contain ‘∞’ or a dash — this means no edge exists.

• 如果两个顶点之间没有直接连接，单元格可能包含 ‘∞’ 或短横线 — 表示不存在边。

Before starting the algorithm, always identify the full set of vertices and note whether the matrix is symmetric. This will help you avoid reading errors.

在开始算法之前，务必先确定完整的顶点集合，并注意矩阵是否对称。这样可以帮助你避免读取错误。

---

2. Prim’s Algorithm: Core Principle | 普里姆算法：核心原理

Prim’s algorithm builds a minimum spanning tree by growing a single tree from an arbitrary starting vertex. At each step, it selects the edge of smallest weight that connects a vertex already in the tree to a vertex not yet in the tree.

普里姆算法通过从一个任意起始顶点开始生长单棵树来构建最小生成树。在每一步中，它选择权重最小的边，该边连接已在树中的顶点与尚未在树中的顶点。

MST = 最小生成树，即连接所有顶点且总权重最小的树

When working with a distance matrix, the “tree” is represented by two sets: the set of visited vertices and the set of unvisited vertices. You repeatedly scan the rows of visited vertices to find the smallest entry pointing to an unvisited vertex.

在距离矩阵上操作时，”树”由两个集合表示：已访问顶点集合和未访问顶点集合。你反复扫描已访问顶点的所有行，找出指向未访问顶点的最小条目。

---

3. Standard Algorithm Steps for a Matrix | 矩阵上的标准算法步骤

The steps below are the examination-friendly version of Prim’s algorithm applied to a distance matrix. Memorise them exactly, as the wording is often quoted in mark schemes.

以下是在距离矩阵上应用普里姆算法的考试友好版本步骤。请准确记忆它们，因为评分标准中经常引用这些措辞。

• Step 1: Choose any starting vertex. Add it to the visited set.

• 步骤 1：选择任意起始顶点，将其加入已访问集合。

• Step 2: Look across the row of the starting vertex. Select the smallest value that connects to an unvisited vertex. Add that vertex to the visited set.

• 步骤 2：查看起始顶点的整行，选择连接未访问顶点的最小值，将该顶点加入已访问集合。

• Step 3: Now look across all rows of visited vertices. Find the smallest edge leading to an unvisited vertex. Add it to the tree.

• 步骤 3：现在查看所有已访问顶点的行，找出通向未访问顶点的最小边，将其加入树中。

• Step 4: Repeat Step 3 until all vertices are visited. If a tie occurs, either choice is valid.

• 步骤 4：重复步骤 3，直到所有顶点均被访问。若出现并列最小值，任选其一均可。

---

4. Worked Example: Setting Up | 完整示例：初始设定

Consider the following distance matrix for five vertices A, B, C, D and E. We will apply Prim’s algorithm starting from vertex A.

考虑以下包含五个顶点 A、B、C、D、E 的距离矩阵。我们将从顶点 A 开始应用普里姆算法。

Vertex	A	B	C	D	E
A	–	2	5	7	1
B	2	–	3	8	4
C	5	3	–	6	9
D	7	8	6	–	2
E	1	4	9	2	–

Visited set initially: {A}. We will track the selected edges in order.

初始已访问集合：{A}。我们将按顺序记录所选边。

---

5. First Iteration: From the Start Vertex | 第一次迭代：从起始顶点出发

Look only at row A. The values are: B=2, C=5, D=7, E=1. The smallest value is 1, which connects A to E. So we select edge A–E with weight 1.

只查看 A 行。值为：B=2、C=5、D=7、E=1。最小值为 1，连接 A 与 E。因此我们选择边 A–E，权重为 1。

• Visited set becomes: {A, E}

• 已访问集合变为：{A, E}

• Edges selected so far: A–E (1)

• 目前已选边：A–E (1)

---

6. Second Iteration: Scanning All Visited Rows | 第二次迭代：扫描所有已访问行

Now we examine rows A and E simultaneously. For each unvisited vertex, record the smallest value from either row:

现在同时查看 A 行和 E 行。对于每个未访问顶点，记录来自任一行的最小值：

• To B: A–B = 2, E–B = 4, so minimum = 2 (via A)

• 到 B：A–B = 2，E–B = 4，所以最小值为 2（通过 A）

• To C: A–C = 5, E–C = 9, so minimum = 5 (via A)

• 到 C：A–C = 5，E–C = 9，所以最小值为 5（通过 A）

• To D: A–D = 7, E–D = 2, so minimum = 2 (via E)

• 到 D：A–D = 7，E–D = 2，所以最小值为 2（通过 E）

The smallest candidate is 2. There is a tie between A–B and E–D. Either one may be chosen. We will select A–B (weight 2).

最小候选值为 2。A–B 与 E–D 并列。两者均可选择。我们选择 A–B（权重 2）。

• Visited set becomes: {A, E, B}

• 已访问集合变为：{A, E, B}

• Edges selected: A–E (1), A–B (2)

• 已选边：A–E (1)，A–B (2)

---

7. Third and Fourth Iterations: Completing the Tree | 第三、四次迭代：完成树

Now scan rows A, E and B. For each unvisited vertex (C and D remains):

现在扫描 A、E、B 三行。对于每个未访问顶点（C 和 D 仍未访问）：

• To C: A–C = 5, E–C = 9, B–C = 3, so minimum = 3 (via B)

• 到 C：A–C = 5，E–C = 9，B–C = 3，所以最小值为 3（通过 B）

• To D: A–D = 7, E–D = 2, B–D = 8, so minimum = 2 (via E)

• 到 D：A–D = 7，E–D = 2，B–D = 8，所以最小值为 2（通过 E）

The smallest is 2, so we select E–D. Visited set: {A, E, B, D}.

最小值为 2，因此我们选择 E–D。已访问集合：{A, E, B, D}。

For the final vertex C, scan rows A, E, B and D: A–C = 5, E–C = 9, B–C = 3, D–C = 6. The minimum is 3, so we select B–C.

对于最后一个顶点 C，扫描 A、E、B、D 四行：A–C = 5，E–C = 9，B–C = 3，D–C = 6。最小值为 3，因此我们选择 B–C。

• Final edge set: A–E (1), A–B (2), E–D (2), B–C (3)

• 最终边集：A–E (1)，A–B (2)，E–D (2)，B–C (3)

• Total weight = 1 + 2 + 2 + 3 = 8

• 总权重 = 1 + 2 + 2 + 3 = 8

---

8. Recording Your Answer Correctly | 正确记录答案

In the exam, marks are awarded for the order in which edges are added, the weights, and the total. Always write edges in the order they were selected, and clearly state the total weight of the minimum spanning tree.

在考试中，得分点包括边加入的顺序、权重以及总权重。务必按选择顺序写出各条边，并清楚标明最小生成树的总权重。

Edges: A–E (1), A–B (2), E–D (2), B–C (3) → Total = 8

A common error is to report the edges without the total, or to list them out of order. Both will cost you marks on a six-mark question.

常见错误是只写边而不写总权重，或者没有按顺序列出边。这两种错误都会在 6 分题中让你失分。

---

9. Complexity and Choice of Start Vertex | 复杂度与起始顶点的选择

The time complexity of Prim’s algorithm using a simple array-based implementation is O(n²), where n is the number of vertices. Using a binary heap priority queue improves this to O((n + m) log n), where m is the number of edges.

使用简单数组实现的普里姆算法时间复杂度为 O(n²)，其中 n 为顶点数。使用二叉堆优先队列可将其改进为 O((n + m) log n)，其中 m 为边数。

• The total weight of the MST is independent of the starting vertex — any valid start yields the same minimum total.

• 最小生成树的总权重与起始顶点无关 — 任意合法起点都得到相同的最小总权重。

• The actual edge set may differ if ties are broken differently, but the total remains minimal.

• 若并列打破方式不同，实际边集可能不同，但总权重仍然最小。

---

10. Common Mistakes and Exam Tips | 常见错误与考试提示

The following pitfalls appear frequently in Edexcel examiner reports. Avoid them to secure full marks.

以下陷阱在 Edexcel 考官报告中频繁出现。避免它们以获得满分。

• Mistake 1: Including the diagonal entries. The dash cells are not edges — never select them.

• 错误 1：包含对角线条目。短横线单元格不是边 — 切勿选择它们。

• Mistake 2: Selecting an edge that connects two already-visited vertices. This creates a cycle and is not allowed.

• 错误 2：选择连接两个已访问顶点的边。这会形成环，是不允许的。

• Mistake 3: Only scanning the most recently added row. You must scan all visited rows every time.

• 错误 3：只扫描最近添加的行。每次都必须扫描所有已访问的行。

• Tip: Cross out rows/columns as vertices are visited, or tick them, to avoid re-reading rejected values.

• 提示：当顶点被访问后，划掉其行/列，或做标记，以避免重复读取被拒绝的值。

---

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）