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 yet already. This is a simple extension of the basic breadth-first or depth-first traversal that we are going to discuss here.
First, let's discuss visiting vertices using both the breadth-first and depth-first search. It involves maintaining two collections...
