How to build Depth First Search?
Difficulty: Easy
Intent
A must know algorithm to know for coding interviews. To the uninitiated, just the name alone can sound intimidating but I promise you we will be solving this common alogirthm question in a few lines of code.
Code
Say we have a graph that is like a tree like data structure that has a bunch of nodes and each node is going to optionally have some children nodes.
We will be exploring one branch at a time going as deep on that branch as possible before moving onto the next branch. So in the graph above, we will be traversing the branch starting from node A to its last node which is node E and if any nodes on this branch have children nodes then we will use our algorithm to explore those branches as well. Our end result will be an array of all the nodes that we have explored but in the order of depth first search. Lets take a look at the first step.
As you can see, we explored the entire first branch of this graph tree like structure and populated the branch’s existing nodes in our output array. But because node B has a child node we also have to call our depth first search algorithm on all children nodes of each node so you can imagine that we will be using some measure of recursion in our algorithm. And that is pretty much the entirety of depth first search. We start traversing the entirety of one branch and if any of the nodes on that branch have children nodes then we call our depth first search algorithm on those children nodes as well.
That is the entirey of the code for depth first search, see not too bad.
Time Space Complexity
The time space analysis for depth first search is not too complex at all. Simply put, because we are traversing each node in the graph and consequentially, traversing every edge (distance between nodes), then we say the time complexity is O(n + e) where n represents the number of nodes and e represents the number of edges we will traverse in order to finish completing depth first search.
For the space complexity, because we are addding calls to the stack when we call depth first search on children nodes then our space complexity is determined by the number of frames we are adding to the stack. So our space complexity is O(n). And that is it for depth first search. A very important. algorithm to get familiar with but not as intimidating as it might sound. I hope this helps you feel at ease with this common algorithm and if you need anymore help please feel free to reach out to me.
