DFS–depth-first search is one of the algorithms to explore the tree nodes where you first deep dive the tree and branches towards the end of the tree, i.e., the leaves.
For example, let's think of the organization chart in a company as a tree where it assumes a boss or manager has one or more subordinates. If you need to look up your name,
1) the depth-first search will start from the CEO, which is the root of your org tree.
2) Then pick up one of those under him/her to check if the person is you or not.
3) If not, we keep doing the same until reaching to the person who does not have any associates, which we call John in this example.
4) Then, just go up one layer i.e., John's boss and look for one of his or her colleagues, Mary. If she has subordinates, we will investigate their names one by one.
Repeat the above steps from 2) to 4) until we find the target name.
This depth-first search can be useful and powerful when you would like to find the following things:
- Find the path of a maze = I believe when you actually try to solve a maze, people typically do the depth-first search.
- Find the connected cities by trains or airplane
Word of the day: arduous, hard to accomplish