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.

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.

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

Originally Published On LinkedIn Newsletter : LinkedIn Newsletter

Github Link