User Tools

Site Tools


algorithms:mst

Minimum Spanning Tree

The Minimum Spanning Tree (MST) of a network is the minimum (according to the sum of some user-defined link weights) tree that contains all the nodes in the network. This tree is not necessarily unique, i.e. a network can have several minimum spanning trees. It can be used to eliminate redundant links and to perform network optimization. The network is considered undirected.

Input parameter Type Default Description
Initial Node* NodeLabel Random Initial NodeLabel to start the computation
Link weight text None Name of the link property to use as a distance between nodes. The property values should be positive numbers

* Required Field

A new link property is created, with value equal to 0 if the link does not belong to the MST. Each link in a MST in each connected component is identified by an integer number >0. The integer value also identifies the connected component the link belongs to, i.e., the MST in a component has the same value.



The next network presents two connected components. A MST in the smaller component is identified with value equal to 1, whereas in the big component the link property is equal to 2. Links not belonging to any MST are colored in blue.



References:

  • M. Newman, Networks: An introduction, Oxford University Press, 2010, ISBN: 978-0-19-920665-0, sec. 6.7.
algorithms/mst.txt · Last modified: 2018/12/20 14:27 by systems