What is depth first search?
Depth first search (DFS) is an algorithm used to traverse a graph that contains a set of nodes and edges. The main objective is to perform a search of data by traversing the vertices connected by edges. It differs from its sister algorithm Breadth first search (BFS) because it traverses the vertices down to the lowest level first instead of traversing the vertices on the same height [1].
Note that in figure 1 the algorithm starts at vertex a, travels from a to c to e, a to b to d to f. As discussed in my article on BFS, Graphs can be directed or undirected so take note of the directions of the arrows.
How is this relevant to my life?
As discussed in my article about BFS, DFS is also used every day by the average Google user or other search platform. This algorithm also shows up in initial interviews or code challenges during the application process. As mentioned in my other article this post will show explicit demonstrations of the algorithm implemented iteratively and then recursively in multiple languages. Hiring managers love these types of questions because it forces the candidate to explain all the steps and it is hard to fake this type of understanding.
Real Examples
Iterative implementation
Recursive implementation
References
[1] Anonymous, “Depth First Search or DFS for a Graph”, 2023, geeksforgeeks.org
Retrieved from Depth First Search or DFS for a Graph – GeeksforGeeks on July 4th, 2023.