Kruskal's Algorithm: Minimum Spanning Tree Algorithm Explained

Last updated by Naina Batra on Aug 30, 2024 at 05:53 PM | Reading time: 8 minutes

What is Kruskal Algorithm?

Kruskal's algorithm is covered in the graph theory of discrete mathematical concepts. It determines the shortest path between two points in a connected weighted graph.

This algorithm transforms a given graph into a tree by treating each node as a separate tree. These trees can only be linked if the edge linking them has a low value and does not form a cycle in the MST structure.

As previously stated, the Kruskal technique is used to create the minimal spanning tree for a given graph.

But what exactly defines a minimal spanning tree? A minimum spanning tree is a subset of a graph that contains the same number of edges as the graph and edges equal to the number of vertices minus one.

It also has a low cost for the total of all edge weights in a spanning tree. Kruskal's algorithm sorts all edges in ascending order of edge weights and adds nodes to the tree only if the selected edge does not form a cycle.

Furthermore, it selects the edge with the lowest cost first and the edge with the highest cost last.

As a result, you can argue that the Kruskal algorithm makes a locally optimal option to get the globally optimal answer. That is why it is known as the Greedy Algorithm.

Know from our experts what a minimum spanning tree is and how to build a minimum spanning tree from a given graph using Kruskal's algorithm.

What is a Minimum Spanning Tree?

A minimal spanning tree (MST) is a subset of edges in a connected, edge-weighted graph that link all vertices without any cycles and with the lowest feasible total edge weight.

It is a method of determining the most cost-effective way to connect a set of vertices. A minimum-spanning tree is not always unique.

All edge weights in the MST must be distinct. If all of the edges in the graph have the same weight, every spanning tree is an MST.

The edges of the minimal spanning tree can be discovered using the algorithm, as well as the more complicated Kruskal or Prim's algorithms.

Working of Kruskal's Algorithm

Kruskal's Algorithm is the recommended method for finding the shortest-spanning tree in a linked weighted graph. The main purpose of this technique is to find a subset of edges that may be used to visit each vertex of the graph.

It employs the greedy technique, which seeks an optimal explanation at each step rather than focusing on a global optimum.

You can watch the video where our instructor is teaching real-world MST problem. It’s easier to comprehend.

Here, we select the edges with the lowest weight and continue counting the edges till we reach our target. To run the Kruskal's algorithm, we must follow the procedures listed below:

First, we will sort all of the edges by weight (low to high).
Now we'll select the edge with the least weight and associate it with the spanning tree. If the edge being added results in a cycle, it should be denied.
Continue adding edges until all vertices are added and a minimum spanning tree is produced.

Kruskal's Algorithm Examples

Example 1: Consider a weighted graph with vertices A, B, C, D, and E, and the following edges with their respective weights:

AB with weight 2
AC with weight 3
AD with weight 1
BC with weight 4
BD with weight 2
BE with weight 3
CD with weight 5
CE with weight 4
DE with weight 6

To apply Kruskal's Algorithm:

Sort all the edges in a non-decreasing order of their weights.
Initialize an empty set to store the minimum spanning tree (MST).
Iterate through each edge in the sorted order:some text
- If adding the edge to the MST does not form a cycle, add it to the MST.
- Otherwise, skip it.
Continue this process until all vertices are connected.

Applying Kruskal's Algorithm:

Sort the edges in non-decreasing order of weights: AD, AB, BD, AC, BE, BC, CE, CD, DE
Begin with an empty MST.
Add the edges in the following order:some text
- AD (weight 1)
- AB (weight 2)
- BD (weight 2)
- AC (weight 3)
- BE (weight 3)
- CE (weight 4)
- BC (weight 4)
- CD (weight 5)
- DE (weight 6)

The resulting minimum spanning tree consists of the edges: AD (weight 1), AB (weight 2), BD (weight 2), AC (weight 3), BE (weight 3), CE (weight 4), and CD (weight 5).

Finally, it constructs the Minimum Spanning Tree (MST) using Kruskal's Algorithm and prints the edges of the MST.

Creating Minimum Spanning Tree Using Kruskal Algorithm

To create a minimum spanning tree (MST) using Kruskal's algorithm, follow these steps:

Sort Edges: Sort all the edges in the graph in a non-decreasing order of their weights.
Initialize MST: Create an empty set to store the minimum spanning tree.
Iterate Over Edges: Iterate through each edge in the sorted order.some text
- If adding the edge to the MST does not create a cycle, add it to the MST.
- Otherwise, skip it.
Repeat: Continue this process until all vertices are connected.

Let's illustrate this process with an example:

Consider the following graph:

4 3

A ------- B ------- C

| \ | |

1| \2 |6 |5

| \ | |

D ------- E ------- F

7 4

Sort Edges:some text
- AD (1), AB (4), AE (2), BC (3), BE (6), EF (5), DE (7)
Initialize MST: Start with an empty set.
Iterate Over Edges:a. Add AD (1) to the MST.b. Add AB (4) to the MST.c. Add AE (2) to the MST.d. Add BC (3) to the MST.e. Add EF (5) to the MST.
Resulting MST:

4 3

A ------- B ------- C

| | |

1| 6| |5

| | |

D ------- E ------- F

7 4

The resulting MST connects all vertices with the minimum total weight.

Implementation of Kruskal's Algorithm

Implementation of Kruskal's Algorithm involves creating a minimum spanning tree (MST) for a given connected, undirected graph. The algorithm efficiently finds the subset of edges that connects all the vertices in the graph while minimizing the total edge weight.

Here's a detailed explanation of how Kruskal's Algorithm is implemented:

Sort Edges: Initially, all the edges in the graph are sorted in a non-decreasing order of their weights. This step ensures that we consider edges with the lowest weights first.
Initialize MST and Disjoint Set: Create an empty set to store the MST. Also, initialize a disjoint set data structure to keep track of disjoint sets of vertices.
Iterate Over Edges: Iterate through each edge in the sorted order. For each edge:some text
- Check if adding the edge to the MST would create a cycle. This is done by checking if the vertices of the edge belong to the same disjoint set.
- If adding the edge does not create a cycle, add it to the MST and merge the disjoint sets of its vertices.
Repeat: Continue this process until all vertices are connected or all edges are considered.
Output MST: The resulting set of edges forms the minimum spanning tree of the graph.

Sort Edges: The edges are sorted based on their weights: AD (1), AB (4), AE (2), BC (3), BE (6), EF (5), DE (7).
Initialize MST and Disjoint Set: We start with an empty MST and initialize disjoint sets for each vertex.
Iterate Over Edges:some text
- Add AD (1) to the MST and merge sets containing vertices A and D.
- Add AB (4) to the MST and merge sets containing vertices A and B.
- Add AE (2) to the MST and merge sets containing vertices A and E.
- Add BC (3) to the MST and merge sets containing vertices B and C.
- Add EF (5) to the MST and merge sets containing vertices E and F.

The resulting MST connects all vertices with the minimum total weight. This implementation efficiently finds the minimum spanning tree of a graph, making it a widely used algorithm in various applications, such as network design and clustering.

Question on the Kruskal algorithm is asked to various tech professionals in the computer science field. In machine learning, it is asked for clustering algorithms and data structures for optimization in large datasets.

FAQ: Kruskal's Algorithm

1. What is Kruskal's Algorithm?
Kruskal's Algorithm is an algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It aims to connect all the vertices of the graph with the minimum total edge weight.

2. How does Kruskal's Algorithm work?
Kruskal's Algorithm works by iteratively selecting edges from the graph in increasing order of their weights and adding them to the MST if they do not create a cycle. It continues this process until all vertices are connected or all edges are considered.

3. When should Kruskal's Algorithm be used?
Kruskal's Algorithm is suitable for finding the MST of a graph when the edges have distinct weights and the graph is sparse (i.e., it has relatively few edges compared to the number of vertices).

4. What is the time complexity of Kruskal's Algorithm?
The time complexity of Kruskal's Algorithm is O(E log E), where E is the number of edges in the graph. This complexity arises mainly from the sorting of edges based on their weights.

5. How does Kruskal's Algorithm handle disconnected graphs?
Kruskal's Algorithm assumes that the input graph is connected. If the graph is disconnected, the algorithm will produce a minimum spanning tree that consists of MSTs for each connected component of the graph.

Related Articles:

AUTHOR

Naina Batra

Manager, Content Marketing

No items found.

Register for our webinar

How to Nail your next Technical Interview

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Hosted By

Ryan Valles

Founder, Interview Kickstart

Our tried & tested strategy for cracking interviews

How FAANG hiring process works

The 4 areas you must prepare for

How you can accelerate your learnings

Register for Webinar

How to Nail your next Technical Interview

Nick Camilleri

Kruskal's Algorithm: Minimum Spanning Tree Algorithm Explained

Contents

Naina Batra

Attend our Free Webinar on How to Nail Your Next Technical Interview

How to Nail your next Technical Interview

Worried About Failing Tech Interviews?

Tools to Enhance Full Stack Development with AI

The Future of Data Science: Emerging Trends and Opportunities

Data-Driven Decision Making: Your Roadmap to Business Success

The Business Impact of Machine Learning: Real-world Case Studies

What is OpenAI? Everything You Need to Know

Mock Interviews for Generative AI: Essential Practice to Land Top AI Roles

Top Python Scripting Interview Questions and Answers You Should Practice

Complex SQL Interview Questions for Interview Preparation

Zoox Software Engineer Interview Questions to Crack Your Tech Interview

Rubrik Interview Questions for Software Engineers

Top Advanced SQL Interview Questions and Answers

Twilio Interview Questions

Ready to
Enroll?

Next webinar starts in

How to Nail your next Technical Interview

You may be missing out on a 66.5% salary hike*

Nick Camilleri

How many years of coding experience do you have?

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

How can we help?

Register for Webinar

Read our Reviews

Send us a note

Kruskal's Algorithm: Minimum Spanning Tree Algorithm Explained

Contents

Naina Batra

Attend our Free Webinar on How to Nail Your Next Technical Interview

How to Nail your next Technical Interview

Worried About Failing Tech Interviews?

Tools to Enhance Full Stack Development with AI

The Future of Data Science: Emerging Trends and Opportunities

Data-Driven Decision Making: Your Roadmap to Business Success

The Business Impact of Machine Learning: Real-world Case Studies

What is OpenAI? Everything You Need to Know

Mock Interviews for Generative AI: Essential Practice to Land Top AI Roles

Top Python Scripting Interview Questions and Answers You Should Practice

Complex SQL Interview Questions for Interview Preparation

Zoox Software Engineer Interview Questions to Crack Your Tech Interview

Rubrik Interview Questions for Software Engineers

Top Advanced SQL Interview Questions and Answers

Twilio Interview Questions

Ready to Enroll?

Next webinar starts in

Ready to
Enroll?