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
- Initialize a set to keep track of vertices included in MST
- Assign key value of
to the first vertex and to all others - 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 MSTint 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 MSTvoid 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 matrixvoid 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
-
Start with vertex A (arbitrary starting point):
- Include A in the MST
- Set key value of A to 0, all others to infinity
-
Update key values of vertices adjacent to A:
- B: key = 1
- D: key = 4
- E: key = 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
-
Select C (minimum key among unvisited vertices):
- Include C in the MST
- Edge added: (B-C, 2)
- Update adjacent vertices’ keys:
- F: key = 6
-
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
-
Select D (minimum key among unvisited vertices):
- Include D in the MST
- Edge added: (A-D, 4)
-
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:
- Using an adjacency matrix and an array for the priority queue:
- Finding the minimum key value takes
time for each of the vertices, resulting in overall. - Suitable for dense graphs (
)
- Finding the minimum key value takes
- Using an adjacency list and a binary heap for the priority queue:
- Extracting the minimum key value takes
time for each vertex. - Updating the key values of adjacent vertices takes
for each edge, resulting in for all edges. - The overall time complexity is
- Suitable for sparse graphs where
- Extracting the minimum key value takes
Space Complexity
The space complexity of Prim’s algorithm is
for storing the key values, parent array, and MST set. for storing the graph representation (adjacency list or matrix).
Graph Type | Time Complexity | Space Complexity |
---|---|---|
Dense Graphs | ||
Sparse Graphs |