Java Reference
In-Depth Information
edges[i][1]
and the weight for the edge is
edges[i][2]
. For example, {
0
,
1
,
807
}
(line 8) represents the edge from vertex
0
(
edges[0][0]
) to vertex
1
(
edges[0][1]
)
with weight
807
(
edges[0][2]
). {
0
,
5
,
2097
} (line 8) represents the edge from ver-
tex
0
(
edges[2][0]
) to vertex
5
(
edges[2][1]
) with weight
2097
(
edges[2][2]
).
Line 35 invokes the
printWeightedEdges()
method on
graph1
to display all edges
in
graph1
.
The program creates the edges for
graph2
for the graph in Figure 29.3a in lines 37-44.
Line 46 invokes the
printWeightedEdges()
method on
graph2
to display all edges in
graph2
.
29.3
✓
✓
If a priority queue is used to store weighted edges, what is the output of the following
code?
Check
Point
PriorityQueue<WeightedEdge> q =
new
PriorityQueue<>();
q.offer(
new
WeightedEdge(
1
,
2
,
3.5
));
q.offer(
new
WeightedEdge(
1
,
6
,
6.5
));
q.offer(
new
WeightedEdge(
1
,
7
,
1.5
));
System.out.println(q.poll().weight);
System.out.println(q.poll().weight);
System.out.println(q.poll().weight);
29.4
If a priority queue is used to store weighted edges, what is wrong in the following
code? Fix it and show the output.
List<PriorityQueue<WeightedEdge>> queues =
new
ArrayList<>();
queues.get(
0
).offer(
new
WeightedEdge(
0
,
2
,
3.5
));
queues.get(
0
).offer(
new
WeightedEdge(
0
,
6
,
6.5
));
queues.get(
0
).offer(
new
WeightedEdge(
0
,
7
,
1.5
));
queues.get(
1
).offer(
new
WeightedEdge(
1
,
0
,
3.5
));
queues.get(
1
).offer(
new
WeightedEdge(
1
,
5
,
8.5
));
queues.get(
1
).offer(
new
WeightedEdge(
1
,
8
,
19.5
));
System.out.println(queues.get(
0
).peek()
.compareTo(queues.get(
1
).peek()));
A minimum spanning tree of a graph is a spanning tree with the minimum total
weights.
Key
Point
A graph may have many spanning trees. Suppose that the edges are weighted. A
minimum span-
ning tree
has the minimum total weights. For example, the trees in Figures 29.5b, 29.5c, 29.5d are
spanning trees for the graph in Figure 29.5a. The trees in Figures 29.3c and 29.3d are minimum
spanning trees.
The problem of finding a minimum spanning tree has many applications. Consider a com-
pany with branches in many cities. The company wants to lease telephone lines to connect all
the branches together. The phone company charges different amounts of money to connect
different pairs of cities. There are many ways to connect all branches together. The cheapest
way is to find a spanning tree with the minimum total rates.
minimum spanning tree
29.4.1 Minimum Spanning Tree Algorithms
How do you find a minimum spanning tree? There are several well-known algorithms for
doing so. This section introduces
Prim's algorithm
. Prim's algorithm starts with a spanning
tree
T
that contains an arbitrary vertex. The algorithm expands the tree by repeatedly adding a
vertex with the
lowest-cost
edge incident to a vertex already in the tree. Prim's algorithm is a
greedy algorithm, and it is described in Listing 29.4.
Prim's algorithm
Search WWH ::
Custom Search