A minimum spanning tree (MST) of a weighted graph G is a spanning tree of G whose edges sum to minimum weight.
In other words, a minimum spanning tree is a tree formed from a subset of the edges in a given undirected graph, with two properties:
it spans the graph, i.e., it includes every vertex in the graph, and
it is a minimum, i.e., the total weight of all the edges is as low as possible.
