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.
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.
Difference between Breadth First Search and Depth First Search
📌 BFS uses Queue data structure while DFS make use of Stack data structure.
📌 BFS can be used to find single source shortest path in an unweighted graph while in DFS we traverse through more edges to reach a particular destination.
📌 BFS considers all the neighbours first while DFS consider all the deep neighbours.
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 :