data structures using tree minimum spanning tree (mstis defined as spanning tree with weight less than or equal to the weight of every other spanning tree in other wordsa minimum spanning tree is spanning tree that has weights associated with its edgesand the total weight of the tree (the sum of the weights of its edgesis at minimum an analogy take an analogy of cable tv company laying cable in new neighbourhood if it is restricted to bury the cable only along particular pathsthen we can make graph that represents the points that are connected by those paths some paths may be more expensive (due to their length or the depth at which the cable should be buriedthan the others we can represent these paths by edges with larger weights thereforea spanning tree for such graph would be subset of those paths that has no cycles but still connects to every house many distinct spanning trees can be obtained from this graphbut minimum spanning tree would be the one with the lowest total cost properties possible multiplicity there can be multiple minimum spanning trees of the same weight particularlyif all the weights are the samethen every spanning tree will be minimum uniqueness when each edge in the graph is assigned different weightthen there will be only one unique minimum spanning tree minimum-cost subgraph if the edges of graph are assigned non-negative weightsthen minimum spanning tree is in fact the minimum-cost subgraph or tree that connects all vertices cycle property if there exists cycle in the graph that has weight larger than that of other edges of cthen this edge cannot belong to an mst usefulness minimum spanning trees can be computed quickly and easily to provide optimal solutions these trees create sparse subgraph that reflects lot about the original graph simplicity the minimum spanning tree of weighted graph is nothing but spanning tree of the graph which comprises of - edges of minimum total weight note that for an unweighted graphany spanning tree is minimum spanning tree example consider an unweighted graph given below (fig from gwe can draw many distinct spanning trees eight of them are given here for an unweighted graphevery spanning tree is minimum spanning tree (unweighted grapha figure unweighted graph and its spanning trees example consider weighted graph shown in fig from gwe can draw three distinct spanning trees but only single minimum spanning tree can be obtainedthat isthe one that has the minimum weight (costassociated with it