Kruskal's Algorithm for finding minimum spanning tree

 The implementation of Kruskal’s Algorithm is explained in the following steps-

Step-01: Sort all the edges from low weight to high weight.

Step-02:

• Take the edge with the lowest weight and use it to connect the vertices of graph.
• If adding an edge creates a cycle, then reject that edge and go for the next least weight edge.

Step-03:
Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is obtained.

Example:

In the above example, we first listed all the edges in this ascending order.

Then, we started adding minimum weighted edge to the MST. If the addition of edge causes cycle in the graph we ignored it.

Repeat this process until all vertices are connected in the graph.

Time complexity:

In Kruskal's algorithm, most time consuming operation is sorting because the total complexity of the Disjoint-Set operations will be O ( E l o g V ) , which is the overall Time Complexity of the algorithm.

Source: classic data structure by samantha