Graph Implementations - Data Structures and Abstractions with Java - page 777

A NSWERS TO S ELF -T EST Q UESTIONS

1.

0 1 2 3

T T T

0

1

T T T

2 T T T

3 T T T

2. Vertex 0 references the list 1, 2, 3.
Vertex 1 references the list 0, 2, 3.
Vertex 2 references the list 0, 1, 3.
Vertex 3 references the list 0, 1, 2.
3. VertexInterface<String> vertexA = new Vertex<String>("A");
VertexInterface<String> vertexB = new Vertex<String>("B");
VertexInterface<String> vertexC = new Vertex<String>("C");
vertexA.addEdge(vertexB, 2.0);
vertexB.addEdge(vertexC, 3.0);
vertexC.addEdge(vertexA, 4.0);
vertexA.addEdge(vertexC, 5.0);

4.

DirectedGraph<String> myGraph = new DirectedGraph<String>();
myGraph.addVertex("A");
myGraph.addVertex("B");
myGraph.addVertex("C");
myGraph.addEdge("A", "B", 2.0);
myGraph.addEdge("B", "C", 3.0);
myGraph.addEdge("C", "A", 4.0);
myGraph.addEdge("A", "C", 5.0);

5.

QueueInterface<String> bfs = myGraph.getBreadthFirstTraversal("A");
while (!bfs.isEmpty())
System.out.print(bfs.dequeue() + " ");
System.out.println();

6.

StackInterface<String> path = new LinkedStack<String>();
int pathLength = myGraph.getShortestPath("A", "C", path);
System.out.println("The shortest path from A to C has length " + pathLength +
" and passes through the following vertices:");
while (!path.isEmpty())
System.out.print(path.pop() + " ");
System.out.println();