Prim's Algorithm Minimum Spanning Tree (MST)

Given a connected, undirected, and weighted graph with V vertices and E edges, the goal is to find a Minimum Spanning Tree (MST). A Minimum Spanning Tree is a subset of the edges that connects all the vertices with the minimum possible total edge weight and without forming any cycles.

Prim's Algorithm helps us construct this MST by starting from a node and greedily choosing the next lightest edge that connects a visited node to an unvisited node.

Sometimes, the problem may also ask to return the MST edges themselves (i.e., a list of edge pairs {u, v} included in the MST).

Understanding the Problem

We are given a connected, weighted, undirected graph. Our task is to find a Minimum Spanning Tree (MST), which is a subset of edges that connects all vertices in the graph with the minimum possible total edge weight, and without forming any cycles.

Prim’s Algorithm helps us solve this problem using a greedy approach. At every step, it picks the smallest weight edge that connects a node already in the MST to a node outside of it. This ensures we keep the tree connected and avoid cycles.

Step-by-Step Solution with Example

Step 1: Choose a starting point

We start from an arbitrary node. Let’s say we begin from node 0.

Step 2: Add all edges from the start node to a Min Heap

This allows us to always access the smallest available edge. Each heap entry stores a tuple like (weight, from_node, to_node).

Step 3: Pop the smallest edge

We take the edge with the least weight from the heap. If the destination node is not yet in the MST, we add it to the MST and include this edge in our result.

Step 4: Add new edges from the newly included node

From the new node, push all edges to unvisited neighbors into the heap. This helps explore other possible minimum connections.

Step 5: Repeat until all nodes are in the MST

We continue this process of picking the smallest edge and expanding the MST until all vertices are included.

Step 6: Example

Let’s consider the following graph with 5 nodes and these edges:

Edges: 
0 --(1)-- 1
0 --(3)-- 2
1 --(1)-- 2
1 --(6)-- 3
2 --(5)-- 3
3 --(2)-- 4

We start at node 0:

• Add edges (0-1, weight 1) and (0-2, weight 3) to the heap.
• Pick edge (0-1). Add node 1 to MST. Total weight = 1
• Add edges (1-2, weight 1), (1-3, weight 6)
• Pick edge (1-2). Add node 2. Total weight = 2
• Add edge (2-3, weight 5)
• Pick edge (2-3). Add node 3. Total weight = 7
• Add edge (3-4, weight 2)
• Pick edge (3-4). Add node 4. Total weight = 9

Final MST edges: (0-1), (1-2), (2-3), (3-4)

Total weight of MST: 9

Edge Cases

• Single node graph: No edges, MST weight is 0.
• Disconnected graph: Prim’s Algorithm assumes the graph is connected. If not, we cannot form a valid MST.
• Multiple edges with same weight: The algorithm still works as it always chooses the minimum available weight. Tie-breaking is handled by heap order.
• Negative weight edges: Prim’s Algorithm can handle them safely, as it doesn’t depend on edge weight signs—only comparisons.

Finally

Prim’s Algorithm is an elegant and efficient way to find a Minimum Spanning Tree using a greedy approach. The use of a Min Heap ensures that we always pick the optimal next edge. For large graphs, the heap makes the algorithm run efficiently in O(E log V) time.

Understanding each step and visualizing the MST growth helps beginners grasp how the algorithm avoids cycles and ensures minimum total weight.

1. Initialize a minHeap and push the first node (weight 0, node 0).
2. Create a visited set to track included vertices.
3. Maintain a totalWeight and optionally an mstEdges list to store the MST edges.
4. While the heap is not empty and not all vertices are included:
1. Extract the edge with the smallest weight.
2. If the destination node is not visited, add it to the MST.
3. Add the edge’s weight to totalWeight.
4. Add all adjacent unvisited edges to the heap.
5. After the loop, totalWeight holds the MST cost and mstEdges (if used) contains the MST structure.