588
Graph Algorithms
example 9
We will find a minimal spanning tree for the graph of Figure 7.7. We let node 1 be
the arbitrary initial node in IN. Next we consider all the nodes adjacent to any node
in IN, that is, all nodes adjacent to 1, and select the closest one, which is node x.
Now IN = 51, x6, and the arc between 1 and x is part of the minimal spanning tree.
Next we consider all nodes not in IN that are adjacent to either 1 or x. The closest
such node is 3, which is 4 units away from x. The arc between 3 and x is part of the
minimal spanning tree. For IN = 51, x, 36, the next closest node is node 4, 1 unit
away from 3. The remaining nodes are added in the order y and then 2. Figure 7.11
shows the minimal spanning tree.
Figure 7.11
praCtiCe 13 Find a minimal spanning tree for the graph of Figure 7.10.
example 10
Seismic sensing instruments are to be distributed at sites along a volcanic rift zone,
as shown in Figure 7.12a, where the distances in meters between sites are given.
(Distances between some sites are not shown because of natural hazards that would
prevent a direct connection.) The most economical way to wire the devices so that
they are all connected is to create a minimal spanning tree for the graph, as shown
in Figure 7.12b. The total length of wire involved is 975 meters.
186
321
172
404
592
987
1120
844
123 47
215
(a)
186
321
172
404
592
987
1120
844
123 47
215
(b)
Figure 7.12
■