Prim's Algorithm | 普里姆算法

📚 Prim's Algorithm | 普里姆算法

Prim's algorithm is a classic greedy method used to construct a minimum spanning tree (MST) for a weighted, undirected graph. Starting from an arbitrary vertex, it repeatedly adds the cheapest possible edge that connects a vertex already in the tree to a vertex outside the tree, growing the MST one edge at a time. This approach guarantees an optimal solution and forms a foundational topic in A‑Level Computer Science under graph traversal and optimisation.

普里姆算法是一种经典的贪心方法，用于为带权无向图构建最小生成树。它从任意一个顶点开始，不断将代价最小的、连接树内顶点与树外顶点的边加入树中，一次扩展一条边。这一方法保证了最优解，是 A‑Level 计算机科学中图遍历与优化领域的基础课题。

---

1. What is a Minimum Spanning Tree? | 什么是最小生成树？

A minimum spanning tree of a connected, weighted, undirected graph is a subset of edges that connects all vertices together, without any cycles, and with the minimum possible total edge weight. Every connected graph has at least one MST, and if edge weights are distinct, the MST is unique. The MST problem arises in network design, circuit layout, and many other real‑world scenarios where we need to minimise total connection cost.

带权连通无向图的最小生成树，是指能够连接所有顶点且没有环的边的子集，并使得边的总权重最小。每个连通图至少有一棵 MST，若所有边的权重互不相同，则 MST 唯一。MST 问题出现在网络设计、电路布局等许多需要最小化总连接成本的实际场景中。

---

2. Overview of Prim's Algorithm | 普里姆算法概述

Prim's algorithm builds an MST incrementally by maintaining a set of visited vertices (initially containing an arbitrary starting node) and a set of unvisited vertices. At each step, it examines all edges that cross the cut between visited and unvisited vertices and selects the edge with the smallest weight. The vertex at the other end of that edge is then moved to the visited set. This process repeats until all vertices are visited, resulting in a tree with (V – 1) edges for a graph with V vertices.

普里姆算法通过维护一个已访问顶点集合（初始时任意选择一个起点）和一个未访问顶点集合，逐步构建 MST。在每一步中，它检查所有横跨已访问与未访问顶点之间的边，并从中选出权重最小的一条边，然后将该边另一端的顶点移入已访问集合。重复此过程直到所有顶点都被访问，最终对于 V 个顶点的图，得到恰好 (V–1) 条边的树。

---

3. Step-by-Step Process | 逐步过程

Consider a graph with vertices {A, B, C, D} and weighted edges. Starting at A, we mark A as visited. We then examine all edges from A: A–B (weight 4), A–C (weight 2). The minimum weight edge is A–C, so we add C to the tree and mark C as visited. Now the visited set is {A, C}. We look at edges from visited vertices to unvisited ones: A–B (4), C–B (1), C–D (3). The smallest is C–B (1), so add B. Then the visited set is {A, C, B}. Finally, the only remaining unvisited vertex is D, with edges C–D (3) and B–D (5); the minimum is C–D (3), adding D. The MST edges are A–C (2), C–B (1), C–D (3), total weight 6.

假设一个图有顶点 {A, B, C, D} 和带权边。从 A 开始，将 A 标记为已访问。然后检查 A 出发的所有边：A–B（权重 4），A–C（权重 2）。最小权重的边是 A–C，因此将 C 加入树中并标记为已访问。此时已访问集合为 {A, C}。再查看从已访问顶点到未访问顶点的边：A–B (4)，C–B (1)，C–D (3)。最小的是 C–B (1)，加入 B。现在已访问集合为 {A, C, B}。最后唯一剩余的未访问顶点是 D，相关边为 C–D (3) 和 B–D (5)；最小边是 C–D (3)，加入 D。最终 MST 的边为 A–C (2), C–B (1), C–D (3)，总权重 6。

---

4. Visualising the Cut Property | 可视化割性质

Prim's algorithm repeatedly exploits the "cut property": for any cut of the graph (a partition of vertices into two disjoint sets), the minimum weight edge crossing the cut must be part of some MST. In Prim's, the cut is defined by the visited and unvisited sets. The algorithm always picks the lightest edge crossing that cut, which guarantees safety – the edge can be added without creating a cycle and will lead to an optimal total weight.

普里姆算法反复利用“割性质”：对于图的任意一个割（将顶点划分为两个不相交的集合），横跨该割的最小权重边必定属于某一棵 MST。在普里姆算法中，割由已访问集合与未访问集合定义。算法总是选择横跨该割的最轻边，这保证了安全性——加入该边不会产生环，并将导向最优的总权重。

---

5. Data Structures Used | 所用的数据结构

The efficiency of Prim's algorithm depends heavily on the chosen data structures. A common representation stores the graph as an adjacency matrix (suitable for dense graphs) or adjacency list (for sparse graphs). To manage the frontier of crossing edges, we often use a priority queue (min‑heap) that holds vertices not yet in the tree, keyed by the minimum known edge weight connecting them to the tree. Additionally, arrays track parent pointers to reconstruct the MST edges, and a boolean array marks visited vertices.

普里姆算法的效率在很大程度上取决于所选的数据结构。通常用邻接矩阵（适合稠密图）或邻接表（适合稀疏图）存储图。为了管理横跨边的边界，我们经常使用一个优先队列（最小堆），其中存放尚未加入树的顶点，键值为已知连接它们到树的最小边权重。此外，还需要用数组记录父指针以重建 MST 的边，以及用布尔数组标记已访问顶点。

---

6. Pseudocode for Prim's Algorithm | 普里姆算法的伪代码

The following pseudocode assumes a graph with V vertices, an adjacency matrix weight[u][v], and uses arrays key[ ] and parent[ ], along with a boolean array inMST[ ].

如下伪代码假设图有 V 个顶点，权重矩阵 weight[u][v]，并使用数组 key[] 和 parent[]，以及布尔数组 inMST[]。

// Initialisation
for each vertex v:
    key[v] = ∞
    parent[v] = NULL
    inMST[v] = false

key[0] = 0        // start from vertex 0

for i = 0 to V-1:
    u = vertex with minimum key among those not in MST
    inMST[u] = true

    for each vertex v adjacent to u:
        if not inMST[v] and weight[u][v] < key[v]:
            key[v] = weight[u][v]
            parent[v] = u

// MST edges: (v, parent[v]) for all v except root

The inner loop updates the frontier: if a newly visited vertex offers a cheaper connection to an unvisited vertex, the key and parent are updated. When using a priority queue, the extraction of minimum key takes O(log V) and updating keys takes O(log V), yielding overall time complexity O((V + E) log V).

内部循环更新边界：如果一个新访问的顶点为某个未访问顶点提供了更廉价的连接，则更新 key 和 parent。当使用优先队列时，提取最小值操作为 O(log V)，更新键值也为 O(log V)，总体时间复杂度为 O((V + E) log V)。

---

广告 / Sponsored

7. Time Complexity Analysis | 时间复杂度分析

The complexity of Prim's algorithm varies with implementation. Using an adjacency matrix and a simple linear search for the minimum key vertex gives O(V²) time, which is efficient for dense graphs where E is about V². With an adjacency list and a binary min‑heap, we achieve O((V + E) log V), which is better for sparse graphs. A Fibonacci heap can theoretically reduce this to O(E + V log V), but it is rarely used in practice due to constant factors and A‑Level contexts stick to binary heaps.

普里姆算法的时间复杂度因实现方式而异。使用邻接矩阵和简单线性搜索最小值顶点时，时间复杂度为 O(V²)，对于 E 接近 V² 的稠密图效率较高。使用邻接表和二叉最小堆时，时间复杂度为 O((V + E) log V)，更适合稀疏图。理论上斐波那契堆可以将其降至 O(E + V log V)，但因常数因子较大，实践中极少使用，A‑Level 学习范围也仅限于二叉堆。

---

8. Comparison with Kruskal's Algorithm | 与克鲁斯卡尔算法的比较

Both Prim's and Kruskal's algorithms find an MST but differ in approach. Kruskal's algorithm sorts all edges by weight and adds them one by one, skipping those that form a cycle, using a disjoint‑set data structure. It operates globally on edges, making it simpler to understand but often requiring O(E log E) time. Prim's grows from a vertex and works elegantly with dense graphs using O(V²). The choice depends on graph density and available data structures. In an exam, you may be asked to trace either algorithm on a given graph.

普里姆算法与克鲁斯卡尔算法都能找到 MST，但方法不同。克鲁斯卡尔算法先将所有边按权重排序，然后逐一加入，跳过那些会形成环的边，并使用并查集数据结构。它在边集上全局操作，理解起来更简单，但通常需要 O(E log E) 时间。普里姆算法从顶点出发增长，在稠密图中采用 O(V²) 非常便捷。选择哪种算法取决于图的密度和可用的数据结构。考试中可能要求你在给定图上跟踪执行任一算法。

---

9. Correctness and Greedy Choice | 正确性与贪心选择

Prim's algorithm is correct because it maintains the invariant that the set of edges selected so far is a subset of some MST. The greedy choice – picking the minimum‑weight edge crossing the cut – is always safe. Proof by induction: base case (empty tree) trivially satisfied; assume after k steps the partial tree is contained in some MST. The next edge chosen is the lightest across the cut defined by the tree vertices. By the cut property, there exists an MST containing all hitherto chosen edges plus this lightest edge, so the invariant holds. Thus, after V–1 additions, we have an MST.

普里姆算法的正确性在于它维持了一个不变式：当前已选边集总是某棵 MST 的子集。其贪心选择——选取横跨割的最小权重边——始终是安全的。归纳证明：基础情况（空树）显然为真；假设经过 k 步后，部分树包含于某 MST 中。下一步选取的边是横跨由树顶点定义的割的最轻边。根据割性质，存在一棵包含迄今所有已选边以及这条最轻边的 MST，因此不变式保持。于是经过 V–1 次加入后，我们得到一棵 MST。

---

10. Applications of Prim's Algorithm | 普里姆算法的应用

Prim's algorithm is widely used in network planning, such as designing minimum‑cost communication networks, laying out electrical wiring, or building roads that connect several cities with minimal total length. It also appears in image segmentation, feature analysis, and approximation algorithms for the travelling salesman problem. Understanding MSTs helps in solving broader optimisation problems in computer science and operations research.

普里姆算法广泛应用于网络规划，例如设计最低成本的通信网络、布置电线或修建连接多个城市且总长度最小的道路。它也出现在图像分割、特征分析以及旅行商问题的近似算法中。理解 MST 有助于解决计算机科学和运筹学中更广泛的优化问题。

---

11. Implementing Prim's in Python (A‑Level Style) | 用 Python 实现（A‑Level 风格）

A typical A‑Level exercise involves implementing Prim's algorithm using an adjacency matrix. Below is a simple O(V²) version that clearly demonstrates the logic without a priority queue. Students should be comfortable tracing such code and modifying it to output the MST edges.

典型的 A‑Level 练习涉及使用邻接矩阵实现普里姆算法。下面是一个简单的 O(V²) 版本，清晰地展示了算法逻辑而不使用优先队列。学生应能熟练地追踪这段代码并修改它以输出 MST 边。

def prim(graph, start=0):
    V = len(graph)
    key = [float('inf')] * V
    parent = [None] * V
    in_mst = [False] * V
    key[start] = 0

    for _ in range(V):
        u = min((i for i in range(V) if not in_mst[i]), key=lambda x: key[x])
        in_mst[u] = True
        for v in range(V):
            if graph[u][v] != 0 and not in_mst[v] and graph[u][v] < key[v]:
                key[v] = graph[u][v]
                parent[v] = u

    mst_edges = [(parent[i], i, graph[i][parent[i]]) for i in range(1, V)]
    return mst_edges

Note that the code uses a dense adjacency matrix where 0 indicates no direct edge. The loop selects the unvisited vertex with smallest key, then updates neighbours. This version is straightforward and examinable.

请注意，代码使用稠密邻接矩阵，0 表示没有直接边。循环选择 key 值最小的未访问顶点，然后更新邻居。这个版本简单明了，适合考试。

---

12. Common Mistakes and Exam Tips | 常见错误与考试技巧

Students frequently confuse Prim's algorithm with Dijkstra's algorithm, as both use a similar relaxation step. Remember: Prim's minimises total edge weight, not path distances, so the update condition uses the direct edge weight, not cumulative distance. Another common error is forgetting to initialise the starting vertex's key to 0, which causes all keys to remain infinity. When tracing by hand, carefully mark visited vertices and update the frontier table step by step. In exams, always show the key and parent arrays iteration by iteration to gain full marks.

学生经常混淆普里姆算法与迪杰斯特拉算法，因为两者都使用类似的放松步骤。请记住：普里姆算法最小化总边权重，而非路径距离，因此更新条件使用直接边权重，而非累积距离。另一个常见错误是忘记将起始顶点的 key 初始化为 0，导致所有 key 值保持无穷大。手工追踪时，务必仔细标记已访问顶点并逐步更新边界表。在考试中，务必逐次迭代地展示 key 和 parent 数组，以获得满分。

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

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