Exploring Time Complexity of Prim’s Algorithm in C++

The Prim's algorithm is used to find the minimum spanning tree of a connected, undirected, and weighted graph.

In this article, we'll analyze the time complexity of the Prim's algorithm.

---

How Does Prim's Algorithm Work?

Prim's algorithm:

1. Chooses a starting vertex and add it to the MST.
2. Adds the edge with the least weight that connects a vertex in MST with the remaining vertices.
3. Repeat the previous step until all vertices are included in the MST.

vector<pair<int, int>> prim_mst(int start) const {

    // 1. Initialization
    vector<bool> in_mst(V, false);
    vector<int> key(V, INT_MAX);
    vector<int> parent(V, -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
 
    pq.emplace(0, start);
    key[start] = 0;
 
    // 2. Priority Queue Operations
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
 
        if (in_mst[u]) continue;
        in_mst[u] = true;

        // 3. Edge Relaxation
        for (const auto& [weight, v] : adj_list[u]) {
            if (!in_mst[v] && weight < key[v]) {
                key[v] = weight;
                pq.emplace(key[v], v);
                parent[v] = u;
            }
        }
    }
 
    vector<pair<int, int>> mst_edges;
    // 4. MST Construction
    for (int v = 1; v < V; ++v) {
        if (parent[v] != -1) {
            mst_edges.emplace_back(parent[v], v);
        }
    }

    return mst_edges;
}

---

Time Complexity

The time complexity of the Prim's algorithm can be broken down into the following components:

1. Initialization

The algorithm initializes vectors (in_mst, key, parent) and a priority queue pq to store vertices to be processed.

These initializations take O(V) time, where V is the number of vertices in the graph.

2. Priority Queue Operations

The time complexity of all priority queue operations, such as pop() and emplace(), is O(logV).

In the code, each vertex u is being processed. Thus, we get a complexity of O(V) due to pop operations.

Therefore, the total time complexity of priority queue operations is O(VlogV).

3. Edge Relaxation

The algorithm iterates over the adjacency list of each vertex and relaxes the edges by updating the minimum weight of each vertex.

This operation is nested inside the priority queue operation. The time complexity of this step is O(E), where E is the number of edges in the graph.

Since this iteration is nested inside the outer loop that iterates over the vertices, the total time complexity of this step is actually O(E + VlogV).

4. MST Construction

The algorithm constructs the MST by iterating over the vertices. Since the iteration takes place for V vertices, the time complexity of this step is O(V).

Overall Time Complexity

The overall time complexity of the Prim's algorithm is the sum of all the above steps:

O(V) + O(E + VlogV) + O(V)

Since O(E + VlogV) dominates other computing costs, the total complexity is O(E + VlogV).

Overall Time Complexity: O(E + VlogV)

---

Factors Affecting the Time Complexity

1. Dense Graph

In a dense graph, the number of edges E is close to the square of the number of vertices V. Thus, the time complexity of the algorithm is dominated by the edge relaxation step.

Therefore, the overall time complexity is <katex>O(V^{2} + VlogV) = O(V^{2})</katex>.

2. Sparse Graph

In a sparse graph, the number of edges E is close to the number of vertices V. Thus, the time complexity of the algorithm is dominated by the priority queue operations.

Therefore, the overall time complexity is O(VlogV + V) = O(VlogV).