1. What is a Spanning Tree and Minimum Spanning Tree?¶
In data structures, a graph consists of vertices (nodes) and edges. A spanning tree is a subgraph of a connected undirected graph that includes all vertices of the graph without cycles (i.e., it has the properties of a tree: n vertices have n-1 edges, and there is exactly one path between any two vertices).
For example, if there are 4 cities (vertices) A, B, C, D connected by roads (edges) forming a network without repeated roads or cycles, this is a spanning tree. A Minimum Spanning Tree (MST) is the spanning tree with the smallest sum of edge weights among all possible spanning trees.
For instance, if roads between cities have different lengths (weights), finding the shortest total length road network connecting all cities is an MST problem.
2. Greedy Algorithm: Why MST is Suitable for Greedy?¶
The core idea of a greedy algorithm is “choose the locally optimal solution at each step to achieve the globally optimal solution”. MST fits the greedy scenario because:
- A spanning tree must include all vertices with exactly n-1 edges (n = number of vertices).
- We only need to consider “local optimal” edge selection: selecting the smallest weight edge connecting the “selected vertices set” and “unselected vertices set” at each step builds the minimum total weight spanning tree incrementally.
3. Basic Idea of Prim’s Algorithm¶
Prim’s algorithm is one of the classic greedy algorithms for MST, with core steps:
- Initialization: Choose any vertex as the starting point (e.g., vertex v₀) and mark it as “selected”.
- Repeated Expansion: In each iteration, select the edge with the smallest weight from all edges connecting the “selected vertices set” and “unselected vertices set”, then add the corresponding unselected vertex to the “selected vertices set”.
- Termination: The spanning tree is complete when all vertices are added to the selected set.
4. Detailed Algorithm Steps with Example¶
To understand intuitively, let’s demonstrate Prim’s algorithm with a simple example:
Example Graph: 4 vertices A, B, C, D with edges and weights:
- A-B: 2, A-C: 3, B-C: 1, B-D: 4, C-D: 5
Vertex numbering: A=0, B=1, C=2, D=3.
Step 1: Select the Starting Point¶
Choose any starting point, e.g., A (vertex 0). Now:
- Selected vertices set S = {0} (only A)
- Unselected vertices set U = {1, 2, 3} (B, C, D)
Step 2: Find Minimum Edge and Expand¶
Repeat until all vertices are selected:
First Iteration:¶
S = {0}, U = {1, 2, 3}
Edges between S (0) and U (1,2,3):
- A-B (0-1): weight 2
- A-C (0-2): weight 3
The smallest edge is A-B (weight 2). Add B (1) to S:
S = {0, 1}, U = {2, 3}
Second Iteration:¶
S = {0, 1}, U = {2, 3}
Edges between S (0,1) and U (2,3):
- A-C (0-2): weight 3
- B-C (1-2): weight 1
- B-D (1-3): weight 4
The smallest edge is B-C (weight 1). Add C (2) to S:
S = {0, 1, 2}, U = {3}
Third Iteration:¶
S = {0, 1, 2}, U = {3}
Edges between S (0,1,2) and U (3):
- A-D (no direct edge)
- B-D (1-3): weight 4
- C-D (2-3): weight 5
The smallest edge is B-D (weight 4). Add D (3) to S:
S = {0, 1, 2, 3}, all vertices selected.
Final MST¶
Selected edges: A-B (2), B-C (1), B-D (4). Total weight = 2 + 1 + 4 = 7.
5. Algorithm Implementation and Details¶
1. Data Structure Representation¶
A graph can be represented by an adjacency matrix or adjacency list. For beginners, the adjacency matrix is more intuitive (2D array):
graph = [
[0, 2, 3, 0], # A's adjacents: A-B=2, A-C=3
[2, 0, 1, 4], # B's adjacents: B-A=2, B-C=1, B-D=4
[3, 1, 0, 5], # C's adjacents: C-A=3, C-B=1, C-D=5
[0, 4, 5, 0] # D's adjacents: D-B=4, D-C=5
]
Here, graph[i][j] represents the edge weight between vertex i and j (0 indicates no edge).
2. Core Steps Pseudocode¶
// Prim's Algorithm Pseudocode
function Prim(graph, n):
// n = number of vertices, graph = adjacency matrix
key = [INF] * n // key array: min edge weight to selected set
parent = [-1] * n // parent array: parent in MST
key[0] = 0 // start from vertex 0
selected = [False] * n // mark selected vertices
for i from 0 to n-1:
// Find u with minimum key and not selected
u = vertex with min key and selected[u] = False
selected[u] = True // add u to selected set
// Update key values of adjacent unselected vertices
for v from 0 to n-1:
if graph[u][v] > 0 and not selected[v] and graph[u][v] < key[v]:
key[v] = graph[u][v]
parent[v] = u
// Calculate total weight
total_weight = sum(key[1..n-1]) // key[0] = 0 (start), others are edge weights
return total_weight, parent
3. Time Complexity¶
- With an adjacency matrix: O(n²) (n iterations for outer loop, n for inner loop), suitable for dense graphs with few vertices.
- With adjacency list + priority queue optimization: O(m log n) (m = number of edges), suitable for sparse graphs.
6. Key Insights of Prim’s Algorithm¶
- Greedy Choice: Select the smallest edge connecting the selected and unselected sets at each step to ensure local optimality.
- Safety Edge Property: The total weight of the MST is guaranteed to be minimal regardless of the starting vertex (proven by mathematical induction; for beginners, it’s sufficient to trust the greedy strategy).
7. Application Scenarios¶
- Network Wiring: Laying fiber optics between cities with minimal cost.
- Circuit Design: Connecting electronic components with the least wire length.
- Traffic Planning: Designing road networks with minimal total length covering all regions.
Summary¶
The MST is a classic application of the greedy algorithm. Prim’s algorithm efficiently constructs the minimum total weight spanning tree by “expanding from the starting vertex and selecting the smallest edge each time”. Understanding its core idea (greedy choice) and steps is crucial for solving graph problems (e.g., shortest paths, network optimization). For beginners, practice with concrete examples (like the 4-vertex graph in this article) helps master implementation details.