Graph Traversals

Depth-first and breadth-first are two common ways to traverse a graph.
Graph traversalis the process of visiting each vertex in the graph exactly once. There are two popular ways to traverse a graph:depth-first traversal(ordepth-first search) andbreadth-first traversal(orbreadth-first search). Both traversals result in a spanning tree, which can be modeled using a class, as shown in Figure below. Note thatTreeis an inner class defined in theAbstractGraphclass.AbstractGraph.Treeis different from theTreeinterface defined in Searching for an Element.AbstractGraph.Treeis a specialized class designed for describing the parent–child relationship of the nodes, whereas theTreeinterface 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.Treeis not defined as a subtype ofTree.

TheTreeclass is defined as an inner class in theAbstractGraphclass in lines 226–293 in AbstractGraph.java. The constructor creates a tree with the root, edges, and a search order.

TheTreeclass defines seven methods. ThegetRoot()method returns the root of the tree. You can get the order of the vertices searched by invoking thegetSearchOrder()method. You can invokegetParent(v)to find the parent of vertexvin the search. InvokinggetNumberOfVerticesFound()returns the number of vertices searched. The methodgetPath(index)returns a list of vertices from the specified vertex index to the root. InvokingprintPath(v)displays a path from the root tov. You can display all edges in the tree using theprintTree()method.

The above is the detailed content of Graph Traversals. For more information, please follow other related articles on the PHP Chinese website!