Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures
dfs
depth first search
algorithms
graph traversal

What is Depth First Search?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.

1 of 8

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)O(V) where V is the number of nodes. In the case of a graph, the time complexity is O(V+E)O(V + E) where V is the number of vertexes and E is the number of edges.

RELATED TAGS

data structures
dfs
depth first search
algorithms
graph traversal
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring