Exploring the Depths: An Introduction to DFS and Its Practical Applications
n this post, after discussing BFS in my previous post, I’ll provide a brief introduction to DFS along with a few examples to illustrate its practical applications.
As we have seen, DFS and BFS are two distinct approaches used to traverse data structure trees. DFS starts from a specific vertex known as the “root” and explores as far as possible along each branch before backtracking. This depth-first exploration gives the algorithm its name.
So, what is DFS good for? Well, one notable application of DFS is determining whether a graph contains a cycle. By running DFS on the graph and tracking visited vertices, we can identify if there is a back edge, indicating the presence of a circle.
Let’s look at a practical problem that will help us understand the benefits of DFS. Imagine that you are the proud owner of a beautiful forest park, and you are trying to make the park more popular. You want to encourage families and people to start running in the park or go on a trip in it. But the park isn’t that big, so how can you encourage people to run 5K or even 10K in a park that is much smaller? Make them run in circles, of course! So, you want to find a circular route in the park so you can advertise it as a park with a running route. How can you find it? Here, DFS comes to help! If we consider every intersection between 2 routes in the park as a vertex, with information about the distance from the last intersection and a field called ‘visited,’ and create a graph from all the vertices, we can run DFS on that graph and find a circle. Let’s see what the code would look like.”
So what did we do here? In this implementation, we have adapted the traditional DFS algorithm to find circles in our park’s running routes. Let’s break down how it works.
We start by traversing each vertex in the unvisited graph and mark it as visited, indicating that we have explored this vertex. We also add it to the current path.
Next, we explore each neighbor of the vertex and check if it has been visited before. If it hasn’t, we go deeper into the graph by recursively calling the DFS function on that neighbor.
If the neighbor has been visited, it means we have found a circle. However, we want to avoid including circles that simply go back and forth between two vertices. To ensure this, we check if the neighbor is not the parent vertex (the vertex we came from). If it is not the parent, it means we have a circle from the neighbor back to the current vertex.
In such cases, we add this circle to the circle’s list, which keeps track of all the circles we find in the park’s running routes.
Additionally, at the end of the DFS traversal, we remove the current node from the path list and mark this node’s “visited” field as false. This step ensures that the correct path is maintained when backtracking in the graph. As we explore different paths, we add vertices to the path list to keep track of the current route. However, once we finish exploring all the adjacent vertices of a particular node, we need to remove that node from the path as we backtrack to the previous node. By removing the current node, we ensure that the path list accurately represents the path from the starting vertex to the current vertex during the traversal.
Furthermore, we set the visited flag of each node to false at the end of the DFS traversal. This step is crucial when we want to run the algorithm multiple times or perform other graph operations. By resetting the visited flag, we ensure that all vertices are considered unvisited for subsequent runs of the algorithm. This allows us to find new cycles or paths when running the algorithm again or perform different graph-related tasks.
By following this approach, we can systematically identify and record a circle in the graph representing our park’s running routes. So now, if we want to know the length of the circle, all we need is to sum the node distance information field.
This was just one practical example of the usefulness of DFS. Another nice thing about DFS is that with a few changes, we can enhance the DFS algorithm and keep track of additional information, such as the order of vertex visits. We can assign pre-visit and post-visit numbers to each vertex. These numbers indicate when a vertex enters and exits the recursion of DFS, providing useful data for various graph algorithms.
For each vertex in the graph, we can introduce three fields: visited, pre, and post. Initially, all vertices are marked as unvisited. We also introduce a variable called time, which keeps track of the current visitation time.
When we visit a vertex during DFS, we first mark it as visited and assign its pre-value as the current time. We then increment the time by one to prepare for the next vertex. Next, we explore the neighboring vertices of the current vertex recursively, following the DFS approach.
As we backtrack from the recursion, when there are no more unvisited vertices to explore from the current vertex, we assign its post value as the current time. This post value represents the point at which we exit the recursion stack for that vertex.
By using this approach, we can obtain a clear picture of the order in which vertices were visited during the DFS traversal. The pre-visit and post-visit numbers provide valuable information that can be utilized for further analysis or algorithms involving graph exploration.
The time complexity of DFS is O(V+E), where V represents the number of vertices and E represents the number of edges in the tree.
This is just one of the many uses DFS has to offer us. Feel free to comment below on other DFS uses!
LinkedIn account — https://www.linkedin.com/in/amitai-turkel
github account — https://github.com/amitaiturkel
