DEV Community

Cover image for Graph Algorithm - Depth First Search
Rohith V
Rohith V

Posted on

Graph Algorithm - Depth First Search

Depth First Search

Depth First Search(DFS) is a graph traversal algorithm that starts with a node in the graph and goes deeper and deeper until we reach a node that does not have further children. Then the algorithm backtracks towards the most recent node and continues the search if there are children unvisited.
Consider a graph given below, with node 0 as the start node. In the DFS algorithm, we will start our search from node 0 and mark it as visited. We continue our search deeper until we reach a dead-end and keep on backtracking to finding a node that has some unvisited children.

DFS Starting

General Algorithm

๐Ÿ“Œ If the graph is disconnected, run a loop from node 0.
๐Ÿ“Œ A recursive function is called that takes the node and visited array.
๐Ÿ“Œ Mark the node as a visited node and store the node in the result list.
๐Ÿ“Œ Traverse the children of the current node and call the recursive function if the child is not visited.

DFS Walkthrough

Time Complexity

๐Ÿ“Œ We are traversing through all the nodes and edges. So time complexity will be O(V + E) where V = vertices or node, E = edges.
๐Ÿ“Œ We use a visited array, adjacency list for the graph and some space for the recursion stack. So the space complexity will be O(V) + O(V + E) + Auxiliary space for recursion stack. (Ignoring the space for the final result list).

Code

DFS Code

Originally Published On LinkedIn Newsletter : LinkedIn Newsletter

Github Link

GitHub logo Rohithv07 / LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions




Top comments (0)