Understanding depth first traversal

Unlike linear data structures, we cannot traverse all nodes in a graph using simple loops. The depth-first traversal is a fundamental traversal algorithm for graph data structures that uses depth-first search to visit all nodes connected to a node. The depth-first search is a recursive algorithm that starts from a node and explores one complete branch at a time. As we will see later, the depth-first traversal algorithm makes multiple depth-first searches from different sources to traverse all the nodes in a graph.

Algorithm

The depth-first traversal algorithm utilises the depth-first search algorithm to traverse all nodes connected to a given node. The depth-first search algorithm is quite straightforward as it fully explores one branch before backtracking to other branches. It can be considered a generalisation of the three tree traversal algorithms (preorder, inorder and postorder traversal).

The simple recursive equation given below summarizes the depth-first search algorithm from a source node.