Prim's Algorithm

Prim's Algorithm is a graph algorithm and this algorithm works as it starts with a single node and then moves through several adjacent nodes form that node , in order to explore all of the connected edges along the way.

Flow to understand:

The prim's algorithm algorithm starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST(Minimum Spanning Tree), and the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST(Minimum spanning Tree).

#include <bits/stdc++.h>
using namespace std;
#define V 5

int minKey(int key[], bool mstSet[])
{
	int min = INT_MAX, min_index;

	for (int v = 0; v < V; v++)
		if (mstSet[v] == false && key[v] < min)
			min = key[v], min_index = v;

	return min_index;
}


void printMST(int parent[], int graph[V][V])
{
	cout<<"Edge \tWeight\n";
	for (int i = 1; i < V; i++)
		cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n";
}


void primMST(int graph[V][V])
{
	int parent[V];
	
	int key[V];
	
	bool mstSet[V];

	for (int i = 0; i < V; i++)
		key[i] = INT_MAX, mstSet[i] = false;


	key[0] = 0;
	parent[0] = -1; // First node is always root of MST

	for (int count = 0; count < V - 1; count++)
	{

		int u = minKey(key, mstSet);

		mstSet[u] = true;


		for (int v = 0; v < V; v++)

			if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
				parent[v] = u, key[v] = graph[u][v];
	}

	printMST(parent, graph);
}

int main()
{
	/* Let us create the following graph
		2 3
	(0)--(1)--(2)
	| / \ |
	6| 8/ \5 |7
	| / \ |
	(3)-------(4)
			9	 */
	int graph[V][V] = { { 0, 2, 0, 6, 0 },
				  { 2, 0, 3, 8, 5 },
				  { 0, 3, 0, 0, 7 },
				  { 6, 8, 0, 0, 9 },
			        { 0, 5, 7, 9, 0 } };

// Print the solution
primMST(graph);

return 0;

}

Time Complexity of the algorithm : O(E * log V) ,where E stands for number of edges and V for number of vertex .

Time Complexity of the algorithm : O(V) , V stands for number of vertices .