Let’s start with defining what we are searching for – the Minimum Spanning Tree.

MST is a tree built on vertices of a given graph, so the total weight of all edges is minimum among all possible vertices. This graph is a subgraph of the given, and it contains V-1 edges, where V is a number of vertices.

One of the approaches to build MST is using Kruskal’s MST Algorithm:

1. Sort all edges by weight in ascending order
2. Label each vertex by the number of subtree it belongs to. In the beginning, each vertex is a separate single-element subtree. 3) Pick the first edge. Edge's vertices belong to different subtrees, so you can join them into one subtree. To do that, make their labels the same.
3. Pick the next 'smallest' edge. Check if the edge's vertices belong to different subtrees. If yes, change labels to join all vertices into one.
4. Repeat 3 until all vertices belong to one subtree. This tree is the answer.