Prim’s Algorithm (Minimum Spanning Tree)

Prim’s algorithm is a greedy method for finding a Minimum Spanning Tree (MST) in a weighted, undirected graph. An MST is a subset of the graph’s edges that connects all vertices together without any cycles and with the minimum possible total edge weight.

---

How It Works

1. Initialization:
   • Start from an arbitrary vertex and mark it as part of the MST.
   • Maintain two sets of vertices: one included in the MST and the other not yet included.
2. Selection of Edge:
   • At each step, look for the smallest weighted edge that connects a vertex in the MST to a vertex outside the MST.
   • Add both the edge and the connected vertex to the MST.
3. Repeat:
   • Continue this process until all vertices are included in the MST.

The algorithm always picks the next minimum edge that expands the growing tree, ensuring that the total weight remains as low as possible.

---

Example

Consider a graph with 5 vertices labeled A, B, C, D, and E with the following weighted edges:

• Edge (A, B) with weight 2
• Edge (A, C) with weight 3
• Edge (B, C) with weight 1
• Edge (B, D) with weight 4
• Edge (C, D) with weight 5
• Edge (C, E) with weight 6
• Edge (D, E) with weight 7

Step-by-Step Process:

1. Start at Vertex A:
   • MST Set: {A}
   • Outgoing edges from A:
     • (A, B): weight 2
     • (A, C): weight 3
   • Choose: (A, B) because 2 is the minimum.
   • MST now contains: A, B and edge (A, B).
2. Expand the MST (Now contains A, B):
   • Look at edges from A and B to vertices not yet in the MST:
     • From A: (A, C) with weight 3
     • From B: (B, C) with weight 1 and (B, D) with weight 4
   • Choose: (B, C) with weight 1.
   • MST now contains: A, B, C and edges (A, B), (B, C).
3. Continue Expanding (MST now: A, B, C):
   • Consider edges from the current MST to outside vertices:
     • From B: (B, D) with weight 4
     • From C: (C, D) with weight 5 and (C, E) with weight 6
   • Choose: (B, D) with weight 4.
   • MST now contains: A, B, C, D and edges (A, B), (B, C), (B, D).
4. Final Expansion (MST now: A, B, C, D):
   • The only vertex left is E.
   • Consider edges connecting to E:
     • From C: (C, E) with weight 6
     • From D: (D, E) with weight 7
   • Choose: (C, E) with weight 6.
   • MST now contains: A, B, C, D, E and edges (A, B), (B, C), (B, D), (C, E).

Final MST:

• Edges: (A, B): 2, (B, C): 1, (B, D): 4, (C, E): 6
• Total Weight: (2 + 1 + 4 + 6 = 13)

---

Summary

Prim’s Algorithm builds a minimum spanning tree by starting from an arbitrary vertex and, at each step, adding the least expensive edge that connects a vertex in the tree to a vertex outside it. This process continues until all vertices are included in the tree, ensuring the total edge weight is minimized.