NCSS Statistical Software NCSS.com
478-1
© NCSS, LLC. All Rights Reserved.
Chapter 478
Minimum Spanning Tree
Introduction
A minimum spanning tree links all nodes (points or vertices) of a network with the minimum length of all
arcs. This procedure finds the minimum spanning tree of a network using a greedy algorithm. If the network
is not connected, the solution, called a minimum spanning forest, is a combination of minimum spanning
trees formed on the connected subsets.
The algorithm is used in applications such as transportation networks, computer networks, and water
networks where a tree connecting all nodes must have minimum length.
Greedy Algorithm
The algorithm proceeds as follows:
1. Start with any node.
2. Connect this node to its nearest neighbor using any of the available branches.
3. Find the unconnected node that is closest any of the connected nodes. Connect these nodes.
4. Repeat steps 2 and 3 until all nodes have been connected.
NCSS Statistical Software NCSS.com
Minimum Spanning Tree
478-2
© NCSS, LLC. All Rights Reserved.
Data Structure
This procedure requires a special data format in which the rows represent the network branches. Each
branch is defined by two nodes and the distance between its nodes.
Consider the following example. Each row represents an electric cable that connects two orchards on a large
fruit farm that produces many types of fruit. The nodes are identified by the type of fruit grown in that
section. The length of the cable is given in the last column. These data are stored in the dataset Wiring
Network.
Wiring Network Dataset
Site1 Site2 Length
A1
A2
6.8
A1
A3
3.2
A2
B1
9.1
A2
A3
8.5
A2
B2
7.2
B1
B2
10.3
A3
B2
14.8
A3
C1
5.6
B2
C1
8.2
B2
C2
9.1
C1
C2
10.9
Z1
Z2
0.5
Z2
Z3
3.4
Z1
Z3
2.2
NCSS Statistical Software NCSS.com
Minimum Spanning Tree
478-3
© NCSS, LLC. All Rights Reserved.
Example 1 – Wiring Network
This section presents an example of how to create a minimum spanning tree from the data presented in the
example given above. The data are contained in the Wiring Network database. Each row represents a
possible arc (connection or branch) of the network by identifying the end points along with the length
between them.
Wiring Network Dataset
Site1 Site2 Length
A1
A2
6.8
A1
A3
3.2
A2
B1
9.1
A2
A3
8.5
A2
B2
7.2
B1
B2
10.3
A3
B2
14.8
A3
C1
5.6
B2
C1
8.2
B2
C2
9.1
C1
C2
10.9
Z1
Z2
0.5
Z2
Z3
3.4
Z1
Z3
2.2
Setup
To run this example, complete the following steps:
1 Open the Wiring Network example dataset
• From the File menu of the NCSS Data window, select Open Example Data.
• Select Wiring Network and click OK.
2 Specify the Minimum Spanning Tree procedure options
• Find and open the Minimum Spanning Tree procedure using the menus or the Procedure
Navigator.
• The settings for this example are listed below and are stored in the Example 1 settings file. To load
these settings to the procedure window, click Open Example Settings File in the Help Center or File
menu.
Specifications Tab
___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Node 1 Column ................................................ Site1
Node 2 Column ................................................ Site2
Length Column ................................................ Length
NCSS Statistical Software NCSS.com
Minimum Spanning Tree
478-4
© NCSS, LLC. All Rights Reserved.
3 Run the procedure
• Click the Run button to perform the calculations and generate the output.
Minimum Spanning Tree
Minimum Spanning Forest
─────────────────────────────────────────────────────────────────────────
Arc Length Site1 Site2
Tree (Row) (Length) (Node 1) (Node 2)
──────────────────────────────────────────────────────────────────────
1 1 6.8 A1 A2
1 2 3.2 A1 A3
1 3 9.1 A2 B1
1 5 7.2 A2 B2
1 8 5.6 A3 C1
1 10 9.1 B2 C2
2 12 0.5 Z1 Z2
2 14 2.2 Z1 Z3
Total 43.7
─────────────────────────────────────────────────────────────────────────
This report lists the solution by giving the arcs that form the minimum spanning tree(s). Note that in this
example, there were two trees, so the solution is called a forest. You can see that there are no defined arcs
between the first and second trees.
Node Connections
Node Connections
─────────────────────────────────────────────────────────────────────────
Connected
Node Nodes
─────────────────────────────────────────
A1 A2*, A3*
A2 A1*, B1*, A3, B2*
A3 A1*, A2, B2, C1*
B1 A2*, B2
B2 A2*, B1, A3, C1, C2*
C1 A3*, B2, C2
C2 B2*, C1
Z1 Z2*, Z3*
Z2 Z1*, Z3
Z3 Z2, Z1*
─────────────────────────────────────────────────────────────────────────
* The connected node is starred if the pair is in the minimum spanning tree.
This report presents a list of the nodes followed by the nodes they are connected with. If the pair of nodes is
in the minimum spanning tree, the connected note is starred.
NCSS Statistical Software NCSS.com
Minimum Spanning Tree
478-5
© NCSS, LLC. All Rights Reserved.
Possible Network Arcs
Possible Network Arcs
─────────────────────────────────────────────────────────────────────────
Arc Length Site1 Site2
Tree (Row) (Length) (Node 1) (Node 2)
──────────────────────────────────────────────────────────────────────
1 1* 6.8 A1 A2
1 2* 3.2 A1 A3
1 3* 9.1 A2 B1
4 8.5 A2 A3
1 5* 7.2 A2 B2
6 10.3 B1 B2
7 14.8 A3 B2
1 8* 5.6 A3 C1
9 8.2 B2 C1
1 10* 9.1 B2 C2
11 10.9 C1 C2
2 12* 0.5 Z1 Z2
13 3.4 Z2 Z3
2 14* 2.2 Z1 Z3
─────────────────────────────────────────────────────────────────────────
* The starred arcs are in the minimum spanning tree.
This report lists the arcs that were input from the dataset. The started arcs are in the minimum spanning
tree.
