Master Kruskal’s Algorithm Zero to Hero

Kruskal’s Algorithm is used while we are working with trees and graphs. It is applied and finds a minimum spanning tree. So now the question arises what exactly a minimum spanning tree is? So the condition depends is that it is a connected graph with no direction, so the spanning tree of that graph is a subset or a subgraph that is a tree connected through links (vertices). The graph can have many spanning trees that are different from each other. A Minimum spanning tree or minimum weighted spanning tree , as the name suggests, is a graph with fewer weights on edges. Weight of a spanning tree is the sum of weights on edges.

If the number of vertices are V, the edges will be equal to (V-1) of the given graph.

Some of the real Life applications of MST are

1. Network Designs
2. Error Correction
3. Reducing data storage for sequence of amino acids in protein
4. Water Supply Networks
5. Bottleneck paths

Basic rule of Kruskal’s Algorithm is to choose those edges with minimum weight in such a way that no closed loop is formed between the graphs. Usage of disjoint set data structure. To form a combined tree Kruskal calls for the UNION procedure. Safest edges are to be put inside the forest.

Pseudocode:

Pseudocode

FIND-SET(u) returns an element from the set containing u.helps in determining 2 vertices u and v belongings of the same tree. So by testing they are supposed to be equal.

Steps to find Minimum Spanning Tree using Kruskal’s Algorithm.

1. Edges should be sorted in nondecreasing order of their weight.
2. Smallest edge should be picked first and check whether it is making a closed loop or cycle so far. If not then add the edge else remove it.
3. Repeat step 2 till there are (V-1) edges in the tree.
4. Repeat these steps and at last find the sum of the edges that are involved in the formation of minimum spanning tree

STEPS

Step 1: In the given connected and undirected graph we have to sort the edges in nondecreasing order of their weight.

Step 2: So start with selecting the edge with weight 2 that is the minimum edge , we are kept in mind that while connecting it will not form any close loop so connect edge C with edge B.

Step 3: Now Again select the minimum edge that will be 3 so connect edge F with edge E and then connect E with edge D. We are ignoring edge C with edge D because that will create a closed loop so we will avoid it.

Step 4: Again with the same logic selecting 4 as min edge and connecting edge A with edge B and avoiding edge A with edge C and edge C with edge E.

Total Cost of final Minimum spanning tree is being calculated by the sum of all the edges in the final Minimum spanning tree

Time Complexity of Kruskal’s algorithm is o(E Log V),

E- No. of Edges

V- No. of Vertices

Applications in Real-life of Kruskal’s Algorithm

1. Layout of electric cables and TV Networks
2. LAN Connections
3. Usage in Geographical Maps.