This content originally appeared on DEV Community and was authored by DEV Community
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
Rohithv07
/
LeetCodeTopInterviewQuestions
Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions
LeetCodeTopInterviewQuestions
Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions-easy/
Also Question answered from CodeSignal.com : https://app.codesignal.com/
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-03-13T05:12:38+00:00) Graph Algorithm – Depth First Search. Retrieved from https://www.scien.cx/2022/03/13/graph-algorithm-depth-first-search/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.