# 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

- Network Designs
- Error Correction
- Reducing data storage for sequence of amino acids in protein
- Water Supply Networks
- 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:

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.

- Edges should be sorted in nondecreasing order of their weight.
- 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.
- Repeat step 2 till there are (V-1) edges in the tree.
- 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**

- Layout of electric cables and TV Networks
- LAN Connections
- Usage in Geographical Maps.