Kruskal’s Minimum Spanning Algorithm

First we need to know what is a minimum spanning tree?

The Minimum Spanning Tree is the one with the fewest cumulative edge weights. A minimum spanning tree has (V — 1) edges.

Kruskal’s Algorithm

Kruskal’s algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which, among all the trees that may be created from the graph, form a tree that contains every vertex and has the smallest sum of weights.

It is a greedy algorithm that find the local optimum in the hopes of finding a global optimum

We begin with the lightest edges and gradually increase the weight of the edges until we accomplish our aim.

What is Greedy Algorithm?

A greedy algorithm is one that selects the best solution for a specific time period without considering the consequences. This means that, regardless of whether the response is the global necessary solution or not, the algorithm will select the best-required solution for the current stage and will continue to select the most ideal solution until it reaches the conclusion. It is, however, straightforward to apply and, in the majority of cases, successful.

Steps

The steps for implementing Kruskal’s algorithm are as follows:

1. Sort all the edges from low weight to high
2. Add the spanning tree to the edge with the lowest weight. If adding the edge resulted in a cycle, discard it.
3. Continue to add edges until we’ve reached all of the vertices.

Pseudocode

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

Time Complexity

T(n)= O(1) + O(V) + O(E log E) + O(V log V) = O(E log E) + O(V LOG V)

|E| ≤ |V|²

log |E| < log |V|²

log |E|< 2 log |V|

Since |V| > |E| +1

T(n)= O(E log V)

Let us take an example –

Here, there are 5 vertices — A, B, C, D, E respectively and

7 edges — AB, BE, DE, AD, AC, CE, BA

So, we know that the required number of edges in MST will be E=V-1

5–1 = 4 edges.

Remove all the loops and parallel edges, image will look like this –

Next, sort the edges in ascending order.

AC = 3, DE = 5, AB = 7, CE = 7, BE = 9, AD = 12

Next, pick the least weightage edge and include in this edge. Here AC is selected with weight 3.

Now we will be looking for the next edge irrespective that it is connected or not to the preciously selected edges. So, DE is selected with weight 5.

Similarly, continuing the same steps, we will be adding AB to the list and putting it together. Here, AB is selected with weight 7.

Next, CE will be selected with weight 7.

This is our required minimum spanning tree. Hence, we were able to find MST using Kruskal's algorithm.