21.1.1. Depth First Search (DFS)

Depth first search (DFS) is an algorithm for exploring graphs. Unlike breadth first search, which explores all vertices level by level, DFS explores each vertex's neighbors immediately. Starting at a vertex, we visit the first unvisited neighbor, suspending the execution at the current vertex until all its neighbors are explored.

DFS begins at a starting vertex and explores as deep as possible along each branch before backtracking. When a vertex has unvisited neighbors, DFS explores these neighbors, marking the current vertex as suspended. If a dead-end is reached, the algorithm backtracks to the nearest vertex that has unexplored neighbors, continuing the same process until all vertices have been visited.

Imagine you are in a library looking for a specific book in a section. You go down each aisle (the depth) and check each shelf (the neighbors) for the book. If you find one section has no books, you backtrack to the previous aisle and explore a different section until you either find the book or check all the aisles.

In DFS, all the suspended vertices are kept in a stack. As you go deeper into the graph, this stack grows. When you reach a dead end, you backtrack using the stack to process earlier suspended vertices.

The stack helps track the path taken during the DFS. Each time a vertex is visited, it gets pushed onto the stack. When there are no more unvisited neighbors, the algorithm pops the vertex off the stack to return to the last suspended vertex, allowing you to continue exploring from there. This technique efficiently manages the state of the algorithm using the principle of Last In, First Out (LIFO).

Think of a person climbing a mountain and using a series of ropes (the stack) to ascend different ridges. When they cannot go higher, they return along the ropes they used until they can find a new route to explore. Each point where they paused is like a suspended vertex in DFS.

When executing DFS on a graph, we start with a designated vertex, mark it as visited, and move through its neighbors recursively. For example, starting from vertex 4, we explore its neighbors: 1, then move to 2, 3, etc., marking each as visited until we return to finish our exploration.

In practical terms, you mark the starting vertex as visited and systematically explore each unvisited neighbor. The algorithm tracks which vertices have been visited to prevent cycles and ensure all vertices are explored efficiently. As we demonstrate on a sample graph, we can mark the sequence in which we visit vertices and backtrack when necessary.

Picture a maze: you start at the entrance (vertex), explore each passageway (neighbors) blindly until you reach a wall (dead end), then retrace your steps back to previous junctions until every path has been explored.

DFS can also be implemented recursively. Each time a new vertex is visited, the DFS function is called recursively on that vertex, eliminating the need for an explicit stack.

Recursion simplifies the DFS implementation because each function call is akin to pushing a vertex onto a stack. When a vertex is explored, a function call is made for its unvisited neighbors, and the call stack takes care of backtracking automatically, leading to a cleaner and more intuitive implementation.

Imagine a nesting doll scenario: you open one doll (visit a vertex) and find another inside (call the function recursively) until you reach the innermost doll. Once you reach the smallest doll (dead end), you put each doll back on top as you exit (backtrack).

The complexity of DFS is determined by the number of vertices and edges in the graph. Each vertex is visited once, leading to O(n) calls, and checking all neighbors amounts to O(n) for adjacency matrices, resulting in O(n^2) time. With adjacency lists, it yields a linear time complexity of O(m + n), where m is edges and n is vertices.

DFS time complexity involves two factors: the number of vertices (n) and the connections (edges, m) between them. For dense graphs represented as matrices, each neighbor must be checked for each vertex, making it slower (O(n^2)). However, for sparse graphs represented using lists, we only examine existing edges, leading to better performance (O(m + n)). It’s vital to use the appropriate representation based on the graph structure to optimize performance.

Consider moving through a busy city (dense graph) where you'd take longer routes, and now imagine moving through a small town (sparse graph) where each street is quick to traverse. In the town, you spend less time checking each intersection than in the busy city with countless traffic signals.

--