Prim's Algorithm

A greedy algorithm to find MST of a graph. Starts with a single vertex. Discovered edges are stored in a priority queue. In each turn, MST grows by 1 edge which is the smallest in the discovered edgegs and would not cause a cycle.

Steps

1. Initialize a set to keep track of vertices included in MST
2. Assign key value of $0$ to the first vertex and $\infty$ to all others
3. While MST doesn’t include all vertices:
   • Pick the vertex with minimum key value not yet included in MST
   • Include this vertex in MST
   • Update key values of adjacent vertices: if the weight of edge is less than the current key value, update the key value

Works particularly well for dense graphs where the number of edges is close to the maximum possible.

Implementation

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int V = 6; // Number of vertices

// Function to find the vertex with the minimum key value from the set of vertices not yet included in MST
int minKey(vector<int>& key, vector<bool>& mstSet) {
    int min = INT_MAX, min_index = -1;

    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }

    return min_index;
}

// Function to print the constructed MST
void printMST(vector<int>& parent, vector<vector<int>>& graph) {
    cout << "Edge \tWeight\n";
    for (int i = 1; i < V; i++) {
        cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << "\n";
    }
}

// Function to construct and print MST for a graph represented using adjacency matrix
void primMST(vector<vector<int>>& graph) {
    vector<int> parent(V); // Array to store constructed MST
    vector<int> key(V, INT_MAX); // Key values used to pick minimum weight edge
    vector<bool> mstSet(V, false); // To represent set of vertices included in MST

    // Always include the first vertex in MST
    key[0] = 0; // Make key 0 so that this vertex is picked as the first vertex
    parent[0] = -1; // First node is always the root of MST

    // The MST will have V vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum key vertex from the set of vertices not yet included in MST
        int u = minKey(key, mstSet);

        // Add the picked vertex to the MST set
        mstSet[u] = true;

        // Update key value and parent index of the adjacent vertices of the picked vertex
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    // Print the constructed MST
    printMST(parent, graph);
}

int main() {
    // Example graph representation using adjacency matrix
    vector<vector<int>> graph = {
        { 0, 1, 0, 4, 3, 0 },
        { 1, 0, 2, 0, 5, 0 },
        { 0, 2, 0, 0, 0, 6 },
        { 4, 0, 0, 0, 7, 0 },
        { 3, 5, 0, 7, 0, 8 },
        { 0, 0, 6, 0, 8, 0 }
    };

    // Print the MST
    primMST(graph);

    return 0;
}

Example

1. Start with vertex A (arbitrary starting point):

   • Include A in the MST
   • Set key value of A to 0, all others to infinity

2. Update key values of vertices adjacent to A:

   • B: key = 1
   • D: key = 4
   • E: key = 3

3. Select B (minimum key among unvisited vertices):

   • Include B in the MST
   • Edge added: (A-B, 1)
   • Update adjacent vertices’ keys:
     • C: key = 2
     • E: already 3, no change

4. Select C (minimum key among unvisited vertices):

   • Include C in the MST
   • Edge added: (B-C, 2)
   • Update adjacent vertices’ keys:
     • F: key = 6

5. Select E (minimum key among unvisited vertices):

   • Include E in the MST
   • Edge added: (A-E, 3)
   • Update adjacent vertices’ keys:
     • D: already 4, no change
     • F: already 6, no change

6. Select D (minimum key among unvisited vertices):

   • Include D in the MST
   • Edge added: (A-D, 4)

7. Select F (minimum key among unvisited vertices):

   • Include F in the MST
   • Edge added: (C-F, 6)

The resulting MST will have the edges: (A-B, 1), (B-C, 2), (A-E, 3), (A-D, 4), (C-F, 6).

Time and Space Complexity

Time Complexity

Depends on the implementation of the graph and priority queue:

1. Using an adjacency matrix and an array for the priority queue:
   • Finding the minimum key value takes $O(V)$ time for each of the $V$ vertices, resulting in $O(V^2)$ overall.
   • Suitable for dense graphs ($E \sim V^2$)
2. Using an adjacency list and a binary heap for the priority queue:
   • Extracting the minimum key value takes $O(\log V)$ time for each vertex.
   • Updating the key values of adjacent vertices takes $O(\log V)$ for each edge, resulting in $O(E \log V)$ for all edges.
   • The overall time complexity is $O((V + E) \log V)$
   • Suitable for sparse graphs where $E \ll V^2$

Space Complexity

The space complexity of Prim’s algorithm is $O(V + E)$. $$

• $O(V)$ for storing the key values, parent array, and MST set.
• $O(E)$ for storing the graph representation (adjacency list or matrix).

Graph Type	Time Complexity	Space Complexity
Dense Graphs	$O(V^2)$	$O(V^2)$
Sparse Graphs	$O((V + E) \log V)$	$O(V + E)$