21.1. Design and Analysis of Algorithms

So, we have seen how to explore connectivity using breadth first search. So, now let us look at the other strategy which is commonly used called depth first search. In depth first search, instead of exploring all vertices level by level, each time we explore a new vertex, we immediately explore its steps.

Depth First Search (DFS) is a strategy for exploring graphs by visiting a vertex and then exploring as far down that vertex's neighbors as possible before backtracking. Unlike Breadth First Search (BFS), which explores vertices layer by layer, DFS delves deep into one path before considering other options. This method is useful for tasks where you need to probe all possibilities, such as solving puzzles or finding mazes.

Imagine you are in a library (the graph) looking for a specific book. With DFS, you might start at a shelf (a vertex), check each book (neighbor) on that shelf, and go to the next shelf that has books you're interested in. You continue picking books to examine deeply until you either find the book or hit a dead-end (all neighbors have been checked). Then you return to the last shelf you visited and check the next shelf.

We start at vertex 'i' and visit the first neighbor 'j' from 'i' which is not yet explored. We suspend the exploration of 'i' and explore 'j' instead. This continues until there is nothing new to explore; then we backtrack.

The process of DFS involves starting from a chosen vertex, marking it as visited, and then recursively visiting unvisited neighbors. If you can't find any unvisited neighbors (when you hit a dead-end), you backtrack to the most recent vertex with unvisited neighbors to explore. This backtracking mechanism is instrumental in ensuring that all vertices are ultimately checked.

Think of this like exploring a cave system. You enter a passage (vertex), and you follow it as far as it goes. If you reach a dead-end (no neighbors to visit), you retrace your steps back to where you turned, then explore the next passage. This method ensures you've explored as much as possible down each route before moving on.

The vertices that are pending exploration are kept in a stack. As you go deeper into the graph, you build up this stack. When you reach a dead-end, you can backtrack by using this stack to revisit earlier vertices.

In DFS, the stack is vital as it keeps track of the vertices you're visiting and those still to be explored. When using a recursive implementation, this stack is managed automatically by the function calls, providing an efficient way to remember your path without explicitly maintaining it. Each time you explore a new vertex, it is added to the stack, and you pop off vertices when backtracking.

Picture a game of Jenga. Each block you stack represents a vertex you visit. If you make a wrong move (reach a dead-end), instead of continuing to balance, you remove blocks carefully until you can find a new placement—a representation of backtracking through earlier visited vertices to find new paths.

What we did explicitly with a stack can be done more cleverly with recursion. Whenever we visit a new vertex 'j', we call DFS of 'j' and suspend DFS of the current vertex 'i'.

Recursion allows us to simplify the DFS implementation. Instead of maintaining a stack explicitly, the programming language's call stack will manage the vertices for us. Each call to the DFS function marks a vertex as visited and recursively calls DFS for each unvisited neighbor, inherently maintaining state without requiring additional data structures.

Imagine telling a story where each time you introduce a character, you dive into their storyline (a call to DFS). You can pause each storyline to explore the next character (recursive call), and when you reach an end (the story concludes), you return to the previous character to see if they have unresolved subplots to explore further (backtracking).

Each vertex is marked and explored exactly once, leading to approximately n calls. If we use an adjacency list, the overall time complexity is O(m + n), which is linear in the size of the graph.

The complexity analysis of DFS reveals it is efficient. Each vertex will be visited once, and if we are using an adjacency list, we only traverse the edges that are present, leading to an overall time complexity of O(m + n), where 'm' is the number of edges and 'n' is the number of vertices. This makes DFS very scalable for large graphs.

Think of a road trip where you visit each city (vertex) and only travel along connected highways (edges). You only count the roads you actually travel on, ensuring that your efficiency mirrors the connected paths of your journey—no time spent on long detours.

One critical difference between DFS and BFS is that the paths discovered by BFS are not necessarily the shortest paths. DFS can explore deeper and may find longer paths while uncovering other useful information about the graph.

In contrast to BFS, which explores the shortest path in a level-order fashion, DFS dives into the depths of paths. While this can yield longer routes in some cases, it is advantageous for discovering structural properties of the graph not visible to BFS. DFS tends to be more insightful for certain applications despite its potential to not find the shortest path.

Consider two different methods of finding a route in a city. BFS is like a map showing all major roads and intersections, ensuring the shortest route, while DFS is like exploring the city's back alleys—you might not take the shortest route but will discover hidden gems and essential information about the city layout that BFS would miss.

By maintaining a pre and post counter for each vertex during DFS, we can extract valuable information about the graph, such as identifying cycles or cut vertices.

Assigning pre and post numbers during the DFS traversal gives additional insights. Pre numbers denote when we first discover a vertex, while post numbers mark when we finish exploring its neighbors. This information helps us analyze graph properties. For example, if a post number of a vertex is less than that of its neighbors, it could indicate a back edge, suggesting a cycle.

Think of visiting a series of art galleries. As you enter (pre number) and exit (post number) each gallery, you take note not just of what you've seen but also of the connections between them. This information allows you to compile a rich narrative of your experience, useful for identifying trends (like recurring artists or styles) that would inform future visits.

DFS is not just used for exploring paths in graphs but also for finding cycles, cut vertices, and understanding the structure of a graph.

The versatility of DFS allows it not only to navigate graphs but also to extract critical structural information. By analyzing the order of vertex visits and their pre/post counts, we can determine critical points in a graph that contribute to understanding its architecture, discovering cycles which indicate flaws or complexities, and identifying vertices whose removal disconnects the graph.

In a network of friends, DFS can help determine key individuals. If removing a person disconnects several groups (cut vertex), this indicates their significance in maintaining social connections. Similarly, if a network of friendships forms a closed loop (cycle), knowing this helps manage relationships effectively as you understand the full dynamics involved.

--