Coders Packet

MST using Kruskal’s Algorithm in C++

By Anirudh C V

Find the Sum of Weights of the Edges of the Minimum Spanning Tree in a given Weighted, Undirected and Connected Graph of V vertices and E edges.

There are various Algorithms to find out the Minimum Spanning Tree. Prim's and Kruskal's are the most common algorithms to find out the Minimum Spanning Tree.

Below are the steps for finding Minimum Spanning Tree using Kruskal’s Algorithm :

    1. Sort all the edges in non-decreasing order of their weight.

    2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.

    3. Repeat step-2 until there are (V-1) edges in the spanning tree.

Download Complete Code


No comments yet