Kruskal’s Algorithm

4 min readApr 6, 2022

INTRODUCTION

Algorithms. Oxford dictionary describes algorithms as a process or a set of rules to be followed in calculations or other problem-solving operations. Algorithms are a very essential part of our lives, there is a definite algorithm of each and every task we could possibly think of! Having a set of instructions to follow only makes the task more organized and easy. Talking about the world of Design Analysis and Algorithms or “DAA” as we call it, one of the many problem solving algorithms is Kruskal’s .

Kruskal’s Algorithm

In 1956, Joseph Kruskal (completed his Phd at Princeton University) invented Kruskal’s algorithm to help finding minimum spanning tree of an edge-weighted graph i.e if the graph is connected , it finds the minimum spanning tree.

A minimum spanning tree is basically a subset of graph with equal number of vertices as the graph and edges equal to vertices -1 (V-1), which also lead to minimal cost for sum of all edge weights . Kruskal’s algorithm sorts all the edges in increasing order and will continue to add nodes if the selected edges do not form any cycle. This algorithm picks the node with minimum cost first and node with the maximum cost at last.

Let’s understand this algorithm more thoroughly through an example!

Here you can see the graph, this graph contains 9 vertices and 14 edges:

Since the graph contains 9 vertices and 14 edges, the minimum spanning tree here should contain 9–1 (V-1) = 8 edges.

Firstly, we need to sort the edges in increasing order.

Now we will select all the edges one by one from the sorted list.

Here, we will choose 7–6 edge. (Important Note: remember, the chosen edges should not form a cycle while constructing the MST)

Now, let’s pick edge 8–2:

Next we’ll go for edge 6–5:

Now, for edge 0–1

Next, edge 2–5

Now, when we choose edge 8–6, you can see that there will be a cycle formed, which is not suppose to happen in Kruskal’s algorithm while forming the MST.

So, we will switch to next minimum edge out of the lot, i.e edge 2–3, since no cycles will be formed by including these:

Similarly, we’ll go for edges 0–7 & 3–4 , since we noticed while picking edge 7–8 & 1–2 , our MST in the making forms a cycle which is not the rule , so we’d have to discard them . After picking our last edge which is 3–4, we will notice that the number of edges formed will be 8. So, now the final MST (as of now since the number of edges is equal to V-1, we’ll stop the algorithm here.)will look like this:

TIME COMPLEXITY:

KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
    MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
    if FIND-SET(u) ≠ FIND-SET(v):       
    A = A ∪ {(u, v)}
    UNION(u, v)
return A

The time complexity for this algorithm is O(ElogE) or O(ElogV) because sorting of edges takes O(ElogE) time. After sorting, we repeatedly go through the edges to find-union algorithm, which takes O(logV) time. Now, the total time taken will be O(ElogE+ElogV), and hence the overall gtime complexity becomes O(ElogE) or O(ElogV).

Well, this was all one would need to know to understand Kruskal’s algorithm, thanks for reading!!!

Kruskal’s Algorithm

Written by Akshita Srivastava