Chapter 29 Weighted Graphs and Applications
Section 29.2 Representing Weighted Graphs
1. True or False? The WeightedEdge class extends Edge.
a. True
b. False
#
2. A WeightedEdge object contains the public data fields .
a. u
b. v
c. weight
d. length
#
Section 29.3 The WeightedGraph Class
4. The WeightedGraph is a subtype of .
a. UnweightedGraph
b. AbstractGraph
c. Graph
d. WeightedEdge
#
3. The adjacent edge for each vertex in the WeightedGraph class is stored in .
a. an ArrayList
b. a LinkedList
c. a PriorityQueue
d. a Stack
#
5. The addEdge(u, v, w) method performs the following operations:
a. Invokes super.add(u, v) to add an edge.
b. Adds a weighed edge to the adjacent list for vertex u.
c. Adds a weighed edge to the adjacent list for vertex v.
#
Section 29.4 Minimum Spanning Trees
9. Suppose a weighted graph is created in the following code. What is total weight of a minimum spanning tree?
Integer[] vertices = {0, 1, 2, 3, 4};
int[][] edges = {
{0, 1, 9}, {0, 2, 5},
{1, 0, 9}, {1, 2, 6}, {1, 3, 4}, {1, 4, 7},
{2, 0, 5}, {2, 1, 6}, {2, 3, 3},
{3, 1, 4}, {3, 2, 3}, {3, 4, 1},
{4, 1, 7}, {4, 3, 1}
};
WeightedGraph<Integer> graph1 =
new WeightedGraph<>(vertices, edges);
WeightedGraph<Integer>.MST tree1 = graph1.getMinimumSpanningTree();
System.out.println(“Total weight is ” + tree1.getTotalWeight());
a. 10
b. 11
c. 12
d. 13
e. 14
#
7. The MST class is subtype of .
a. BST
b. AVLTree
c. SearchTree
d. Tree
#
8. The getMinimumSpanningTree() method returns .
a. an ArrayList
b. a LinkedList
c. a queue
d. a MST
#
6. A graph may have several minimum spanning tree.
a. True
b. False
#
Section 29.5 Finding Shortest Paths
13. Suppose a weighted graph is created in the following code. What is the shortest path from vertex 4 to 0?
Integer[] vertices = {0, 1, 2, 3, 4};
int[][] edges = {
{0, 1, 9}, {0, 2, 5},
{1, 0, 9}, {1, 2, 6}, {1, 3, 4}, {1, 4, 7},
{2, 0, 5}, {2, 1, 6}, {2, 3, 3},
{3, 1, 4}, {3, 2, 3}, {3, 4, 1},
{4, 1, 7}, {4, 3, 1}
};
WeightedGraph<Integer> graph1 =
new WeightedGraph<>(vertices, edges);
WeightedGraph<Integer>.ShortestPathTree tree1 =
graph1.getShortestPath(graph1.getIndex(0));
System.out.println(“Shortest path from 4 to 0 is ” +
tree1.getPath(4));
a. 4 1 0
b. 4 1 3 2 0
c. 4 3 2 0
d. 4 3 1 0
e. 4 1 2 0
#
11. The ShortestPathTree class is subtype of .
a. BST
b. AVLTree
c. UnweightedGraph.SearchTree
d. Tree
#
12. The getShortestPath() method returns .
a. an ArrayList
b. a LinkedList
c. a ShortestPathTree
d. a MST
#
10. A of a graph is a subgraph that is a tree and connects all vertices in the graph.
a. spanning tree
b. shortest path