Minimum spanning tree

A minimum spanning tree (MST) is a special type of subgraph on a network that connects all the nodes together with the minimum possible total weight for the connections.

A minimum spanning tree is a type of tree. It does *not contain any cycles, and there is exactly one path between any two nodes in the tree.

Finding the minimum spanning tree is also known as the minimum connector problem.

Properties of a minimum spanning tree

Some important properties of a minimum spanning tree are:

• It includes all the nodes in the original network.
• It has exactly N-1 edges, where N is the number of nodes in the network.
• The total weight of the edges in the MST is the lowest possible.
• There are no cycles in the MST.