What is Depth First Search?

The Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures which uses the idea of backtracking. It explores all the nodes by going forward if possible or uses backtracking.

Note: It can be implemented using a stack.

The algorithm

Here are the steps for the DFS algorithm:

• Pick a node and push all its adjacent nodes into a stack.

• Pop a node from the stack and push all its adjacent nodes into a stack.

• Repeat this process until the stack is empty or you meet a goal.

The program can be stuck in an infinite loop if a node is revisited and was not marked as visited before. Hence, prevent exploring nodes that are visited by marking them as visited.

Example

We have a directed graph of five nodes with G being the node to be searched. The nodes will be marked as visited using the visited array while adjacent nodes will be added to the stack.

Explanation

Starting from the source node A, we keep moving to the adjacent nodes A to B to D where we reach the farthest level. Then we backtrack to the previous node B and pick an adjacent node. Once again, we probe till the farthest level where we hit the desired node G.

Time complexity

The time complexity of DFS if the entire tree is traversed is $O(V)$ where V is the number of nodes. In the case of a graph, the time complexity is $O(V + E)$ where V is the number of vertexes and E is the number of edges.