All About Kruskal’s Algorithm

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

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?
• Conditions for Kruskal’s Algorithm
• Working
• Example
• Complexity
• Applications

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

Example

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

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

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

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. 

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. 

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. 

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

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

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