Java Reference
In-Depth Information
2
5
10
4
20
10
1
3
6
2
11
3
3
15
5
Figure11.26
Example graph for Chapter 11 exercises.
11.16 The single-destination shortest-paths problem for a directed graph is to find
the shortest path from every vertex to a specified vertex V. Write an algorithm
to solve the single-destination shortest-paths problem.
11.17 List the order in which the edges of the graph in Figure 11.26 are visited
when running Prim's MST algorithm starting at Vertex 3.
Show the final
MST.
11.18 List the order in which the edges of the graph in Figure 11.26 are visited
when running Kruskal's MST algorithm. Each time an edge is added to the
MST, show the result on the equivalence array, (e.g., show the array as in
Figure 6.7).
11.19 Write an algorithm to find a maximum cost spanning tree, that is, the span-
ning tree with highest possible cost.
11.20 When can Prim's and Kruskal's algorithms yield different MSTs?
11.21 Prove that, if the costs for the edges of Graph G are distinct, then only one
MST exists for G.
11.22 Does either Prim's or Kruskal's algorithm work if there are negative edge
weights?
11.23 Consider the collection of edges selected by Dijkstra's algorithm as the short-
est paths to the graph's vertices from the start vertex. Do these edges form
a spanning tree (not necessarily of minimum cost)? Do these edges form an
MST? Explain why or why not.
11.24 Prove that a tree is a bipartite graph.
11.25 Prove that any tree (i.e., a connected, undirected graph with no cycles) can
be two-colored. (A graph can be two colored if every vertex can be assigned
one of two colors such that no adjacent vertices have the same color.)
11.26 Write an algorithm that determines if an arbitrary undirected graph is a bipar-
tite graph. If the graph is bipartite, then your algorithm should also identify
the vertices as to which of the two partitions each belongs to.
