Minimum Spanning Tree: Prim's Algorithm

I. Problem Description
A Minimum Spanning Tree (MST) is a spanning tree of a weighted, connected graph that minimizes the total sum of edge weights. Prim's Algorithm is a greedy algorithm used to construct an MST. Its core idea is to start from a single vertex and iteratively grow the tree by always adding the minimum-weight edge that connects a vertex in the tree to a vertex outside the tree, until all vertices are included.

II. Detailed Algorithm Steps

1. Initialization

   • Choose any vertex from the graph as the starting point and add it to the MST set (denoted as MST).
   • Maintain an array key[] to record the minimum edge weight from each vertex to the MST. Initially, the starting vertex's key value is 0, and all others are infinity (indicating no connection yet).
   • Maintain an array parent[] to record the parent node of each vertex in the MST (used to construct the tree structure).

2. Greedy Selection and Expansion

   • Repeat the following steps until all vertices are added to the MST:
     a. From the vertices not yet in MST, select the vertex u with the minimum key value (i.e., the vertex currently closest to the MST).
     b. Add u to the MST.
     c. For each adjacent vertex v of u:
     If v is not in MST and the weight of edge (u, v) is less than the current key[v], then update key[v] = weight(u, v) and set parent[v] = u.

3. Termination Condition

   • The algorithm ends when all vertices are added to MST. At this point, the parent[] array defines the edges of the minimum spanning tree.

III. Example Demonstration
Consider the following weighted graph (vertices A, B, C, D with edge weights as shown):

    A --2-- B  
    |     / |  
    3   1   4  
    | /     |  
    C --5-- D  

Execution Process:

1. Start from A. key[A]=0, key values for other vertices are ∞.
2. Add A to MST. Update key values for adjacent vertices B and C: key[B]=2, key[C]=3.
3. Select vertex B (with minimum key=2) and add it to MST. Update key[D]=4 (adjacent to B). Check vertex C: edge weight B-C (1) is less than current key[C]=3, so update key[C]=1.
4. Select vertex C (with minimum key=1) and add it to MST. Check adjacent vertex D: edge weight C-D (5) is greater than current key[D]=4, so no update.
5. Finally, add D to MST. The resulting spanning tree edges are A-B, B-C, and B-D, with total weight = 2+1+4 = 7.

IV. Algorithm Complexity and Optimization

• Time Complexity:
  • Naive implementation (adjacency matrix + linear search for min key): O(V²), suitable for dense graphs.
  • Optimized implementation (adjacency list + min-heap): O(E log V), suitable for sparse graphs.
• Space Complexity: O(V) (for storing key and parent arrays).

V. Comparison with Kruskal's Algorithm

• Prim's algorithm is vertex-based and suitable for dense graphs; Kruskal's algorithm is edge-sorting based and suitable for sparse graphs.
• Both guarantee an optimal solution but employ different greedy strategies: Prim always maintains a single tree, while Kruskal may maintain multiple subtrees simultaneously (merging them via a union-find data structure).