Graphs 101: Prim’s Algorithm

In the previous part of our Graph Series, we introduced Minimum Spanning Trees (MST) and explained why they are important for cost-efficient connectivity in graphs.

In this part, we will focus entirely on Prim’s Algorithm and understand how it actually builds a Minimum Spanning Tree, step by step, followed by its implementation.

So let’s get started…

What Does Prim’s Algorithm Do?

Prim’s Algorithm is used to:

• Construct a Minimum Spanning Tree
• Connect all the vertices of a graph
• Minimize the total edge weight
• Avoid cycles

The algorithm grows the MST one vertex at a time, starting from any chosen vertex.

Core Idea Behind Prim’s Algorithm

The idea behind Prim’s Algorithm is simple:

Get Shruti Pokale’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

At every step:

• Select the minimum-weight edge
• That connects a vertex already in the MST
• To a vertex not yet included

This greedy choice ensures that the total cost remains minimum.

Step-by-Step Intuition of Prim’s Algorithm

Step 1: Initialization

We maintain three things:

• inMST[]
  Tracks whether a vertex is already included in the MST.
• key[]
  Stores the minimum cost required to connect each vertex to the MST.
• parent[]
  Stores the MST structure.
  If parent[v] = u, it means edge (u, v) is part of the MST.

Initialization:

• Start from the vertex 0
• Set key[0] = 0
• Set all other key values to infinity
• Mark all vertices as not included in the MST

Step 2: Pick the Minimum Key Vertex

• From all vertices not yet in the MST, select the vertex with the smallest key value.
• This vertex is the next safest and cheapest choice to expand the MST.

Step 3: Include the Vertex in MST

• Mark the selected vertex as included
• Add its key value to the total MST cost

Step 4: Update Adjacent Vertices

For each neighbor of the selected vertex:

• If the neighbor is not already in the MST
• And the edge weight is smaller than its current key value

Then:

• Update the key value
• Update the parent of that vertex

Step 5: Repeat

Repeat Steps 2 to 4 until:

• All vertices are included in the MST
• Exactly V − 1 edges are chosen

Two Ways to Implement Prim’s Algorithm

Prim’s Algorithm can be implemented in two common ways:

• Using a Priority Queue (optimized)
• Without using a priority queue (simple array-based approach)

Both follow the same logic. Only the selection of the minimum key vertex differs.

Using Priority Queue

This approach uses a min heap to efficiently select the minimum-weight edge.

How It Works

• Start from the vertex 0
• Push (weight, node) into the priority queue
• Always extract the minimum-weight edge
• Skip nodes already included in the MST
• Push valid adjacent edges into the queue

C++ Implementation (Using Priority Queue)

class Solution
{
    typedef pair<int, int> P;
public:
    int spanningTree(int V, vector<vector<int>> adj[]) {
        priority_queue<P, vector<P>, greater<P>> pq;
        pq.push({0, 0}); // {weight, node}
        vector<bool> inMST(V, false);
        int sum = 0;
        while(!pq.empty()) {
            auto p = pq.top();
            pq.pop();
            int wt   = p.first;
            int node = p.second;
            if(inMST[node])
                continue;
            inMST[node] = true;
            sum += wt;
            for(auto &tmp : adj[node]) {
                int neighbor    = tmp[0];
                int neighbor_wt = tmp[1];
                if(!inMST[neighbor]) {
                    pq.push({neighbor_wt, neighbor});
                }
            }
        }
        return sum;
    }
};

Without Using Priority Queue

This is the simpler version, ideal for understanding the algorithm clearly. Instead of a heap, we linearly search for the minimum key vertex.

How It Works

• Find Minimum Key Vertex
• Use Prim’s Algorithm Logic

int minKey(int V, vector<bool> inMST, vector<int> key) {
    int minValue = INT_MAX;
    int min_index;
for(int v = 0; v < V; v++) {
        if(!inMST[v] && key[v] < minValue) {
            min_index = v;
            minValue  = key[v];
        }
    }
    return min_index;
}
int spanningTree(int V, int E, vector<vector<int>> &graph) {
    vector<int> key(V, INT_MAX);
    vector<int> parent(V);
    vector<bool> inMST(V, false);
parent[0] = -1;
    key[0] = 0; // Start from vertex 0
    for(int count = 1; count <= V - 1; count++) {
        int u = minKey(V, inMST, key);
        inMST[u] = true;
        for(int v = 0; v < V; v++) {
            if(graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {
                key[v]    = graph[u][v];
                parent[v] = u;
            }
        }
    }
    int sum = 0;
    for(int i = 1; i < V; i++) {
        sum += key[i];
    }
    return sum;
}

Time Complexity

• Without Priority Queue: O(V²)
• With Priority Queue: O(E log V)

Key Takeaways

• Prim’s Algorithm builds a Minimum Spanning Tree greedily
• It expands the tree from a starting vertex
• At each step, the minimum-cost edge is chosen
• Both implementations follow the same logic
• Understanding the simple version makes the optimized version easier

What’s Next?

After understanding what a Minimum Spanning Tree is, we have now seen how Prim’s Algorithm builds an MST step by step, along with its practical implementations.

In the next part, we will study Kruskal’s Algorithm, another greedy approach to finding a Minimum Spanning Tree. Stay tuned 😄