Depth First Search

In this article, I will define the Depth First Search (DFS) algorithm. I will be explaining the definition and the uses of the search on a tree and a graph.

DFS is a tree and graph traversal algorithm used to explore node(s) in a tree or graph data structure. Depending on the data structure a node will have different meaning in regards to the relationship with other nodes. For example, a node in a tree is a single element in a tree that will either be connected to another node via parent-child relationship. While a node in graph will be connected to other nodes via neighbor relationship.

DFS on a tree has three traversal methods: pre-order, in-order, and post-order. These tree traversals generally go from left to right. In the pre-order traversal, we would start from the current node, then traverse the left subtree, and finally traverse the right subtree. In-order traversal, we would start from the root node and traverse the left subtree, then the current node, and finally traverse the right subtree. The last traversal method post-order traversal, we would start from the root node and traverse the left subtree, then the right subtree, and finally visit the current node. Below is an example of in-order traversal these steps are basis for how each traversal method operates:

1. Traverse the left subtree
2. Visit the current node
3. Traverse the right subtree

We now get into using these same traversals with a graph data structure. The main difference in using these traversal methods with graphs are that you have to mark each visited node. The reason for the marking of nodes because graph contains cycles and we don’t want to get stuck in an infinite loop.

When determining when to use the following algorithm we chose by first understanding if the problem is a tree/graph problem or not. This can be difficult at first because all tree/graph problem don’t just same “I’m a tree” or “I’m a graph”. Determining whether a problem is a tree/graph is done by understanding what the problem is asking just like any other algorithm. Generally identifying DFS problem you will notice whether the question is asking for the following:

• Max Depth of Tree, anything tree

• Combination Search

• “Generate all possible”

• “Number of ways”

The strategy to determining which traversal methods to use depends on the algorithm that is being design. When thinking about picking pre-order method, you may be thinking of exploring the root prior to the leaves. While using post-order method, you may be thinking of exploring the leaves before the root. In-order is best used, when you know that the tree has a sequence in the nodes.

To implement DFS algorithm is simple for both a tree and a graph. It is implemented just as it is defined. See the example below written in Python:

                    def dfs(root):
                    if not root:
                    return
                    # Traverse the left subtree
                    dfs(root.left)
                    # Visit current node
                    print(root)
                    # Traverse the right subtree
                    dfs(root.right)
                    return
                  
                

The difference in the implementation for a tree and a graph is including a visited set as a state. In the implementation of DFS in a graph you will add a visited set to store all the vertices/nodes that were already visited. Since a graph uses a visited set, you no longer need to used the goal state that a tree would used to find a left node. The python example below shows the basic implementation to start from:

                  def dfs(root, visited):
                  # Visit all neighbors
                  for neighbor in get_neighbors(root):
                  # Check if neighbor has been visited before
                  if neighbor in visited:
                  continue

                  # Add neighbor to visited set
                  visited.add(neighbor)

                  # Add neighbor to stack
                  dfs(neighbor, visited)