Understanding Depth First Search (DFS)

Question

What is Depth First Search (DFS) and how does it differ when used on trees versus graphs? DFS is defined as a Turing complete algorithm which can be used to explore finite discrete structures. Theoretically, DFS employs backtracking since the algorithm will traverse down a particular branch of the tree until it reaches the leaves before moving and attempting another branch. This algorithm is naturally recursive as any function will return when it reaches the base case which in this scenario is the leaf of a tree. However, DFS on a tree is different than when it is implemented on other data structures such as graphs. The differences that arise when implementing this algorithm mechanically is due to the presence of cycles in graphs as opposed to simply expanding trees. There are two caveats which arise in the presence of cycles which is we don’t want to traverse in already visited nodes and the second being the need for an iterative procedure in order to visit a node’s neighbors. Another difference is in the way nodes are expanded since when graph traversal is performed DFS usually utilizes a stack where new children nodes are pushed on top and are looked at first when traversed.

Answer 1

DFS ( Depth First Search ) is an algorithm of graph exploration that goes along each branch down to the last child node before backtracking. When trees T ( more specifically, acyclic connected graphs ) are considered, it runs rather straightforward, visiting all the nodes of the tree. Nevertheless, in the case of graphs with loops, it is essential to control which vertices were visited so as not to get stuck in infinite loops. Casewise, a particular order is used, such as pre-order, in-order, or post-order to carry out the traversals for DFS.