Understanding Prim's Algorithm for Minimum Spanning Trees

Prim's algorithm is a fundamental greedy algorithm in graph theory that helps us find the minimum spanning tree (MST) of a connected weighted graph. In this post, I'll break down how Prim's algorithm works and walk through a C++ implementation that efficiently solves this classic problem. What is a Minimum Spanning Tree? Before diving into the algorithm, let's clarify what we're trying to achieve. A spanning tree of a graph is a tree that includes all vertices of the graph with the minimum possible number of edges. When our graph has weighted edges, a minimum spanning tree is a spanning tree where the total weight of all edges is minimized. Minimum spanning trees have numerous real-world applications: Network design (telecommunications, electrical grids) Cluster analysis Circuit design Transportation planning Approximation algorithms for NP-hard problems like the Traveling Salesman Problem How Prim's Algorithm Works Prim's algorithm builds the MST one vertex at a time, starting from an arbitrary vertex and growing the tree by adding the lowest-weight edge connecting the tree to a vertex not yet in the tree. Here's the basic approach: Start with any vertex as a single-vertex tree Grow the tree by adding the minimum-weight edge that connects the tree to a vertex not yet in the tree Repeat step 2 until all vertices are included in the tree The C++ Implementation Let's analyze the C++ code that implements Prim's algorithm: #include #include #include using namespace std; // Function to find the minimum spanning tree using Prim's algorithm int primMST(vector &graph, int V) { // Create a priority queue to store the edges priority_queue pq; // Create a vector to store the minimum weight of each vertex vector key(V, INT_MAX); // Create a vector to store the parent of each vertex in the MST vector parent(V, -1); // Create a vector to track if a vertex is included in the MST vector inMST(V, false); // Set the key of the first vertex to 0 key[0] = 0; // Add the first vertex to the priority queue pq.push({0, 0}); // Loop until the priority queue is empty while (!pq.empty()) { // Extract the vertex with the minimum key from the priority queue int u = pq.top().second; pq.pop(); // Mark the vertex as included in the MST inMST[u] = true; // Loop through all the vertices for (int v = 0; v

Apr 22, 2025 - 12:17

Understanding Prim's Algorithm for Minimum Spanning Trees

Prim's algorithm is a fundamental greedy algorithm in graph theory that helps us find the minimum spanning tree (MST) of a connected weighted graph. In this post, I'll break down how Prim's algorithm works and walk through a C++ implementation that efficiently solves this classic problem.

What is a Minimum Spanning Tree?

Before diving into the algorithm, let's clarify what we're trying to achieve. A spanning tree of a graph is a tree that includes all vertices of the graph with the minimum possible number of edges. When our graph has weighted edges, a minimum spanning tree is a spanning tree where the total weight of all edges is minimized.

Minimum spanning trees have numerous real-world applications:

Network design (telecommunications, electrical grids)
Cluster analysis
Circuit design
Transportation planning
Approximation algorithms for NP-hard problems like the Traveling Salesman Problem

How Prim's Algorithm Works

Prim's algorithm builds the MST one vertex at a time, starting from an arbitrary vertex and growing the tree by adding the lowest-weight edge connecting the tree to a vertex not yet in the tree. Here's the basic approach:

Start with any vertex as a single-vertex tree
Grow the tree by adding the minimum-weight edge that connects the tree to a vertex not yet in the tree
Repeat step 2 until all vertices are included in the tree

The C++ Implementation

Let's analyze the C++ code that implements Prim's algorithm:

#include 
#include 
#include 
using namespace std;

// Function to find the minimum spanning tree using Prim's algorithm
int primMST(vector<vector<int>> &graph, int V)
{
    // Create a priority queue to store the edges
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // Create a vector to store the minimum weight of each vertex
    vector<int> key(V, INT_MAX);

    // Create a vector to store the parent of each vertex in the MST
    vector<int> parent(V, -1);

    // Create a vector to track if a vertex is included in the MST
    vector<bool> inMST(V, false);

    // Set the key of the first vertex to 0
    key[0] = 0;

    // Add the first vertex to the priority queue
    pq.push({0, 0});

    // Loop until the priority queue is empty
    while (!pq.empty())
    {
        // Extract the vertex with the minimum key from the priority queue
        int u = pq.top().second;
        pq.pop();

        // Mark the vertex as included in the MST
        inMST[u] = true;

        // Loop through all the vertices
        for (int v = 0; v < V; v++)
        {
            // If the vertex is not included in the MST and there is an edge between u and v
            if (!inMST[v] && graph[u][v] != 0)
            {
                // If the weight of the edge is smaller than the current key of v
                if (graph[u][v] < key[v])
                {
                    // Update the key of v
                    key[v] = graph[u][v];

                    // Update the parent of v
                    parent[v] = u;

                    // Add v to the priority queue
                    pq.push({key[v], v});
                }
            }
        }
    }

    // Calculate the total weight of the MST
    int totalWeight = 0;
    for (int i = 1; i < V; i++)
    {
        totalWeight += graph[i][parent[i]];
    }

    return totalWeight;
}

int main()
{
    // Number of vertices
    int V = 5;

    // Adjacency matrix representation of the graph
    vector<vector<int>> graph = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}};

    // Find the minimum spanning tree
    int totalWeight = primMST(graph, V);

    // Print the total weight of the MST
    cout << "Total weight of the minimum spanning tree: " << totalWeight << endl;

    return 0;
}

Key Components of the Implementation

Data Structures

Priority Queue: We use a min-priority queue to always select the edge with the minimum weight. The queue stores pairs of {weight, vertex}.
Key Vector: Stores the minimum weight of the edge that connects each vertex to the MST being constructed.
Parent Vector: Tracks the parent of each vertex in the MST, allowing us to reconstruct the tree if needed.
inMST Vector: Keeps track of which vertices have already been included in the MST.

Time Complexity Analysis

The main loop runs V times (once for each vertex)
For each vertex, we may add at most V-1 entries to the priority queue
Each extract-min operation takes O(log E) time
Overall time complexity: O(E log V), where E is the number of edges and V is the number of vertices

When using an adjacency matrix as in our implementation (which has V² potential edges), the time complexity becomes O(V² log V).

Visualizing the Process

Let's see how the algorithm works on our example graph with 5 vertices:

We start at vertex 0
We examine all edges from vertex 0: (0,1) with weight 2 and (0,3) with weight 6
We select the edge with minimum weight: (0,1) with weight 2
From the vertices now in our tree (0 and 1), we look at all edges to vertices not yet in the tree
We continue this process until all vertices are included

The final MST has a total weight of 16, which consists of the edges:

(0,1) with weight 2
(1,2) with weight 3
(1,4) with weight 5
(0,3) with weight 6

Advantages of Prim's Algorithm

Simplicity: The algorithm is conceptually straightforward
Efficiency: Works well for dense graphs
Guaranteed optimality: Always finds the minimum spanning tree

When to Use Prim's vs. Kruskal's

Prim's algorithm is one of two popular algorithms for finding MSTs, the other being Kruskal's algorithm. While both produce the same result, they differ in approach:

Prim's grows a single tree from a starting vertex
Kruskal's builds a forest of trees that eventually merge into a single MST

Prim's algorithm tends to perform better on dense graphs, while Kruskal's may be faster on sparse graphs.

Conclusion

Prim's algorithm is an elegant and efficient solution for finding minimum spanning trees. The implementation we explored uses a priority queue to optimize the selection of the next edge, making it suitable for practical applications on large graphs.

By understanding this algorithm, you gain insight into an important technique in graph theory that has numerous real-world applications. Whether you're designing networks, analyzing data clusters, or solving complex optimization problems, Prim's algorithm is a valuable tool in your algorithmic toolkit.

If you found this helpful, feel free to share your thoughts in the comments! What other graph algorithms would you like to explore next?