All About Kruskal’s Algorithm

All About Kruskal’s Algorithm

4 mins read2.1K Views Comment
Updated on Jul 6, 2023 17:29 IST

Kruskal’s algorithm is based on a greedy approach, whose goal is to find the shortest path in a graph with a minimum cost.

2022_10_2-1.jpg

Kruskal’s algorithm is used to find the shortest way between two connected weighted nodes, it divides a graph into a forest and considers each node as an individual tree. Kruskal’s algorithm connects each tree or node in such a way that the connecting edge has the minimum value and no cycle is created in the resulting minimum spanning tree. In this article, we are going to discuss what is Kruskal’s algorithm, the working of Kruskal’s algorithm along with examples, complexity, and implementation. 

Table of Contents

What is Kruskal’s Algorithm?

Kruskal’s algorithm is a greedy algorithm used to find out the shortest path in a minimum spanning tree. The algorithm aims to traverse the graph and detect the subset of edges with minimal value and cover all the vertices of the graph. At every step of the algorithm and analysis, it follows a greedy approach for an overall optimized result. 

Kruskal’s algorithm can be summed up as it is a minimum spanning tree algorithm that takes a graph as input and forms a subset of the edges of the graph, 

  • which has a minimum sum of edge weight among all the trees that can be formed from that graph. 
  • that form a tree including each vertex of the graph, without forming any cycle between the vertex. 

Explore Free Online Courses with Certificates

Necessary conditions for Kruskal’s algorithm

It works on the graph. So, 

  • The graph must be undirected.
  • The graph must be weighted.
  • The graph must be connected. 

Working

Kruskal’s algorithm follows a greedy approach that always tries to find a local optimum result and hopes to obtain a global optimum result. 

Being a greedy algorithm, Kruskal’s algorithm begins with selecting the edge with minimum weight and keeps adding edges until all the vertices aren’t covered. 

Step-wise working of Kruskal’s algorithm is as follows:

  1. Keep all the edges sorted and in ascending order or sort all the edges in increasing weight order.
  2. Select the edge with the smallest or minimum edge weight.
  3. Add the selected edge to the spanning tree.
  4. Check whether the added edge is creating a cycle or loop. If yes, then reject that edge. 
  5. Repeat until all the vertices are added to the graph.

Explore free data structure and algorithms courses

Know more about Data Structure and Algorithms

Must Check: Data Structure and Algorithms Online Courses and Certificates

Psuedo code:

Pseudo code for the kruskal’s algorithm is as follows:

Kruskal(Edges, V, E):

    a=0, i=0

    sum=0

    Sort(Edges)

    while(a<V-1):

        u=Edges[i].u

        v=Edges[i].v

        if(Adding edge {u, v} do not form cycle):

            Print(Adding edge {u, v} to MST)

            sum+=Edges[i].weight

            a+=1

        i+=1

Data Structures and Algorithms in Python – All You Need to Know
Data Structures and Algorithms in Python – All You Need to Know
Python is a high-level, object-oriented programming language. It is a general-purpose language that is used in a variety of applications such as software testing, web development, data science, machine learning,...read more
An Introduction to Genetic Algorithms
An Introduction to Genetic Algorithms
Genetic Algorithms are search algorithms that are based on Darwin’s Theory of Evolution. This algorithm is an artificial intelligence technique inspired by the idea that the one that survives is...read more
Top Data Mining Algorithms You Should Learn in 2024
Top Data Mining Algorithms You Should Learn in 2024
Data mining is a technique that allows us to obtain patterns or models from the collected data. It aims to extract meaningful information from huge chunks of datasets using data...read more

Example

Consider the following graph and draw the MST using Kruskal’s algorithm.

2022_10_MST-using-kruskals-algorithm-1.jpg

Solution:

Edges in increasing order are:

B-D: 1

D-C: 2

B-A: 3

A-E: 4

A-C: 6

E-F: 6

D-F:8

B-F: 10

Selecting the edge with minimum weight, i.e. B – D

2022_10_image-65.jpg

Now, we will select another edge with the next minimum weight, so edge D-C is selected. 

2022_10_Edge-D-C-in-Kruskals-algorithm-1.jpg

No cycle or self-loop is formed, so we can proceed further. Now, select another edge with the next minimum weight. So, edges B- A will be selected. 

2022_10_Edge-B-A-in-Kruskals-algorithm.jpg

No cycle or self-loop is formed, so we can proceed further. Now, select another edge with the next minimum weight. So, edges A-E will be selected. 

2022_10_image-68.jpg

No cycle or self-loop is formed, so we can proceed further. Now, select another edge with the next minimum weight. So, edges A-C will be selected. 

2022_10_image-70.jpg

This selected edge formed a cycle, so we have to reject it and proceed further. After rejecting, the above edge the graph will be

2022_10_image-71.jpg

Now, select the next edge, i.e. E-F.

2022_10_image-72.jpg

All the edges of the graph are included in the MST and adding any other edge will be worthless or create a loop in the MST. So, the above tree is the final tree. 

The total cost of Tree traversal or cost of the shortest path using Kruskal’s algorithm is:

         =  2+1+3+4+6

         =  16

Complexity

Time complexity: O(E log E). 

Explanation: Sorting all the edges requires O(E log E) time and after the sorting, the algorithm iterates through all edges, and the union function takes O(log V) time. 

Overall complexity= O (E log E + E log V) 

The at-most value of E can be O (V^2), so we can say O(log V) and O (log E) aresame. 

Therefore, the time complexity is  O(E log E).

Space Complexity: O(E)

Applications

This algorithm is used in:

  • electrical wiring layout
  • In the layout of the LAN’s connection

Key Takeaways:

  • The edges in Kruskal’s algorithm are maintained as min-heap.
  • If the edges are already sorted, no need to create a min-heap. In this case, the time complexity would be O (E+V).

Author: Kanika Joshi

FAQs

What are the applications of Kruskal's algorithm?

Kruskal's algorithm has several applications, including: Designing efficient network connections or cable layout planning. Constructing efficient road networks or transportation systems. Cluster analysis or data grouping. Approximate solutions to the traveling salesman problem.

Are there any limitations to Kruskal's algorithm?

Kruskal's algorithm assumes an undirected, connected graph with non-negative edge weights. It does not handle graphs with negative weights or disconnected graphs. For graphs with negative weights, other algorithms like Prim's algorithm or Dijkstra's algorithm can be more suitable.

How does Kruskal's algorithm work?

Initially, each vertex in the graph is considered as a separate component. Edges of the graph are sorted in non-decreasing order of their weights. Starting with the lowest weight edge, Kruskal's algorithm checks if adding the edge to the current MST creates a cycle. If the edge does not create a cycle, it is added to the MST. Otherwise, it is discarded. The process continues until all vertices are included in the MST or all edges have been considered.

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio