📚 Prim's Algorithm | Prim 算法
Prim's algorithm is a greedy method for finding the minimum spanning tree of a connected, weighted, undirected graph. It builds the tree one vertex at a time, always adding the cheapest edge that connects the current tree to a vertex outside the tree.
Prim 算法是一种贪心算法，用于在连通、带权、无向图中寻找最小生成树。它每次扩展一个顶点，总是添加连接当前树与树外顶点的权重最小的边。
1. Minimum Spanning Trees | 最小生成树
A minimum spanning tree, or MST, is a subset of edges that connects every vertex in a graph together without any cycles and has the smallest possible total edge weight. An MST with V vertices always contains exactly V - 1 edges.
最小生成树（MST）是指将图中所有顶点连接起来且不含回路的一棵边子集，并且这些边的总权重尽可能小。对于有 V 个顶点的图，最小生成树恰好包含 V - 1 条边。
Prim's algorithm is useful because many real-world problems can be modelled as finding a minimum spanning tree, such as designing road networks, laying cables, or building low-cost communication links.
Prim 算法非常实用，因为许多现实问题都可以建模为寻找最小生成树，例如设计道路网络、铺设电缆或建立低成本的通信连接。
2. The Core Idea of Prim's Algorithm | Prim 算法的核心思想
Prim's algorithm starts at an arbitrary vertex and treats this vertex as the initial tree. At each step, it looks at every edge that connects a vertex already in the tree to a vertex outside the tree, and it selects the edge with the minimum weight. That edge and the new vertex are then added to the tree.
Prim 算法从任意一个顶点开始，把这个顶点当作初始的树。每一步，它查看所有连接已在树中的顶点与树外顶点的边，并选择权重最小的那条边。然后将这条边和新的顶点加入树中。
This process repeats until all vertices have been included. Because the algorithm always picks the cheapest available connection and never revises earlier decisions, it is classified as a greedy algorithm.
这个过程不断重复，直到所有顶点都被加入树中。由于算法总是选择当前可用的最便宜连接，并且不会修正之前的决定，因此它被归类为贪心算法。
3. Step-by-Step Procedure | 逐步执行步骤
The algorithm can be described as follows:
算法可以描述如下：
1. Choose any starting vertex. Mark it as visited and set its key value to 0. For every other vertex, set the key value to infinity.
1. 选择任意一个起始顶点。将其标记为已访问，并设置它的 key 值为 0。对于其他所有顶点，把 key 值设为无穷大。
2. While there are still unvisited vertices, select the unvisited vertex with the smallest key value. Add the edge connecting this vertex to the current tree, and mark the vertex as visited.
2. 当仍然存在未访问顶点时，选择 key 值最小的未访问顶点。将连接该顶点与当前树的边加入生成树，并把这个顶点标记为已访问。
3. After visiting a vertex, examine all its neighbours that are not yet visited. If the weight of the edge to a neighbour is smaller than the neighbour's current key value, update that key value and record the current vertex as its parent.
3. 访问一个顶点后，检查它所有尚未访问的邻接顶点。如果通向某个邻接顶点的边的权重小于该邻接顶点当前的 key 值，就更新这个 key 值，并把当前顶点记录为它的父顶点。
4. Repeat steps 2 and 3 until every vertex is visited. The resulting set of edges used to visit each vertex forms the minimum spanning tree.
4. 重复步骤 2 和 3，直到所有顶点都被访问。最终用于访问每个顶点的边的集合就构成最小生成树。
4. Worked Example | 示例演算
A, B, C and D. The edge weights are AB = 4, AC = 2, BC = 1, BD = 5 and CD = 3. Start Prim's algorithm at vertex A.
考虑一个包含顶点 A、B、C 和 D 的带权图。边的权重为 AB = 4、AC = 2、BC = 1、BD = 5 和 CD = 3。从顶点 A 开始执行 Prim 算法。
The tables below show the visited set, the chosen edge and the current total cost after each step.
下表展示了每一步的已访问集合、选择的边以及当前总成本。
| Step | Visited set | Chosen edge | Weight | Total |
|---|---|---|---|---|
| 0 | {A} | — | — | 0 |
| 1 | {A, C} | AC | 2 | 2 |
| 2 | {A, C, B} | CB | 1 | 3 |
| 3 | {A, C, B, D} | CD | 3 | 6 |
he minimum spanning tree consists of edges AC, CB and CD, with total weight 2 + 1 + 3 = 6.
最小生成树由边 AC、CB 和 CD 组成，总权重为 2 + 1 + 3 = 6。
5. Data Structures and Implementation | 数据结构与实现
To implement Prim's algorithm efficiently, we need three main structures: a key array to store the current minimum distance from the tree to each vertex, a parent array to record the edge that connects each vertex to the tree, and a priority queue or similar structure to select the next unvisited vertex with the smallest key.
为了高效地实现 Prim 算法，我们需要三种主要结构：一个 key 数组，用于存储从当前树到每个顶点的最小距离；一个 parent 数组，用于记录连接每个顶点与树的边；以及一个优先队列或类似结构，用于选择下一个 key 值最小的未访问顶点。
A typical high-level implementation can be expressed using the following update rule after adding a vertex u:
在加入顶点 u 之后，典型的高层实现可以用下面的更新规则表示：
if v is unvisited and weight(u, v) < key[v] then key[v] ← weight(u, v), parent[v] ← u
For small graphs, a simple array and linear scan can be used, which is easier to trace in an exam. For larger graphs, a binary heap priority queue reduces the time needed to find the minimum key value.
对于小图，可以使用简单的数组和线性扫描，这在考试中更容易追踪。对于较大的图，二叉堆优先队列可以减少查找最小 key 值所需的时间。
6. Time Complexity Analysis | 时间复杂度分析
The time complexity of Prim's algorithm depends on how the graph is stored and how the next vertex is selected.
Prim 算法的时间复杂度取决于图的存储方式以及如何选择下一个顶点。
If the graph is stored as an adjacency matrix and we use a simple linear scan to find the minimum key, the complexity is O(V²), where V is the number of vertices. This approach is simple and works well for dense graphs.
如果图用邻接矩阵存储，并且使用简单的线性扫描来查找最小 key 值，那么时间复杂度为 O(V²)，其中 V 是顶点数。这种方法简单，并且适用于稠密图。
If the graph is stored as an adjacency list and a binary heap is used as the priority queue, the complexity is O(E log V), where E is the number of edges. This is generally better for sparse graphs. With a Fibonacci heap, the complexity can be improved to O(E + V log V).
如果图用邻接表存储，并使用二叉堆作为优先队列，时间复杂度为 O(E log V)，其中 E 是边数。对于稀疏图，这种方式通常更好。如果使用斐波那契堆，复杂度可以进一步优化为 O(E + V log V)。
7. Correctness of Prim's Algorithm | Prim 算法的正确性
Prim's algorithm is correct because of the cut property. A cut partitions the vertices into two disjoint sets; the cut property states that for any cut, the minimum-weight edge crossing the cut belongs to some minimum spanning tree.
Prim 算法之所以正确，是因为切分性质。一个切分将顶点分为两个不相交的集合；切分性质指出，对于任意一个切分，横跨该切分的最小权重边一定属于某个最小生成树。
At every step, Prim's algorithm considers the cut between the set of visited vertices and the set of unvisited vertices. It adds the minimum-weight edge crossing this cut. By the cut property, this edge is safe to include in an MST. Therefore, after V - 1 iterations, the algorithm has constructed a valid minimum spanning tree.
在每一步，Prim 算法考虑已访问顶点集合与未访问顶点集合之间的切分。它加入横跨这个切分的最小权重边。根据切分性质，这条边可以安全地包含在最小生成树中。因此，经过 V - 1 次迭代后，算法就构造出了一棵有效的最小生成树。
8. Prim's vs Kruskal's Algorithm | Prim 与 Kruskal 算法比较
Both Prim's algorithm and Kruskal's algorithm find the same minimum spanning tree weight, but they build the tree in different ways. Prim's algorithm grows a single tree from a starting vertex, whereas Kruskal's algorithm sorts all edges by weight and adds the cheapest edge that does not create a cycle.
Prim 算法和 Kruskal 算法都能得到相同的最小生成树总权重，但它们的建树方式不同。Prim 算法从一个起始顶点开始生长一棵树，而 Kruskal 算法将所有边按权重排序，然后添加不会形成回路的最便宜边。
| Feature | Prim's algorithm | Kruskal's algorithm |
|---|---|---|
| Approach | Grow one tree from a start vertex | Build forest and merge components |
| Best for | Dense graphs | Sparse graphs |
| Time complexity | O(V²) with adjacency matrix, O(E log V) with heap | O(E log E) or O(E log V) |
| Data structure needed | Priority queue or key array | Union-find / disjoint set |
In exam questions, you should choose the algorithm that is easier to apply to the given graph. If the graph is drawn with a clear starting point, Prim's algorithm is usually faster to trace manually. If the edges are already listed, Kruskal's algorithm may be simpler.
在考试题目中，你应该选择更适合给定图的算法。如果图给出了明确的起点，Prim 算法通常更容易手动追踪。如果边已经列出，Kruskal 算法可能更简单。
9. Common Mistakes and Exam Tips | 常见错误与应试技巧
One common mistake is updating a key value without checking whether the vertex is already visited. This can lead to the same vertex being added twice or an incorrect edge being selected. Always separate the visited set from the unvisited set.
一个常见错误是在没有检查顶点是否已经访问的情况下就更新 key 值。这可能导致同一个顶点被加入两次，或者选择了错误的边。一定要把已访问集合和未访问集合分开。
Another mistake is choosing the smallest edge globally instead of the smallest edge crossing the cut. Prim's algorithm only considers edges that connect the current tree to an outside vertex, not any edge anywhere in the graph.
另一个错误是选择全局最小的边，而不是横跨切分的最小边。Prim 算法只考虑连接当前树与树外顶点的边，而不是图中任意位置的边。
When tracing Prim's algorithm in an exam, always draw the current tree and list the candidate crossing edges at each step. Show key values in a table and record which vertex and edge are selected. This makes your reasoning clear and helps avoid arithmetic slips.
在考试中追踪 Prim 算法时，始终画出当前的树，并在每一步列出候选的横跨边。在表格中显示 key 值，并记录选择了哪个顶点和哪条边。这会让你的推理过程更清晰，并帮助避免计算错误。
10. Exam-Style Practice Question | 考试风格练习题
PR = 5, QR = 3, QS = 4, RS = 2, RT = 6, ST = 5 and QT = 9. Starting at vertex P, use Prim's algorithm to construct a minimum spanning tree. Show each step clearly.
考虑下面的带权图。顶点为 P、Q、R、S 和 T。边的权重为 PQ = 7、PR = 5、QR = 3、QS = 4、RS = 2、RT = 6、ST = 5 和 QT = 9。从顶点 P 开始，使用 Prim 算法构造最小生成树。请清楚地展示每一步。
ST = 5. Choose ST = 5. The MST has weight 5 + 2 + 3 + 5 = 15 with edges PR, RS, RQ and ST.
解答：从 P 开始，选择 PR = 5。从已访问集合 {P, R} 出发，候选边为 PQ = 7、RQ = 3、RT = 6 和 RS = 2。选择 RS = 2。从 {P, R, S} 出发，候选边为 PQ = 7、RQ = 3、RT = 6、SQ = 4 和 ST = 5。选择 RQ = 3。从 {P, R, S, Q} 出发，候选边为 QT = 9、QS = 4 已访问、RT = 6 和 ST = 5。选择 ST = 5。最小生成树的总权重为 5 + 2 + 3 + 5 = 15，包含边 PR、RS、RQ 和 ST。
11. Summary | 总结
Prim's algorithm is a greedy algorithm for finding a minimum spanning tree. It grows the tree one vertex at a time by repeatedly adding the cheapest edge that connects a visited vertex to an unvisited vertex. With clear step-by-step tracing, you can confidently solve MST questions in the Edexcel A-Level Computer Science exam.
Prim 算法是一种用于寻找最小生成树的贪心算法。它通过不断添加连接已访问顶点与未访问顶点的最便宜边，每次扩展一个顶点。只要按照清晰的步骤逐步追踪，你就能在 Edexcel A-Level 计算机科学考试中自信地解决最小生成树问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图