Traversal
One of the operations that’s commonly performed on a graph is traversal – that is, visiting all of the nodes in some particular order. Of course, the aforementioned problem can be solved in various ways, such as using DFS or BFS approaches. It is worth mentioning that the traversal topic is strictly connected with the task of searching for a given node in a graph.
Depth-first search
The first graph traversal algorithm described in this chapter is named DFS. It tries to go as deep as possible. First, it proceeds to the next levels of the nodes instead of visiting all the neighbors of the current node. Its steps, in the context of the example graph, are as follows:
Figure 8.14 – Illustration of a DFS of a graph
Of course, it can be a bit difficult to understand how the DFS algorithm operates just by looking at the preceding diagram. For this reason, let’s try to analyze its stages.
In Step 1, there’s...
