Limited Period Offer : 20% Discount on online/offline courses, for more details call/whatsapp

Prim's Algorithm

1 min read
1 year ago By Aniket Prajapati

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 .

Jul 07, 2023 22:12 Back to Articles

Other Articles

Establishing Validation by Converting TypeScript Code to Zod Schemas Establishing Validation by Converting TypeScript Code to Zod Schemas

In this article, we'll explore how to establish validation by converting TypeScript code to Zod schemas. Zod is a TypeScript-first schema validation library that ensures data validity at runtime.

1 year ago By Mitali Gupta
Introduction to Django

A high-level Python web framework called Django makes it possible for programmers to create web applications rapidly and effectively. It adheres to the Model-View-Controller (MVC) architectural design pattern, placing emphasis on the division of duties and encouraging code reuse. Django offers a comprehensive collection of conventions, frameworks, and tools that speed up development and promote best practises.

React State Management Made Easy: Zustand and Redux Explained React State Management Made Easy: Zustand and Redux Explained

In this article, we will discover two powerful state management libraries for React: Zustand and Redux. Also explore their unique approaches, advantages, and use cases, to simplify and optimize your application's state handling. Choose the best fit for your project's needs and boost development efficiency with these popular solutions.

1 year ago By Mitali Gupta
Real DOM VS Virtual DOM

In this article, we will discuss the differences between the real DOM and the virtual DOM in the context of web development. We'll explore how these concepts impact the performance and efficiency of web applications, and how they contribute to the overall user experience. By the end of this article, you'll have a clear understanding of the distinctions between these two approaches to managing and updating user interfaces on the web.

1 year ago By Mitali Gupta