Java Reference
In-Depth Information
figure 24.6
(a) A graph
G
and
(b) its minimum
spanning tree
2
2
V
0
V
1
V
0
V
1
1
4
13
0
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
4
58
4 6
1
1
V
5
V
6
V
5
V
6
(a)
(b)
acyclic, it is
spanning
because it covers every vertex, and it is
minimum
for
the obvious reason. Suppose that we need to connect several towns with
roads, minimizing the total construction cost, with the provision that we can
transfer to another road only at a town (in other words, no extra junctions are
allowed). Then we need to solve a minimum spanning tree problem, where
each vertex is a town, and each edge is the cost of building a road between the
two cities it connects.
A related problem is the
minimum Steiner tree problem,
which is like the
minimum spanning tree problem, except that junctions can be created as
part of the solution. The minimum Steiner tree problem is much more diffi-
cult to solve. However, it can be shown that if the cost of a connection is
proportional to the Euclidean distance, the minimum spanning tree is at
most 15 percent more expensive than the minimum Steiner tree. Thus a mini-
mum spanning tree, which is easy to compute, provides a good approximation
for the minimum Steiner tree, which is hard to compute.
A simple algorithm, commonly called
Kruskal's algorithm,
is used to
select edges continually in order of smallest weight and to add an edge to the
tree if it does not cause a cycle. Formally, Kruskal's algorithm maintains a
forest—a collection of trees. Initially, there are single-node trees. Adding
an edge merges two trees into one. When the algorithm terminates, there is
only one tree, which is the minimum spanning tree.
1
By counting the number
of accepted edges, we can determine when the algorithm should terminate.
Figure 24.7 shows the action of Kruskal's algorithm on the graph shown
in Figure 24.6. The first five edges are all accepted because they do not create
cycles. The next two edges, (
v
1
,
v
3
) (of cost 3) and then (
v
0
,
v
2
) (of cost 4), are
rejected because each would create a cycle in the tree. The next edge consid-
ered is accepted, and because it is the sixth edge in a seven-vertex graph, we
can terminate the algorithm.
Kruskal's algorithm
is used to select
edges in order of
increasing cost and
adds an edge to
the tree if it does
not create a cycle.
V
1. If the graph is not connected, the algorithm will terminate with more than one tree. Each
tree then represents a minimum spanning tree for each connected component of the graph.
Search WWH ::
Custom Search