📚 Applying Prim's Algorithm to a Distance Matrix | 将普里姆算法应用于距离矩阵
Prim's algorithm is a classic greedy approach for finding a minimum spanning tree (MST) in a weighted, undirected graph. When the graph is represented as a distance matrix, the algorithm can be executed efficiently using a tabular method. This article explains how to apply Prim's algorithm directly to a distance matrix, step by step, covering the logic, worked examples, and common pitfalls.
普里姆算法是一种经典的贪心算法，用于在加权无向图中寻找最小生成树（MST）。当图以距离矩阵的形式表示时，可以通过表格法高效地执行该算法。本文将逐步讲解如何将普里姆算法直接应用于距离矩阵，涵盖逻辑、详细示例和常见易错点。
1. Understanding Minimum Spanning Trees | 理解最小生成树
A minimum spanning tree connects all vertices of a graph with the minimum total edge weight, without forming any cycles. Prim's algorithm builds the MST by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a vertex in the tree to a vertex outside the tree.
最小生成树以最小的总边权连接图中的所有顶点，且不形成任何环。普里姆算法通过从任意顶点开始，反复添加连接树内顶点与树外顶点的最便宜边来构建MST。
The distance matrix is an n × n table where the entry at row i, column j gives the weight of the edge between vertex i and vertex j. If there is no direct edge, the entry is typically a very large value or infinity. The matrix is symmetric for an undirected graph.
距离矩阵是一个 n × n 的表格，其中第i行第j列的元素给出了顶点i与顶点j之间边的权重。如果没有直接的边，该元素通常为一个非常大的值或无穷大。对于无向图，矩阵是对称的。
2. The Tabular Method for Prim's Algorithm | 普里姆算法的表格法
When using a distance matrix, we can avoid drawing the graph by maintaining a table that tracks, for each vertex not yet in the MST, the minimum weight edge connecting it to the current tree. This table is updated as new vertices are added to the MST.
当使用距离矩阵时，我们可以避免绘制图形，而是维护一个表格，为每个尚未加入MST的顶点记录其连接到当前生成树的最小边权。当新顶点加入MST时，更新此表格。
The algorithm proceeds as follows: Choose a starting vertex (often vertex 1). Mark it as part of the MST. Then, for every other vertex, look up the weight from the starting vertex in the matrix. Select the smallest such weight and the corresponding vertex. Add that vertex to the MST and note the chosen edge. Then, for each remaining vertex, compare its current stored weight with the weight from the newly added vertex; update if smaller. Repeat until all vertices are included.
算法步骤如下：选择一个起始顶点（通常为顶点1），将其标记为MST的一部分。然后，对于其他每个顶点，在矩阵中查找从起始顶点出发的权重。选择最小的权重及其对应顶点，将该顶点加入MST并记录所选边。接着，对于每个剩余顶点，将其当前存储的权重与从新加入顶点出发的权重进行比较；如果更小则更新。重复直到所有顶点都加入。
3. Setting Up the Distance Matrix | 建立距离矩阵
e this, using 0 on the diagonal and a large number (say, ∞) where there is no direct edge:
假设我们有一个包含顶点 A、B、C、D、E 的图。距离矩阵可能如下所示，对角线为0，没有直接边的地方用一个大数（例如 ∞）表示：
| A | B | C | D | E | |
| A | 0 | 4 | 2 | ∞ | ∞ |
| B | 4 | 0 | 1 | 5 | ∞ |
| C | 2 | 1 | 0 | 8 | 7 |
| D | ∞ | 5 | 8 | 0 | 3 |
| E | ∞ | ∞ | 7 | 3 | 0 |
In exam problems, an infinite or absent connection is often shown as a dash '-' that will never be chosen unless all remaining options are infinite (disconnected graph).
在考试题目中，无限或无连接通常用破折号 '-' 或符号 ∞ 表示。我们将其视为一个除非所有剩余选项均为无穷大（不连通图）否则永远不会被选中的值。
4. Step 1: Initialisation | 第一步：初始化
ght from the MST to that vertex. Initially, the MST contains only A, so the distances are simply row A from the matrix: B=4, C=2, D=∞, E=∞.
选择顶点 A 作为起点。将 A 标记为已访问。为未访问的顶点 B、C、D、E 设置一行（或列表），显示从 MST 到该顶点当前的最小边权。初始时，MST 只包含 A，因此距离就是矩阵中 A 行的数值：B=4，C=2，D=∞，E=∞。
We also keep track of the parent vertex that gives this smallest weight; initially, parent of all is A.
我们还要记录给出此最小权重的父顶点；最初，所有顶点的父顶点都是 A。
5. Step 2: Selecting the First Edge | 第二步：选择第一条边
, C=2, D=∞, E=∞, the smallest value is 2 for vertex C. So we add C to the MST, with edge A–C weight 2. Mark C as visited.
在 B=4，C=2，D=∞，E=∞ 中，最小值是顶点 C 的 2。因此我们将 C 加入 MST，边为 A–C，权重为 2。将 C 标记为已访问。
The MST now contains {A, C}. We must update the distances for the remaining unvisited vertices B, D, E by comparing their current stored values with the weights from C's row in the matrix.
现在 MST 包含 {A, C}。我们必须通过比较当前存储值与矩阵 C 行中的权重，来更新剩余未访问顶点 B、D、E 的距离。
- For B: current value is 4; weight from C to B is 1. Since 1 < 4, update B to 1 and set parent to C.
- For D: current ∞; weight from C to D is 8. 8 < ∞, update D to 8, parent C.
- For E: current ∞; weight from C to E is 7. Update E to 7, parent C.
- 对于 B：当前值为 4；从 C 到 B 的权重是 1。因为 1 < 4，将 B 更新为 1，父顶点设为 C。
- 对于 D：当前为 ∞；从 C 到 D 的权重是 8。8 < ∞，将 D 更新为 8，父顶点 C。
- 对于 E：当前为 ∞；从 C 到 E 的权重是 7。将 E 更新为 7，父顶点 C。
6. Step 3: Next Selection | 第三步：下一次选择
Current distances: B=1, D=8, E=7. The smallest is B with value 1. Add B to MST with edge C–B weight 1 (parent was C). Mark B visited.
当前距离：B=1，D=8，E=7。最小的是值为1的 B。将 B 加入 MST，边为 C–B，权重为 1（父顶点为 C）。标记 B 已访问。
MST is now {A, C, B}. Update remaining unvisited vertices D, E using B's row: B–D is 5, B–E is ∞. Compare:
MST 现为 {A, C, B}。使用 B 行更新剩余未访问顶点 D、E：B–D 为 5，B–E 为 ∞。进行比较：
- D: current 8, new 5 → update to 5, parent B.
- E: current 7, new ∞ → no change (7 remains).
- D：当前 8，新值 5 → 更新为 5，父顶点 B。
- E：当前 7，新值 ∞ → 不变（保持 7）。
7. Step 4: Completing the Tree | 第四步：完成生成树
Distances left: D=5, E=7. Smallest is D (5). Add D via edge B–D weight 5. Mark D visited. MST: {A, C, B, D}. Update E with D's row: D–E is 3. 3 < 7, so update E to 3, parent D.
剩余距离：D=5，E=7。最小的是 D (5)。通过边 B–D（权重 5）加入 D。标记 D 已访问。MST：{A, C, B, D}。用 D 行更新 E：D–E 为 3。3 < 7，因此将 E 更新为 3，父顶点 D。
Now only E remains, with distance 3. Add E via D–E weight 3. All vertices are in the MST. Total weight = 2 (A–C) + 1 (C–B) + 5 (B–D) + 3 (D–E) = 11.
现在只剩下 E，距离为 3。通过 D–E（权重 3）加入 E。所有顶点都已加入 MST。总权重 = 2 (A–C) + 1 (C–B) + 5 (B–D) + 3 (D–E) = 11。
8. Recording the Steps in a Tabular Format | 以表格形式记录步骤
A typical exam question expects you to show the values in a table with columns for each vertex and rows for each iteration. Here's how it might look for the example:
典型的考试题目期望你用一个表格来展示数值，每列对应一个顶点，每行对应一次迭代。对于本示例，可能如下所示：
| Iteration | Visited | B | C | D | E | Chosen edge |
|---|---|---|---|---|---|---|
| 1 | A | 4 (A) | 2 (A) | ∞ | ∞ | A–C (2) |
| 2 | A, C | 1 (C) | - | 8 (C) | 7 (C) | C–B (1) |
| 3 | A, C, B | - | - | 5 (B) | 7 (C) | B–D (5) |
| 4 | A, C, B, D | - | - | - | 3 (D) | D–E (3) |
Note that once a vertex is visited, its column can be crossed out or ignored. The parent is shown in parentheses. This clearly demonstrates the progressive selection and updating process.
请注意，一旦某个顶点被访问，其列可以被划掉或忽略。父顶点显示在括号中。这清楚地展示了逐步选择和更新的过程。
9. Handling Disconnected Components | 处理不连通分量
If the graph is disconnected, at some stage all the remaining candidate distances will be infinite. In that case, the algorithm cannot form an MST spanning all vertices, and the process terminates early. It's essential to recognise that Prim's algorithm only works on connected graphs.
如果图不连通，在某个阶段所有剩余的候选距离都会是无穷大。此时，算法无法形成涵盖所有顶点的MST，过程会提前终止。需要认识到普里姆算法仅适用于连通图。
In the distance matrix, a disconnected graph will have rows where large/infinite values cannot be avoided, even after updates. Exam questions might ask you to explain why the algorithm fails or to state the condition for a valid MST.
在距离矩阵中，不连通图会出现即使经过更新也无法避免大值/无穷值的行。考试题目可能会要求解释算法为何失败，或说明有效MST的条件。
10. Choosing a Different Starting Vertex | 选择不同的起始顶点
Prim's algorithm can start at any vertex. The resulting MST will have the same total weight (though the edges selected may differ if there are multiple edges with the same weight). Some exam questions specify the starting vertex; otherwise, choose vertex 1 or A for consistency.
普里姆算法可以从任意顶点开始。生成的MST将具有相同的总权重（尽管如果存在多条权重相同的边，所选边可能不同）。一些考试题目会指定起始顶点；否则，为了一致性选择顶点1或A。
If you start from a different vertex, the sequence of selected edges will change, but the final total weight remains minimal and invariant. The distance matrix method works identically; just initialise using the chosen start row.
如果从不同顶点开始，所选边的顺序会改变，但最终总权重保持最小且不变。距离矩阵法的工作方式完全相同；只需使用所选起始行进行初始化。
11. Comparison with Kruskal's Algorithm | 与克鲁斯卡尔算法的比较
While Prim's algorithm grows a single tree, Kruskal's algorithm sorts all edges by weight and adds them if they don't create a cycle. On a distance matrix, Kruskal's is less convenient because it requires sorting edges, but Prim's maps naturally to the row/column update process. The choice of method often depends on the representation.
普里姆算法增长一棵树，而克鲁斯卡尔算法将所有边按权重排序，并在不产生环的前提下添加边。在距离矩阵上，克鲁斯卡尔算法不太方便，因为它需要对边进行排序，而普里姆算法自然地映射到行/列更新过程。方法的选择通常取决于图的表示形式。
In terms of complexity, Prim's algorithm with a distance matrix and simple linear search runs in O(n²) time, where n is the number of vertices. This is efficient for dense graphs. Kruskal's typically runs in O(m log m), where m is the number of edges, which can be better for sparse graphs.
就复杂度而言，使用距离矩阵和简单线性搜索的普里姆算法运行时间为 O(n²)，其中 n 是顶点数量。这对于稠密图是高效的。克鲁斯卡尔算法通常运行时间为 O(m log m)，其中 m 是边的数量，这对于稀疏图可能更好。
12. Practice Exercise and Common Mistakes | 练习题与常见错误
Exercise: Given the distance matrix below, use Prim's algorithm starting from vertex P to find the MST and its total weight.
练习： 给定下面的距离矩阵，使用普里姆算法从顶点 P 开始，寻找 MST 及其总权重。
| P | Q | R | S | |
| P | - | 3 | 6 | 9 |
| Q | 3 | - | 4 | 2 |
| R | 6 | 4 | - | 5 |
| S | 9 | 2 | 5 | - |
Common mistakes: Forgetting to update the table after each addition; using the wrong row to update; updating visited vertices; confusing the parent vertex; or misreading symmetric entries as differing. Always remember to only consider unvisited vertices for the minimum selection, and to use the newly added vertex's row for potential improvements.
常见错误： 忘记在每次添加后更新表格；使用了错误的行进行更新；更新已访问的顶点；混淆父顶点；或将对称项误读为不同值。始终记住仅考虑未访问的顶点以进行最小选择，并使用新添加顶点的行进行可能的改进。
Practising this tabular method thoroughly will give you confidence in solving distance matrix problems efficiently under timed conditions.
彻底练习这种表格法将使你在计时条件下有信心高效地解决距离矩阵问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图