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.

## Top comments (0)