Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
What is a Spanning Tree?
1.2.
What is Minimum Spanning Tree?
2.
Algorithm
2.1.
Prim’s Algorithm
3.
Code
3.1.
C++
3.2.
Python3
3.3.
Output
4.
Complexity
5.
Frequently Asked Questions
5.1.
What are a tree and a spanning tree?
5.2.
What are the properties of a spanning tree?
5.3.
Why Prim's algorithm is greedy?
5.4.
Why is Prims better than Kruskal?
5.5.
Which is faster Prim or Kruskal?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Prim’s Minimum Spanning Tree

Author soham Medewar
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Prim's algorithm is a Greedy algorithm. Prim's algorithm always begins with a single node and progresses through numerous nearby nodes to study all linked edges along the route. To understand where Prim's algorithm is useful, we must know what the spanning tree and minimum spanning tree are.

What is a Spanning Tree?

Suppose you are given a connected and undirected graph G where graph G has V vertices and E edges. A tree that spans all the vertices of graph G is called the spanning tree. In contrast, the spanning tree is a subgraph of graph G.

What is Minimum Spanning Tree?

The weights of all the edges in the tree are added to determine the cost of the spanning tree. Many spanning trees may exist. The spanning tree with the lowest cost among all other spanning trees is known as a minimum spanning tree. There may be a lot of minimum spanning trees as well.

Let us understand this with an example.

Graph

Algorithm

To find the minimum spanning tree of the undirected graph, we can use two algorithms, i.e., Kruskal's and Prim’s algorithms. In this article, we will be learning about Prim’s algorithm.

Prim’s Algorithm

The Greedy technique is used by Prim's Algorithm to discover the minimum spanning tree. In Prim's Algorithm, the spanning tree is grown from scratch. We add a vertex to the expanding spanning tree in Prim's method rather than an edge in Kruskal's.

Steps of the algorithm

  • Keep two separate sets of vertices. One of them has vertices in the expanding spanning tree, and the other does not have any such vertices.
     
  • Choose the least expensive vertex that is connected to the developing spanning tree but isn't already present in the growing spanning tree, and include it there. Priority Queues can be used to accomplish this. Add the developing spanning tree's connected vertices to the Priority Queue.
     
  • Examine for cycles. To accomplish this, mark the nodes that have already been chosen and only add the unmarked nodes to the Priority Queue.
     

Following are the steps (working of Prim’s algorithm):

Steps
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Code

C++

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

// Defining number of vertices
#define V 5

/* a utility function that searches the set of vertices not yet included in MST for the vertex with the lowest key value. */
int minKey(int key[], bool mstSet[])
{
	// Initializing the min value
	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;
}

/* A useful function to print the built-in MST contained in parent[] */
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";
}

/* For a graph represented using adjacency matrix representation, there is a function to construct and print MST. */
void primMST(int graph[V][V])
{
	// array that stores MST
	int parent[V];

	// Key factors utilised to select the cut's minimal weight
	int key[V];

	// to display a collection of vertices used in MST
	bool mstSet[V];

	// Set all keys to INFINITE at start.
	for (int i = 0; i < V; i++)
		key[i] = INT_MAX, mstSet[i] = false;

/* Include the initial vertex in MST at all times. To ensure that this vertex is chosen as the initial vertex, set key to 0. */
	key[0] = 0;
	parent[0] = -1; // In MST first node is always root

	// The MST of V vertices
	for (int count = 0; count < V - 1; count++) {
        /* Choose the minimum key vertex from the collection of vertices that aren't yet part of MST. */
		int u = minKey(key, mstSet);

	// adding picked vertex to MST
	mstSet[u] = true;

/* Update the neighbouring vertices' parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST */
	for (int v = 0; v < V; v++)
/* Only the nearby vertices of m mst make graph[u][v] non zero. For vertices not yet included in MST, Set[v] is false. Only change the key if graph[u][v] is less than key[v]. */
		if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
			parent[v] = u, key[v] = graph[u][v];
	}

// printing the MST
	printMST(parent, graph);
}

// main code
int main()
{
	int graph[V][V] = { { 0, 1, 0, 0, 3 },
	{ 1, 0, 7, 0, 2 },
	{ 0, 7, 0, 2, 10 },
	{ 0, 0, 2, 0, 5 },
	{ 3, 2, 10, 5, 0 } };

	// printing the solution
	primMST(graph);
	return 0;
}

Python3

import sys 
class Graph():

def __init__(self, vertices):
	self.V = vertices
	self.graph = [[0 for column in range(vertices)]
		for row in range(vertices)]

    # A useful function to print the built-in MST contained in parent[]
def printMST(self, parent):
	print("Edge \tWeight")
	for i in range(1, self.V):
		print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

""" A useful function that searches the set of vertices not yet included in the shortest path tree for the vertex with the lowest distance value. """
def minKey(self, key, mstSet):

	# Initializing the min value
	min = sys.maxsize

	for v in range(self.V):
		if key[v] < min and mstSet[v] == False:
			min = key[v]
			min_index = v

	return min_index

def primMST(self):

	key = [sys.maxsize] * self.V
	parent = [None] * self.V # array for storing MST

	key[0] = 0
	mstSet = [False] * self.V

	parent[0] = -1 # First node is always the root of MST

	for cout in range(self.V):

		"""Choose the minimum key vertex from the collection of vertices that aren't yet part of MST."""
		u = self.minKey(key, mstSet)

	# adding picked vertex to MST
	mstSet[u] = True

	""" Update the neighbouring vertices' parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST"""
	for v in range(self.V):

		if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
			key[v] = self.graph[u][v]
			parent[v] = u

	self.printMST(parent)


# Driver's code
if __name__ == '__main__':
	g = Graph(5)
	g.graph = [[ 0, 1, 0, 0, 3 ], 
              	[ 1, 0, 7, 0, 2 ], 
              	[ 0, 7, 0, 2, 10 ], 
              	[ 0, 0, 2, 0, 5 ], 
              	[ 3, 2, 10, 5, 0 ] ]
	g.primMST()

Output

Edge  Weight
0 - 1   1 
3 - 2   2 
4 - 3   5 
1 - 4   2 

Complexity

Time Complexity O(V2): The time complexity of Prim's algorithm can be decreased to O(E log V) with the use of a binary heap if the input graph is represented using an adjacency list. In this implementation, the spanning tree is always believed to begin at the graph's root.

Space Complexity: O(V)
Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What are a tree and a spanning tree?

One sort of graph is a tree. A subgraph of the graph that is a tree and spans every vertex is called a spanning tree.

What are the properties of a spanning tree?

There is exactly the same number of edges and vertices in each of a graph's potential spanning trees. A cycle can never be found inside a spanning tree. If we remove one edge from the spanning tree, it will become unconnected since spanning trees are always minimally linked.

Why Prim's algorithm is greedy?

Input is rearranged by Prim's Algorithm in order to select the least expensive edge. In the sense that the algorithm strives to readjust the input to its own convenience at each iteration, we refer to Prim's Algorithm as an adaptive greedy algorithm.

Why is Prims better than Kruskal?

Prim's algorithm has an advantage over Kruskal's in that it is more complex. Prim's approach is therefore useful for handling dense networks with a large number of edges. However, when numerous edges with the same weight occur, Prim's approach doesn't provide us much control over the selected edges.

Which is faster Prim or Kruskal?

The Prim algorithm returns connected components and solely utilizes connected graphs. In dense graphs, Prim's method operates more quickly. In sparse graphs, Kruskal's algorithm operates more quickly.

Conclusion

In the above article, we have discussed the following topics:

  • Spanning Tree
     
  • Finding spanning tree using Prim’s algorithm
     
  • Example of Prim’s algorithm
     
  • Implementation of Prim’s algorithm
     

If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder TraversalRegular and Bipartite graphs, and Planar and Non-Planar Graphs.

Happy Coding!

Previous article
Prim’s Algorithm in Java
Next article
Minimum Product Spanning Tree
Live masterclass