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?
2.
What is the Minimum Spanning Tree?
3.
Algorithm
4.
Kruskal’s Algorithm
4.1.
Algorithm
5.
What To Do?
6.
Implementation
6.1.
C++
6.2.
Python
7.
Complexity
7.1.
Time Complexity
7.2.
Space Complexity
8.
Frequently Asked Questions
8.1.
What are a tree and a spanning tree?
8.2.
What are the properties of a spanning tree?
8.3.
Which is faster Prim or Kruskal?
8.4.
Why does Kruskal's algorithm work?
8.5.
Why is the Kruskal algorithm called greedy?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Kruskal’s Minimum Spanning Tree

Author Mayank Goyal
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Kruskal’s algorithm is used to find the minimum spanning tree. Kruskal's Algorithm creates the spanning tree by gradually adding edges to an expanding spanning tree. Let’s first understand the meaning of a spanning tree and a minimum spanning tree.

What is a Spanning Tree?

Suppose you are given a connected and undirected graph G where graph G has V vertices and E edges. The tree which spans all the vertices of graph G is called the spanning tree. In contrast, the spanning tree is a subgraph of graph G. Given that a graph doesn't involve cycles, it is referred to as a tree. A tree is similar to a graph with N nodes and N-1 edges.

What is the 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.

MST
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

Algorithm

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

Kruskal’s Algorithm

Kruskal's Algorithm creates the spanning tree by gradually adding edges to an expanding spanning tree. The greedy strategy used by Kruskal's algorithm is to find the edge with the least weight in each iteration and add it to the expanding spanning tree.

Algorithm

Sort the graph edges according to their relative weights.

So after sorting, our adjacency list will look something like this(the above example is taken):

Weight Initial node Final node
1 1 2
2 2 5
2 3 4
3 1 5
5 5 4
7 2 3
10 3 5

From the edge with the smallest weight up until the edge with the heaviest weight is added to the MST.

example

Add only edges that don't form cycles or connect only detached parts.

What To Do?

How can I determine whether vertices are connected or not, then?

DFS Algorithm, which starts at the first vertex and determines if the second vertex is visited or not, might be used to do this. However, because DFS has an order of where is the number of vertices and the number of edges, it will have a high time complexity. So "Disjoint Sets" is the ideal solution.

Disjoint Sets have no elements in common because their intersection is the empty set.

Implementation

C++

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


// DSU data structure
// path compression + rank by union


class DSU {
     int* parent;
	int* rank;


public:
DSU(int n)
{
 	parent = new int[n];
	rank = new int[n];


	for (int i = 0; i < n; i++) 
	{
		parent[i] = -1;
		rank[i] = 1;
	}
}

int find(int i)
{
	if (parent[i] == -1)
		return i;

	return parent[i] = find(parent[i]);
}


// Union function
void unite(int x, int y)
{
	int s1 = find(x);
	int s2 = find(y);


	if (s1 != s2)
	{
	 if (rank[s1] < rank[s2]) 
	  {
		parent[s1] = s2;
		rank[s2] += rank[s1];
       }
	else 
	  {
		parent[s2] = s1;
		rank[s1] += rank[s2];
       }
  }
 }
};


class Graph {
vector<vector<int> > adjlist;
int V;


public:
Graph(int V)
      { this->V = V; }


void addEdge(int x, int y, int w)
 {
	adjlist.push_back({ w, x, y });
 }


void kruskals()
{
 sort(adjlist.begin(), adjlist.end());


// Initialize the DSU
DSU s(V);
int ans = 0;
  cout << "Following are the edges in the constructed MST"<< endl;
	for (auto x : adjlist) {
		int w = x[0];
		int x = x[1];
		int y = x[2];


	// We will take this edge in MST if it does
	// not form a cycle
	if (s.find(x) != s.find(y)) {
		s.unite(x, y);
		ans += w;
		cout << x << "->" << y << " == " << w<< endl;
     }
}

cout << "Minimum Cost Spanning Tree: " << ans;
}
};



int main()
{
	Graph g(4);
	g.addEdge(0, 1, 10);
	g.addEdge(1, 3, 15);
	g.addEdge(2, 3, 4);
	g.addEdge(2, 0, 6);
	g.addEdge(0, 3, 5);


	// Function call
	g.kruskals();
	return 0;
}

Python

from collections import defaultdict


class Graph:


def __init__(self, vertices):
	self.V = vertices
	self.graph = [] 


# function to add an edge to the graph
def addEdges(self, u, v, w):
	self.graph.append([u, v, w])


# A utility function to find set of an element i.
def find(self, parent, i):
	if parent[i] == i:
	return i
return self.find(parent, parent[i])


# A function that does the union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):
	xroot = self.find(parent, x)
	yroot = self.find(parent, y)


# Attach a smaller rank tree under the root of
# high-rank tree (Union by Rank)
if rank[xroot] < rank[yroot]:
	parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
	parent[yroot] = xroot


# If ranks are the same, then make one as a root
# and increment it's rank by one
else:
	parent[yroot] = xroot
	rank[xroot] += 1



def KruskalMST(self):
	result = [] # This will store the resultant MST


	# An index variable used for sorted edges
	i = 0


	# An index variable used for result[]
	e = 0


	self.graph = sorted(self.graph,
	key=lambda item: item[2])


	parent = []
	rank = []


	# Create V subsets with single elements
	for x in range(self.V):
	parent.append(x)
	rank.append(0)


	# Number of edges to be taken is equal to V-1
	while e < self.V - 1:
		u, v, w = self.graph[i]
		i = i + 1
		x = self.find(parent, u)
		y = self.find(parent, v)


	/*Include this edge in the result and raise the result's index for the following 
  	edge if including it doesn't result in a cycle.*/
	if x != y:
	  e = e + 1
	  result.append([u, v, w])
	  self.union(parent, rank, x, y)
	# Else, discard the edge


	mincost = 0
	print("Edges in the constructed MST")
	for u, v, wt in result:
	mincost += wt
	print("%d -- %d == %d" % (u, v, wt))
	print("Minimum Spanning Tree is:", mincost)



# Driver's code
if __name__ == '__main__':
	g = Graph(4)
	g.addEdges(0, 1, 10)
	g.addEdges(0, 2, 6)
	g.addEdges(0, 3, 5)
	g.addEdges(1, 3, 15)
	g.addEdges(2, 3, 4)


	# Function call
	g.KruskalMST()

Complexity

Time Complexity

In Kruskal’s algorithm, the most time-consuming operation is sorting because the total complexity of the Disjoint-Set operations will be O(E log V), which is the overall Time Complexity of the algorithm.

Space Complexity

In Kruskal's algorithm, we store the parent and rank of each node in an array. So the space complexity reduces to O(N).
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 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.

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.

Why does Kruskal's algorithm work?

The Kruskal algorithm is greedy in graph theory since it adds increasing cost arcs at each step while it searches for the least spanning tree for a linked weighted network. The overall weight of all the edges in the tree is reduced, and as a result, it discovers a subset of the edges that creates a tree with every vertex.

Why is the Kruskal algorithm called greedy?

It is a greedy method since you decided to union two sets of vertices at each stage based on the smallest weight available. You also decided to utilize the edge that appeared to be the best option at the time. The algorithm is said to be greedy since this phase is greedy.

Conclusion

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

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

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

Well, you can brush up your knowledge by practising the question here.

Happy Coding!

Previous article
Kruskal's Algorithm
Next article
Prim’s Algorithm in Java
Live masterclass