What is a Minimum Spanning Tree?

graph-algorithm
minimum-spanning-tree

(Team) #1
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted directed or undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. It is a spanning tree whose sum of edge weights is as small as possible.

See article for properties and applications of a Minimum Spanning Tree.
This is a companion discussion topic for the original entry at http://iq.opengenus.org/what-is-a-minimum-spanning-tree/