Algorithms for Coding Interviews in C++/

...

/

Solution: Find the Minimum Spanning Tree - Prim's Solution

Solution: Find the Minimum Spanning Tree - Prim's Solution

In this review, we give a detailed analysis on finding the minimum spanning tree of the given graph using Prim's solution.

We'll cover the following...

Solution: Prim’s Algorithm Using Priority Queue

There is another method by which we can find the Minimum Spanning Tree of a graph; that is by using Priority Queue.

Note: We print only the edges of the graph in the following solution.

We use STL Priority Queue for our solution. If you want to get an idea of how they are used, have a look at the appendix.

Press + to interact
main.cpp
Graph.cpp
Graph.h
#include "Graph.h"
typedef pair<int, int> myPair; 
void Graph::primMST() { 
  //create a priority queue
  //the greater keyword will help make a kind of min heap
  //top element is the smallest
	priority_queue <myPair, vector <myPair> , greater <myPair>> myPriorityQueue; 
	int source = 0; 
	vector<int> key(this -> vertices, INF); 
	vector<int> parent(this -> vertices, -1); 
	vector<bool> inMinimumSpanningTree(this -> vertices, false); //initially no edge in MST
	myPriorityQueue.push(make_pair(0, source)); 
	key[source] = 0; 
	while (!myPriorityQueue.empty()) { 
		int u = myPriorityQueue.top().second; 
		myPriorityQueue.pop(); 
    
		inMinimumSpanningTree[u] = true; //THIS IS MINIMUM --> add in our list
		list< pair<int, int>>::iterator i; 
		for (i = adjacencyList[u].begin(); i != adjacencyList[u].end(); ++i) { 
			int v = (*i).first; 
			int weight = (*i).second; 
			if (inMinimumSpanningTree[v] == false && key[v] > weight) { 
				key[v] = weight; 
				myPriorityQueue.push(make_pair(key[v], v)); 
				parent[v] = u; 
			} 
		} 
	} 
	for (int i = 1; i < this -> vertices; ++i) 
		cout << parent[i] << " -- " << i << endl; 
} 
int main() {
  int V = 4, E = 5;
  Graph g(V, E);
  g.addEdge(0, 1, 10);
  g.addEdge(0, 2, 6);
  g.addEdge(0, 3, 5);
  g.addEdge(1, 3, 15);
  g.addEdge(2, 3, 4);
  
  cout << "Minimum Spanning Tree of Graph 1" << endl;
  g.primMST();
  cout << endl <<endl;
  //////////////////
  
  V = 6;
  E = 15;
  Graph g2(V, E);
  g2.addEdge(0, 1, 4);
  g2.addEdge(0, 2, 4);
  g2.addEdge(1, 2, 2);
  g2.addEdge(1, 0, 4);
  g2.addEdge(2, 0, 4);
  g2.addEdge(2, 1, 2);
  g2.addEdge(2, 3, 3);
  g2.addEdge(2, 5, 2);
  g2.addEdge(2, 4, 4);
  g2.addEdge(3, 2, 3);
  g2.addEdge(3, 4, 3);
  g2.addEdge(4, 2, 4);
  g2.addEdge(4, 3, 3);
  g2.addEdge(5, 2, 2);
  g2.addEdge(5, 4, 3);
  
  cout << "Minimum Spanning Tree of Graph 2" << endl;
  g2.primMST();
  return 0;
}

Pseudocode

PrimMST()
 //Initialize Priority Queue with single vertex, chosen arbitrarily from the graph.
 //Grow the Priority Queue by one edge
 //Repeat step 2 (until all vertices are in the tree).
While (Priority Queue !empty)
      Extract the min value node from Priority Queue. 
      Let the extracted vertex be u.
      for every adjacent vertex v of u, 
          check if v is in Priority Queue
          if v is in Priority Queue and its key value is more than weight of u-v, 
             update the value of v as weight of u-v.

Time Complexity

The time complexity of the above code looks like it’s O(V2)O(V^2) ...