Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconArtificial Intelligencebreadcumb forward arrow iconWhat is Kruskal’s Algorithm? Steps, Examples, Overview

What is Kruskal’s Algorithm? Steps, Examples, Overview

Last updated:
27th May, 2023
Views
Read Time
9 Mins
share image icon
In this article
Chevron in toc
View All
What is Kruskal’s Algorithm? Steps, Examples, Overview

Introduction to Kruskal Algorithm

Kruskal’s Algorithm is a popular algorithm used in graph theory to find the Minimum Spanning Tree (MST) of a weighted graph. The MST represents the subset of edges that form the most efficient way to connect all the vertices while minimizing the total weight. By employing Kruskal’s Algorithm, we can solve complex optimization problems in various domains, such as network design, transportation planning, and circuit layout. This algorithm follows a step-by-step approach, carefully selecting edges based on their weights to construct the MST. To learn more about these algorithms, you can check out the MS in Full Stack AI and ML program by upGrad.

How does Kruskal’s Algorithm work?

Kruskal’s Algorithm follows a simple and intuitive approach to finding the MST of a connected weighted graph. Let’s explore the steps and process involved:

  • Sort the Edges: The first step in Kruskal’s Algorithm is to sort all the edges in the graph in the non-decreasing order of their weights. This step ensures that we consider edges with lower weights first.
  • Initialize an Empty MST: Create an empty set to represent the MST.
  • Iterate through the Edges: Starting from the edge with the lowest weight, iterate through the sorted edges.
  • Check for Cycle: For each edge, check if including it in the MST would create a cycle. A cycle is formed when adding an edge connects two vertices that are already connected through a different path.
  • Add to the MST: If including the current edge does not create a cycle, add it to the MST set.
  • Repeat Until MST is Complete: Continue steps 4 and 5 until there are V-1 edges in the MST, where V is the number of vertices in the graph. The MST will always have V-1 edges, ensuring that all vertices are connected without forming cycles.

By following these steps, Kruskal’s Algorithm effectively constructs the Minimum Spanning Tree, connecting all the vertices with the least total weight.

Learn Machine learning courses from the world’s top universities.

Ads of upGrad blog

Example of Kruskal’s Algorithm

Let’s consider a graph with five vertices: A, B, C, D, and E. The edges and their corresponding weights are as follows:

AB: 3

AC: 1

BC: 4

BD: 2

CD: 5

CE: 6

By applying Kruskal’s Algorithm to this graph, we can find the Minimum Spanning Tree. Here’s a step-by-step breakdown of the process:

  • Sort the edges in non-decreasing order of their weights: AC, BD, AB, BC, CD, CE.
  • Initialize an empty MST.
  • Take the edge AC with weight 1 and add it to the MST.
  • Move to the next edge, BD with weight 2, and add it to the MST.
  • Proceed to edge AB with weight 3 and include it in the MST.
  • Add the edge BC with weight 4 to the MST.
  • Skip the edge CD as it creates a cycle in the current MST.
  • Finally, include the edge CE with weight 6 to the MST.
  • The resulting Minimum Spanning Tree for this graph includes the edges AC, BD, AB, and BC.

What is a Spanning Tree?

A spanning tree of a graph is a subgraph that includes all the vertices of the original graph but contains only a subset of the edges. It is a connected and acyclic graph, which means there are no cycles in the spanning tree. In other words, it is a tree that spans all the vertices of the graph, providing a way to reach any vertex from any other vertex.

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) is a spanning tree of a graph that has the minimum possible total weight among all the spanning trees. It represents the subset of edges that form the most efficient and cost-effective way to connect all the vertices in the graph. The primary objective of finding an MST is to minimize the overall cost or weight while ensuring that all vertices are connected.

How many edges does a Minimum Spanning Tree have?

A Minimum Spanning Tree (MST) of a graph with V vertices always has V-1 edges. This property holds for any connected graph. The MST includes the optimal subset of edges that connects all the vertices while minimizing the total weight.

Creating Minimum Spanning Tree using Kruskal’s Algorithm

Explanation of the process of creating an MST using Kruskal’s Algorithm

To create a Minimum Spanning Tree (MST) using Kruskal’s Algorithm, follow these steps:

  1. Sort the Edges: Start by sorting all the edges of the graph in the non-decreasing order of their weights. This ensures that we consider edges with lower weights first.
  2. Initialize the MST: Create an empty set to represent the MST.
  3. Iterate through the Edges: Begin iterating through the sorted edges.
  4. Check for Cycle: For each edge, check if including it in the MST would create a cycle. This can be done using the Union-Find algorithm, which efficiently detects cycles and maintains the connectivity of the graph.
  5. Add to the MST: If including the current edge does not create a cycle, add it to the MST set.
  6. Repeat Until MST is Complete: Continue steps 4 and 5 until there are V-1 edges in the MST, where V is the number of vertices in the graph. The MST will have V-1 edges since a spanning tree includes all vertices without forming cycles.

By following these steps, Kruskal’s Algorithm constructs the Minimum Spanning Tree of the given graph. It selects edges with the lowest weights that do not form cycles, ensuring that the resulting MST is the most cost-effective way to connect all the vertices. In order to get a hand over these algorithms, you can choose the Advanced Certificate Programme in Machine Learning & NLP from IIITB. 

Union Find Algorithm

The Union Find Algorithm, also known as the Disjoint Set Data Structure, is an efficient way to keep track of elements that are partitioned into disjoint sets. It provides operations to determine which set an element belongs to and to merge two sets. In the context of Kruskal’s Algorithm, the Union Find algorithm is used to detect cycles when adding edges to the MST. It helps maintain the connectivity of the graph and ensures that no cycles are formed in the MST construction process.

Implementation of Kruskal’s Algorithm

A detailed explanation of how to implement Kruskal’s Algorithm

To implement Kruskal’s Algorithm, you can follow the steps outlined earlier. Here’s a detailed explanation of the implementation process:

  1. Sort the Edges: Begin by sorting all the edges of the graph in the non-decreasing order of their weights.
  2. Initialize the MST and Union Find Data Structure: Create an empty set to represent the MST and initialize the Union Find data structure with each vertex as a separate set.
  3. Iterate through the Edges: Start iterating through the sorted edges.
  4. Check for Cycle: For each edge, check if including it in the MST would create a cycle. This can be done by checking if the endpoints of the edge belong to the same set in the Union Find data structure. If they do not belong to the same set, including the edge does not create a cycle.
  5. Add to the MST and Union Find Data Structure: If including the current edge does not create a cycle, add it to the MST set and merge the sets of its endpoints in the Union Find data structure.
  6. Repeat Until MST is Complete: Continue steps 4 and 5 until there are V-1 edges in the MST, where V is the number of vertices in the graph.

By implementing these steps, you can effectively construct the Minimum Spanning Tree using Kruskal’s Algorithm. The Union Find data structure plays a crucial role in detecting cycles and maintaining the connectivity of the graph throughout the process.

Best Machine Learning and AI Courses Online

Kruskal’s Algorithm vs Prim’s Algorithm

Kruskal’s Algorithm and Prim’s Algorithm are both widely used for finding the Minimum Spanning Tree (MST) of a graph. However, they differ in their approach:

Kruskal’s Algorithm

  • Kruskal’s Algorithm follows a greedy approach.
  • It starts by sorting all the edges of the graph in non-decreasing order of weights.
  • It iteratively selects the edges with the smallest weights and adds them to the MST, as long as they do not create a cycle.
  • Kruskal’s Algorithm does not necessarily start from a specific vertex.
Ads of upGrad blog

Prim’s Algorithm

  • Prim’s Algorithm also follows a greedy approach.
  • It starts by selecting an arbitrary vertex as the starting point.
  • It iteratively adds the shortest edge that connects the MST to a new vertex, until all vertices are included.
  • Prim’s Algorithm always starts from a specific vertex.

The choice between Kruskal’s Algorithm and Prim’s Algorithm depends on the specific requirements and characteristics of the graph. Kruskal’s Algorithm is typically preferred when the graph is dense, while Prim’s Algorithm is more efficient for sparse graphs.

Applications of Kruskal’s Algorithm

Kruskal’s Algorithm has several applications in various domains. Here are three common examples:

  1. Network Design: Kruskal’s Algorithm can be used to design cost-effective networks, such as telephone or internet networks, by connecting cities or routers with the minimum cost of laying cables or establishing connections.
  2. Circuit Design: In electronic circuit design, Kruskal’s Algorithm can be used to determine the minimum cost of connecting components or nodes in a circuit, minimizing the overall wiring or connection cost.
  3. DNA Sequencing: Kruskal’s Algorithm can be applied to determine the evolutionary relationships between different species based on their DNA sequences. Constructing a minimum cost-spanning tree helps identify common ancestors and genetic similarities.

In-demand Machine Learning Skills

Conclusion

In conclusion, Kruskal’s Algorithm is a popular and efficient algorithm for finding the Minimum Spanning Tree of a graph. By iteratively selecting edges with the smallest weights, it constructs a tree that connects all vertices with the minimum total weight. The algorithm works by avoiding cycles and is commonly used in network design, circuit design, and DNA sequencing applications. Kruskal’s Algorithm can be implemented in various programming languages like Python, Java, and C/C, and its time complexity is primarily determined by the sorting step and the Union-Find operations. Understanding Kruskal’s Algorithm and its applications provides valuable insights into graph theory and optimization problems. Learn more about these complex algorithms via Advanced Certificate Programme in Machine Learning & Deep Learning from IITB which may aid you to become a professional Machine Learning Engineer.

Profile

Rohan Vats

Blog Author
Software Engineering Manager @ upGrad. Passionate about building large scale web apps with delightful experiences. In pursuit of transforming engineers into leaders.
Get Free Consultation

Select Coursecaret down icon
Selectcaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Machine Learning Course

Frequently Asked Questions (FAQs)

1What is the difference between Kruskal's Algorithm and Prim's Algorithm?

Kruskal's Algorithm follows a greedy approach and starts by sorting all the edges, while Prim's Algorithm starts from a specific vertex and adds the shortest edges iteratively.

2What is a Minimum Spanning Tree?

A Minimum Spanning Tree is a tree that connects all vertices of a graph with the minimum total weight.

3How does Kruskal's Algorithm avoid cycles?

Kruskal's Algorithm uses the Union-Find algorithm to determine if adding an edge creates a cycle. It maintains a disjoint set data structure to track the connected components of the graph.

4Can Kruskal's Algorithm handle disconnected graphs?

Yes, Kruskal's Algorithm can handle disconnected graphs. It will construct a minimum-spanning forest, which is a collection of Minimum Spanning Trees for each connected component.

5Is Kruskal's Algorithm efficient for large graphs?

Kruskal's Algorithm has a time complexity of O(E log E) and is generally efficient for large graphs. However, the choice of algorithm depends on the characteristics of the graph and specific requirements.

Explore Free Courses

Suggested Blogs

Top 9 Python Libraries for Machine Learning in 2024
74544
Machine learning is the most algorithm-intense field in computer science. Gone are those days when people had to code all algorithms for machine learn
Read More

by upGrad

19 Feb 2024

Top 15 IoT Interview Questions & Answers 2024 – For Beginners & Experienced
63922
These days, the minute you indulge in any technology-oriented discussion, interview questions on cloud computing come up in some form or the other. Th
Read More

by Kechit Goyal

19 Feb 2024

Data Preprocessing in Machine Learning: 7 Easy Steps To Follow
147536
Summary: In this article, you will learn about data preprocessing in Machine Learning: 7 easy steps to follow. Acquire the dataset Import all the cr
Read More

by Kechit Goyal

18 Feb 2024

Artificial Intelligence Salary in India [For Beginners & Experienced] in 2024
906574
Artificial Intelligence (AI) has been one of the hottest buzzwords in the tech sphere for quite some time now. As Data Science is advancing, both AI a
Read More

by upGrad

18 Feb 2024

24 Exciting IoT Project Ideas & Topics For Beginners 2024 [Latest]
744597
Summary: In this article, you will learn the 24 Exciting IoT Project Ideas & Topics. Take a glimpse at the project ideas listed below. Smart Agr
Read More

by Kechit Goyal

18 Feb 2024

Natural Language Processing (NLP) Projects & Topics For Beginners [2023]
105487
What are Natural Language Processing Projects? NLP project ideas advanced encompass various applications and research areas that leverage computation
Read More

by Pavan Vadapalli

17 Feb 2024

45+ Interesting Machine Learning Project Ideas For Beginners [2024]
323831
Summary: In this Article, you will learn Stock Prices Predictor Sports Predictor Develop A Sentiment Analyzer Enhance Healthcare Prepare ML Algorith
Read More

by Jaideep Khare

16 Feb 2024

AWS Salary in India in 2023 [For Freshers & Experienced]
903632
Summary: In this article, you will learn about AWS Salary in India For Freshers & Experienced. AWS Salary in India INR 6,07,000 per annum AW
Read More

by Pavan Vadapalli

15 Feb 2024

Top 8 Exciting AWS Projects & Ideas For Beginners [2023]
95727
AWS Projects & Topics Looking for AWS project ideas? Then you’ve come to the right place because, in this article, we’ve shared multiple AWS proj
Read More

by Pavan Vadapalli

13 Feb 2024

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon