Prim's Algorithm - Minimum Spanning Tree - C++ and Java

Welcome to Chapter 45 of the Graph - DSA series. In this chapter, we explore Prim's Algorithm, a classic greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, undirected, connected graph.

1. Why Do We Need Prim's Algorithm? (Problem Statement & Status Quo)

When working with network designs (such as electrical grids, local area networks, or road systems), we often need to connect a set of vertices using the minimum possible total edge weight without creating any cycles.

• Minimum Spanning Tree (MST): A subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles, and with the minimum possible total edge weight.
• Why Prim's?: While Kruskal's algorithm focuses on sorting and merging edge sets using Disjoint Set Union (DSU), Prim's Algorithm focuses on a vertex-centric growth approach. It starts from an arbitrary node and greedily grows the MST edge by edge, always picking the smallest available edge that connects the visited component to an unvisited node.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Expanding a Power Grid

Imagine you are tasked with connecting several houses (vertices) to a central power plant using cables (weighted edges) such that every house has power, all houses are connected, and you spend the absolute minimum amount of money on cable length.

• You start at House 0 (your starting point, now "powered" or visited).
• You look at all the available cables leading out from the powered houses to unpowered houses.
• You greedily pick the shortest (cheapest) cable available, connect the new house, and now consider that new house as part of the powered network.
• You repeat this process, always expanding from the currently powered network using the cheapest available bridge, until all houses are powered.

3. Initial Configuration & Data Structures

To implement Prim's algorithm efficiently, we initialize three main components:

1. Min-Priority Queue (std::priority_queue in C++):
   • Stores tuples of (weight, node) or (weight, node, parent) depending on whether you need just the MST weight or the actual tree edges.
   • Automatically bubbles the smallest weight to the top (Min-Heap property).
2. Visited Array (vis):
   • A boolean/integer array of size $V$ initialized to $0$ (unvisited) to keep track of nodes already included in the MST. This prevents cycles.
3. MST Weight Accumulator (sum):
   • An integer initialized to $0$ that accumulates the total weight of the MST edges.

4. Step-by-Step Evolution of the Algorithm

Let us trace Prim's algorithm execution on a sample graph with vertices 0, 1, 2, 3, 4.

Initial Setup

• Push (weight = 0, node = 0, parent = -1) into the Priority Queue.
• sum = 0, vis = [0, 0, 0, 0, 0].

Iteration Trace

1. Pop (0, 0, -1):
   • Parent is -1 (first node), so do not add to MST sum yet.
   • Mark 0 as visited (vis[0] = 1).
   • Look at adjacent nodes of 0: Node 1 (weight 2) and Node 2 (weight 1). Push both into PQ: (2, 1, 0) and (1, 2, 0).
2. Pop (1, 2, 0) (Min weight from PQ):
   • Node 2 is unvisited.
   • Add weight 1 to sum (sum = 1).
   • Mark 2 as visited (vis[2] = 1).
   • Push unvisited adjacent nodes of 2 into PQ: Node 1 (weight 1), Node 4 (weight 2), Node 3 (weight 2).
3. Pop (1, 1, 2) (Min weight from PQ):
   • Node 1 is unvisited.
   • Add weight 1 to sum (sum = 1 + 1 = 2).
   • Mark 1 as visited (vis[1] = 1).
   • Inspect adjacent nodes: All neighbors of 1 (0 and 2) are already visited.
4. Pop (2, 3, 2):
   • Node 3 is unvisited.
   • Add weight 2 to sum (sum = 2 + 2 = 4).
   • Mark 3 as visited (vis[3] = 1).
   • Push unvisited adjacent nodes of 3: Node 4 (weight 1).
5. Pop (1, 4, 3):
   • Node 4 is unvisited.
   • Add weight 1 to sum (sum = 4 + 1 = 5).
   • Mark 4 as visited (vis[4] = 1).
   • Inspect adjacent nodes: All visited.
6. Remaining PQ Elements:
   • Remaining elements ((2, 1, 0), (2, 2, 3), etc.) are popped, but their nodes are already visited, so they are ignored.

• Final MST Weight Sum: 5.

5. Complete Flow Walkthrough (Text Diagram)

6. Real-World Practical Pitfalls & Edge Cases

• Graph Disconnection: Prim's algorithm assumes the input graph is connected. If the graph has multiple disconnected components, a standard single-source start will only span the component containing the starting node. For disconnected graphs, an outer loop over all vertices is required to check if (!vis[i]).
• Lazy Deletion / Duplicate Entries: In standard priority queues where edge weights might decrease, older heavier edges to the same node might remain in the PQ. The vis check at the top of the processing loop handles this safely by discarding already-visited nodes.
• Parent Tracking for Actual MST Structure: If the problem asks for the actual edges of the MST rather than just the sum, store triplets (weight, node, parent) in the PQ and record valid edges whenever a node is marked visited.

7. Complete Code Implementation (C++ and Java)

Below is the production-ready code to compute the Minimum Spanning Tree sum using Prim's Algorithm.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector<vector<int>> adj[]) {
        // Priority queue stores pairs of {weight, node} (Min-Heap)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        vector<int> vis(V, 0);
        
        // {weight, node} -> start with node 0, weight 0
        pq.push({0, 0});
        int sum = 0;

        while (!pq.empty()) {
            auto it = pq.top();
            pq.pop();

            int node = it.second;
            int wt = it.first;

            // If the node is already visited, skip it
            if (vis[node] == 1) continue;

            // Mark as visited and add weight to MST sum
            vis[node] = 1;
            sum += wt;

            // Traverse all adjacent nodes
            for (auto it : adj[node]) {
                int adjNode = it[0];
                int edW = it[1];
                
                if (!vis[adjNode]) {
                    pq.push({edW, adjNode});
                }
            }
        }
        return sum;
    }
};

Java Implementation

import java.util.*;

class Pair {
    int node;
    int distance;

    public Pair(int distance, int node) {
        this.distance = distance;
        this.node = node;
    }
}

class Solution {
    // Function to find sum of weights of edges of the Minimum Spanning Tree.
    static int spanningTree(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj) {
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>((x, y) -> x.distance - y.distance);
        int[] vis = new int[V];
        
        // {weight, node} -> start with node 0, weight 0
        pq.add(new Pair(0, 0));
        int sum = 0;

        while (!pq.isEmpty()) {
            Pair it = pq.peek();
            pq.remove();
            int node = it.node;
            int wt = it.distance;

            // If the node is already visited, skip it
            if (vis[node] == 1) continue;

            // Mark as visited and add weight to MST sum
            vis[node] = 1;
            sum += wt;

            // Traverse all adjacent nodes
            for (int i = 0; i < adj.get(node).size(); i++) {
                int adjNode = adj.get(node).get(i).get(0);
                int edW = adj.get(node).get(i).get(1);
                
                if (vis[adjNode] == 0) {
                    pq.add(new Pair(edW, adjNode));
                }
            }
        }
        return sum;
    }
}

8. Complexity Analysis

Summary and Key Takeaways

• Greedy Paradigm: Prim's Algorithm greedily expands the MST by always selecting the minimum weight edge connected to the currently visited component.
• Starting Point Independence: You can start Prim's algorithm from any arbitrary vertex (e.g., node 0), and it will still arrive at the correct Minimum Spanning Tree.
• Visited Array Protection: Marking a node as visited only when it is popped from the priority queue (rather than when it is pushed) correctly prevents cycles and redundant edge processing.
• Priority Queue Efficiency: Using a Min-Heap ensures $O(\log N)$ retrieval of the minimum weight edge at every expansion step.
• Edge vs. Weight Requirement: If only the MST weight sum is needed, storing (weight, node) in the PQ is sufficient; tracking parent pointers is only necessary if the explicit tree edges must be reconstructed.