Minimum Spanning Tree
A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight among all the possible spanning trees.
The minimum spanning tree has all the properties of a spanning tree with an added constraint of having the minimum possible weights among all possible spanning trees. Like a spanning tree, there can also be many possible MSTs for a graph.
- Let’s look at the MST of the above example Graph,
What is Minimum Spanning Tree (MST)
A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight among all the possible spanning trees
A spanning tree is defined as a tree-like subgraph of a connected, undirected graph that includes all the vertices of the graph. Or, to say in Layman’s words, it is a subset of the edges of the graph that forms a tree (acyclic) where every node of the graph is a part of the tree.
The minimum spanning tree has all the properties of a spanning tree with an added constraint of having the minimum possible weights among all possible spanning trees. Like a spanning tree, there can also be many possible MSTs for a graph.