Page 375 -
P. 375
MINIMAL SPANNING TREE PROBLEM 355
A Minimal Spanning Tree Algorithm
For a network consisting
of N nodes, a spanning A spanning tree for an N-node network is a set of N–1 arcs that connects every node to
tree will consist of N –1
arcs. every other node. A minimal spanning tree provides this set of arcs at minimal total arc
cost, distance or some other measure. The network algorithm that can be used to solve
the minimal spanning tree problem is simple. The steps of the algorithm are as follows:
Step 1. Arbitrarily begin at any node and connect it to the closest node in terms
of the criterion being used (e.g., time, cost or distance). The two nodes
are referred to as connected nodes, and the remaining nodes are referred
to as unconnected nodes.
Step 2. Identify the unconnected node that is closest to one of the connected
nodes. Break ties arbitrarily if two or more nodes qualify as the closest
node. Add this new node to the set of connected nodes. Repeat this step
until all nodes have been connected.
This network algorithm is implemented by making the connection decisions directly
Dijkstre also published on the network.
an algorithm for the Referring to the communications network for the regional computer centre and arbi-
spanning tree problem trarily beginning atnode1, wefindtheclosestnodeisnode2 witha distance of20.Usinga
in 1956.
bold line to connect nodes 1 and 2, step 1 of the algorithm provides the following result:
5
40
2 50 30
20
40 3
1 10 40
30
4 30
40 20
6
In step 2 of the algorithm, we find that the unconnected node closest to one of the
connected nodes is node 4, with a distance of 30km from node 1. Adding node 4 to
the set of connected nodes provides the following result:
5
40
2 50 30
20
40 3
1 10 40
30
4 30
40 20
6
Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
