Graph Traversals

Depth-first and breadth-first are two common ways to traverse a graph.
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 below. Note that Tree is an inner class defined in the AbstractGraph class. AbstractGraph.Tree is different from the Tree interface defined in Searching for an Element. AbstractGraph.Tree is a specialized class designed for describing the parent–child relationship of the nodes, whereas the Tree interface defines common operations such as searching, inserting, and deleting in a tree. Since there is no need to perform these operations for a spanning tree, AbstractGraph.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 AbstractGraph.java. 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. Invoking getNumberOfVerticesFound() returns the number of vertices searched. The method getPath(index) returns a list of vertices from the specified vertex index to the root. Invoking printPath(v) displays a path from the root to v. You can display all edges in the tree using the printTree() method.