GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1037

F IGURE 28.10

The graph is displayed in the pane.

28.9

Will Listing 28.7 DisplayUSMap.java work, if the code in lines 30-34 in Listing 28.6
GraphView.java is replaced by the following code?
if (i < v) {
int x2 = graph.getVertex(v).getX();
int y2 = graph.getVertex(v).getY();

✓ ✓

Check

Point

// Draw an edge for (i, v)
getChildren().add( new Line(x1, y1, x2, y2));
}

28.10

For the graph1 object created in Listing 28.1, TestGraph.java, can you create a
GraphView object as follows?
GraphView view = new GraphView(graph1);

28.6 Graph Traversals
Depth-first and breadth-first are two common ways to traverse a graph.

Key
Point

Graph traversal is the process of visiting each vertex in the graph exactly once. There are two
popular ways to traverse a graph: depth-first traversal (or depth-first search ) and breadth-
first traversal (or breadth-first search ). Both traversals result in a spanning tree, which can be
modeled using a class, as shown in Figure 28.11. Note that Tree is an inner class defined in
the AbstractGraph class. AbstractGraph<V>.Tree is different from the Tree interface
defined in Section 25.2.5. AbstractGraph.Tree is a specialized class designed for describing
the parent-child relationship of the nodes, whereas the Tree interface defines common opera-
tions such as searching, inserting, and deleting in a tree. Since there is no need to perform these
operations for a spanning tree, AbstractGraph<V>.Tree is not defined as a subtype of Tree .
The Tree class is defined as an inner class in the AbstractGraph class in lines 226-293
in Listing 28.3. The constructor creates a tree with the root, edges, and a search order.
The Tree class defines seven methods. The getRoot() method returns the root of the
tree. You can get the order of the vertices searched by invoking the getSearchOrder()
method. You can invoke getParent(v) to find the parent of vertex v in the search. Invok-
ing getNumberOfVerticesFound() returns the number of vertices searched. The method
getPath(index) returns a list of vertices from the specified vertex index to the root. Invok-
ing printPath(v) displays a path from the root to v . You can display all edges in the tree
using the printTree() method.

depth-first search
breadth-first search