KRUSKAL’S MINIMUM SPANNING TREE ALGORITHM.

Kruskal’s Algorithm is used to calculate the least cost of a graph’s Minimum Spanning tree, or MST (MINIMUM SPANNING TREE). It comes under the class of greedy algorithms. So what is a MINIMUM SPANNING TREE or what is a spanning tree? Before starting with Kruskal's algorithm we first have to get an idea about what a minimum spanning tree is.

SPANNING TREE

A spanning tree is a subset of Graph G that covers all of the vertices with the fewest amount of edges feasible. As a result, a spanning tree has no cycles(which means it is acyclic) and cannot be disconnected.

MINIMUM SPANNING TREE

A minimum spanning tree, also known as a minimum weight spanning tree, is a subset of the edges of a connected, edge-weighted undirected graph that binds all of the vertices together with the least feasible total edge weight and no cycles. That is, it is a spanning tree with the smallest feasible sum of edge weights.

KRUSKAL’S ALGORITHM

Kruskal’s algorithm is a greedy approach for finding a minimum spanning tree. The strategy is to pick the shortest edge repeatedly as long as the spanning tree constructed so far does not have a cycle.

STEPS to find MST USING KRUSKALS ALGORITHM:-

step 1:- Sort all the edges from low weight to high weight.

step 2:- Use the edge with the smallest weight to connect the graph’s vertices.

step 3:- If adding an edge causes a cycle, discard it and go on to the next edge with the least weight.

step 4:- Continue adding edges until all of the vertices are joined and you have a Minimum Spanning Tree (MST).

Let us consider the following example:

Start with a weighted graph.

Choose the edge with the least weight. If there is more than 1 edge with the same weight choose anyone.

Choose the next shortest edge and add it

Choose the next shortest edge that doesn’t create a cycle and add it.

Since all the vertices have been connected/included in the MST, so we stop.

Weight of the MST = Sum of all edge weights

= 2+2+3+3+4

= 14

Pseudo code of Kruskal’s algorithm

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)
as |E| >= |V| — 1
T(n) = E log E + E log E
= E log E

Kruskal’s algorithm has a time complexity of O(E log E) or O(V log V), Here E is the number of edges and V is the number of vertices.

Applications of Kruskal’s algorithm:

Landing cables.

TV Network.

Tour Operations.

LAN Networks.

A network of pipes for drinking water or natural gas.