21.1.4. Complexity of Depth First Search

DFS is a strategy that explores a graph by traversing as deep as possible along each branch before backtracking. It starts with a vertex and explores its neighbors, suspending the current vertex execution until all neighbors have been explored.

In DFS, we begin at a starting vertex and explore the first unvisited neighbor. If we reach a vertex with no unvisited neighbors, we backtrack to the last vertex that has unexplored neighbors. This continues until all vertices accessible from the starting vertex are visited. By using a stack (either explicit or recursive), we keep track of the vertices that need to be explored. This means that DFS explores deeper down into the graph before returning back up to check for other paths.

Imagine you are exploring a cave system. You enter the main tunnel and decide to follow the first path you encounter. If that path leads to a dead end, you backtrack to the last junction and try another route. This way, you explore as deeply as possible before coming back to see if there are other paths to take.

Each vertex is visited once, resulting in O(n) time, where n is the number of vertices. When using an adjacency list, the time complexity becomes O(m + n), where m is the number of edges.

In DFS, for each vertex visited, we look at its neighbors. If using an adjacency matrix, this may require checking through all vertices (leading to O(n^2)). However, with an adjacency list, we only check direct connections. Since each edge is reviewed twice (once from each vertex), the total time complexity is linear with respect to both the number of vertices and edges, resulting in O(m + n). This is efficient compared to other graph algorithms that may operate in quadratic time.

Think of a city map where intersections are vertices and roads are edges. If you need to navigate this map, checking each intersection and its direct road connections (with an adjacency list) is far quicker than checking every possible road for each intersection (as would happen in an adjacency matrix).

While DFS may not find the shortest paths like Breadth First Search does, it uncovers unique structural features of graphs through the order of exploration.

DFS prioritizes depth over breadth, which can lead to longer paths between vertices, as it isn't designed to find the shortest route. However, this method reveals significant insights about the graph’s structure, such as component connectivity and cycles, that are not apparent in BFS. By recording how one vertex leads to another during the traversal, we can infer many properties of the graph.

Consider a treasure map: using DFS might mean you start digging in a cave that extends deep but leads to a dead end, whereas BFS is like systematically checking each room in a house to ensure you find the quickest way to the treasure. While DFS might miss the shortest route, it uncovers hidden chambers that BFS could overlook.

DFS can contribute valuable information by recording two numbers for each vertex—the time it was entered and the time it was exited, known as pre and post numbers.

To maintain the exploration order and timing, we initialize a counter at the start of DFS. As we visit each vertex, we assign its pre number using the current counter value and then increment it. Upon exiting a vertex, we assign its post number. These numbers allow us to analyze graph properties, such as identifying cycles or critical vertices, and reveal the order in which vertices were accessed.

Imagine a classroom activity where students enter and leave at different times. If you note the time each student enters and exits, you can identify who was present at any given moment and observe if any students interrupted each other. This concept parallels how pre and post numbers help us track the flow of exploration in graphs.

Using the pre and post numbers recorded during DFS, we can assess various properties of a graph, such as detecting cycles and identifying cut vertices.

By leveraging the pre and post values gathered during the DFS, we can derive useful insights about the graph structure. This includes determining if a cycle exists (where a vertex is revisited within an exploration path) or identifying cut vertices, which, when removed, disconnects portions of the graph. This dimensional analysis proves the versatility of DFS beyond simple traversal.

Think of removing roads in a city to see which neighborhoods become isolated. Each time you remove a road (cut vertex), you can observe how the city's connectivity changes. The pre and post numbers from DFS provide a systematic method to analyze and visualize these connectivity properties of the graph.

--