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.
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.
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.
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.
The time complexity of DFS
if the entire tree is traversed is where V is the number of nodes. In the case of a graph, the time complexity is where V is the number of vertexes and E is the number of edges.