Minimum Spanning Tree (MST) and Prim's Algorithm

A minimum spanning tree (MST) is a subset of edges from a connected, weighted, undirected graph that:

1. includes all vertices,
2. contains no cycles,
3. uses exactly $V-1$ edges for $V$ vertices,
4. has the minimum total weight among all spanning trees of the graph.3

A spanning tree is already a minimal connector of the graph, but the MST adds the optimization goal of minimizing total cost.2 This makes MSTs fundamental in network design, such as laying cables, designing roads, building communication backbones, and clustering data.2

If the graph is not connected, an MST for the whole graph does not exist; instead, we obtain a minimum spanning forest.

A central theoretical idea behind MST algorithms is the cut property: for any cut of the graph, a minimum-weight edge crossing that cut belongs to an MST.2 Prim's algorithm repeatedly uses this principle to grow one tree from a starting vertex outward.2

3

Footnotes

1. Minimum spanning trees - Defines spanning trees and MSTs, including tree properties and examples. ↩ ↩² ↩³

2. What is Minimum Spanning Tree (MST) - GeeksforGeeks - Summarizes spanning tree properties such as acyclicity and $V-1$ edges. ↩ ↩²

3. Minimum Spanning Trees - Princeton Algorithms - Explains connectedness requirements and formal MST conditions. ↩ ↩²

4. Minimum Spanning Trees - Princeton Algorithms - Notes that disconnected graphs lead to minimum spanning forests rather than a single MST. ↩ ↩² ↩³

5. Introduction to Algorithms Spanning Trees and Cuts Cut Property - States the cut property and explains why the lightest crossing edge is safe. ↩ ↩² ↩³

6. Introduction to Algorithms - Describes Prim's algorithm as a greedy MST method and contrasts it with Kruskal. ↩

7. Prim's algorithm - Wikipedia - Provides the high-level procedure and discusses data-structure-dependent complexity. ↩

Why Prim's Algorithm Works

Prim's algorithm is a greedy algorithm for MST construction.2 It starts with any one vertex and maintains a growing set of vertices already included in the tree. At every iteration, it selects the smallest-weight edge that connects a vertex inside the current tree to a vertex outside it.2

This is safe because the algorithm always chooses a light edge across the cut $(S, V-S)$, where $S$ is the set of vertices already in the tree.2 By the cut property, that edge can be included in some MST, so repeating this choice eventually builds an MST.

Key ideas used by Prim's algorithm:

• the graph must be connected, weighted, and undirected for a full MST to exist.2
• the partial solution always remains a single tree, unlike Kruskal's algorithm which may maintain a forest temporarily.2
• the algorithm ends when all vertices are included, yielding exactly $V-1$ selected edges.2

A common efficient implementation uses an adjacency list and a priority queue to track the cheapest edge reaching each outside vertex.2

3

Footnotes

1. Introduction to Algorithms - Describes Prim's algorithm as a greedy MST method and contrasts it with Kruskal. ↩ ↩² ↩³

2. Prim's algorithm - Wikipedia - Provides the high-level procedure and discusses data-structure-dependent complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Introduction to Algorithms Spanning Trees and Cuts Cut Property - States the cut property and explains why the lightest crossing edge is safe. ↩ ↩² ↩³ ↩⁴

4. Minimum Spanning Trees - Princeton Algorithms - Explains connectedness requirements and formal MST conditions. ↩

5. Minimum Spanning Trees - Princeton Algorithms - Notes that disconnected graphs lead to minimum spanning forests rather than a single MST. ↩

6. Minimum spanning trees - Defines spanning trees and MSTs, including tree properties and examples. ↩ ↩²

7. Prim's algorithm using priority_queue in STL - GeeksforGeeks - Details practical priority-queue implementation and typical $O(E \log V)$ complexity. ↩ ↩²

Worked Example of Prim's Algorithm

Consider the following weighted graph with vertices $A, B, C, D, E$:

We will start Prim's algorithm from vertex $A$. The goal is to build a tree connecting all vertices with minimum total weight.2

At each stage, choose the lightest edge leaving the current tree:

1. Start with $A$
2. Choose $A-B$ with weight $2$
3. From $\{A,B\}$, choose $B-C$ with weight $1$
4. From $\{A,B,C\}$, choose $B-D$ with weight $4$
5. From $\{A,B,C,D\}$, choose $C-E$ with weight $6$

So the MST edges are:

$$\{(A,B), (B,C), (B,D), (C,E)\}$$

and the total weight is

$$2 + 1 + 4 + 6 = 13$$

This tree spans all five vertices, has exactly $5-1=4$ edges, and contains no cycle, so it is a spanning tree. Because Prim's greedy selections are safe, it is an MST.3

Footnotes

1. Minimum spanning trees - Defines spanning trees and MSTs, including tree properties and examples. ↩

2. Prim's algorithm - Wikipedia - Provides the high-level procedure and discusses data-structure-dependent complexity. ↩ ↩²

3. Introduction to Algorithms Spanning Trees and Cuts Cut Property - States the cut property and explains why the lightest crossing edge is safe. ↩

4. Introduction to Algorithms - Describes Prim's algorithm as a greedy MST method and contrasts it with Kruskal. ↩

Time Complexity and Implementation Notes

The efficiency of Prim's algorithm depends on the data structures used.2

In practice:

• For dense graphs, $O(V^2)$ implementations can be acceptable.
• For sparse graphs, adjacency lists with a priority queue are usually preferred because they scale better.2

The priority queue stores, for each outside vertex, the smallest known edge weight connecting it to the current tree. When a lighter connection is found, its key is updated. This is analogous in style to Dijkstra's method, but the objective is different: Prim optimizes tree weight, not source-to-vertex distance.2

Footnotes

1. Prim's algorithm - Wikipedia - Provides the high-level procedure and discusses data-structure-dependent complexity. ↩ ↩² ↩³ ↩⁴

2. Prim's algorithm using priority_queue in STL - GeeksforGeeks - Details practical priority-queue implementation and typical $O(E \log V)$ complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Introduction to Algorithms - Describes Prim's algorithm as a greedy MST method and contrasts it with Kruskal. ↩

Conceptual Summary

Prim's algorithm solves the MST problem by repeatedly expanding a connected partial tree with the cheapest valid edge.2 Its correctness follows from the cut property, and its output is a minimum-cost acyclic connector of all vertices.2

For the sample graph, the algorithm selected:

$$AB(2),\; BC(1),\; BD(4),\; CE(6)$$

giving total weight:

$$13$$

This illustrates the central principle of MST construction: choose edges that improve global connectivity at minimum cumulative cost, not edges that merely give short routes from one source.2

Footnotes

1. Introduction to Algorithms Spanning Trees and Cuts Cut Property - States the cut property and explains why the lightest crossing edge is safe. ↩ ↩²

2. Prim's algorithm - Wikipedia - Provides the high-level procedure and discusses data-structure-dependent complexity. ↩ ↩²

3. Introduction to Algorithms - Describes Prim's algorithm as a greedy MST method and contrasts it with Kruskal. ↩ ↩²