Prim's Algorithm

A spanning tree of a graph consists of all vertices and some of the edges of the graph so that there is a path between any two vertices. Therefore, spanning trees are connected and acyclic. Consider the graph below:

One possible spanning tree for the above graph is:

The weight of a spanning tree is defined as sum of the weights of all the edges of it. For instance, weight of the above spanning tree is 3 + 5 + 9 + 3 + 2 = 22.

A minimum spanning tree (MST) is a spanning tree whose weight is as low as possible. For example, the weight of the minimum spanning tree of the example graph is 20. One such MST can be drawn like this:

Note: MST is not unique and a graph can have several MSTs.

This implementation of Prim’s Algorithm is pretty much similar to Dijkstra’s Algorithm and works well with sparse graphs.

Time Complexity: O(n + mlogm) where n: number of vertices and m: number of edges

Pseudo code for Prim’s Algorithm

PrimMST(Graph,V) # Graph is represented here using adjacency matrix.
{
	int key[V] = {INT_MAX};
	bool set[V] = {false};
	priority_queue<pair<int,int>> pq;
	key[0] = 0;
	pq.push({0,0});
	while pq is not Empty:
		u = pq.top().second;
		pq.pop();
		if(set[u]) continue;
		set[u] = true;
		
		for i = 1 to i = V:
		 if(graph[u][v]!=INT_MAX && !set[v] && graph[u][v]<key[v]):
		  key[v] = graph[u][v];
		  pq.push({-key[v],v});

}

References: GeeksforGeeks,cp-algorithms