Java Reference
In-Depth Information
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);
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
Search WWH ::
Custom Search