Java 9 Data Structures and Algorithms

Traversal of a graph

The traversal of a graph is the graph's equivalent of the traversal of a tree, as discussed in an earlier chapter. Just as in the case of a tree, we can traverse either breadth-first or depth-first. However, unlike a tree, a graph can reach all the vertices without going through the edges. This makes it necessary to consider the traversal of all the edges and vertices separately. Another thing is that a graph has no designated root, so we can start from any particular vertex. Finally, since a graph may not be connected, we may not be able to traverse all the vertices/edges, starting from one single vertex. This is achieved by performing the traversal repeatedly, starting each time from any vertex that has not been visited ...