21.1.5. DFS Numbering Technique

Depth first search (DFS) explores connectivity differently than breadth first search (BFS). Instead of exploring all vertices level by level, DFS dives into one vertex and explores as far as possible along its branch before backtracking.

DFS begins at a starting vertex (say vertex 'i') and visits the first unvisited neighbor (let's call it 'j'). It explores 'j' completely, then backtracks to 'i' when 'j' has no more unexplored neighbors. This process repeats until all vertices are explored, leading to a depth-first traversal of the graph.

Imagine you are exploring a cave with multiple tunnels. Instead of checking all tunnels at the entrance (like BFS), you choose one tunnel and go as deep as you can. Once you reach a dead end, you come back to the point where you can explore another tunnel. This is how DFS works by exploring deeply before coming back.

To execute the algorithm, start at a specified vertex (4 in this case), mark it visited, and explore its unvisited neighbors. When you reach a point with no unvisited neighbors, backtrack to the most recent vertex with unexplored options.

For example, starting from vertex 4, it has neighbors like 1, 3, 5, and 6. You mark 1 as visited, suspend vertex 4 on a stack, and move on to explore further. If you encounter a dead end, you utilize the stack to return to the last suspended vertex and explore its other neighbors. This process continues until all vertices have either been visited or accounted for.

Think of it like solving a maze: when you reach a wall (dead end), you backtrack to the last turn (suspended vertex) and try a different path until you've explored every option in the maze.

DFS can be efficiently implemented using recursion. Instead of maintaining an explicit stack, each recursive call simulates the stack behavior implicitly.

When you call DFS on a vertex, it checks all connected vertices recursively. This way, you don't need a separate data structure to keep track of visited nodes and vertices, as the function call stack manages it efficiently.

Imagine telling a story to a friend where each part of the story leads naturally into the next. Instead of writing it all down, you just 'tell' as you go, returning to previous points as needed, which reflects the recursive nature of DFS.

The complexity of depth first search is O(V + E) (where V is the number of vertices and E is the number of edges) when using adjacency lists, making it efficient. However, using adjacency matrices results in O(V^2).

In DFS, every vertex is visited once, and thus each vertex contributes to the overall complexity. When using adjacency lists, you only visit relevant edges connected to the vertex, making it potentially faster than minimal operations (O(V + E)). In contrast, adjacency matrices require scanning through all potential connections, leading to higher time complexity.

Consider looking at a map: using a detailed layout (adjacency list) allows you to see just the roads you're interested in, while trying to check every possible route (adjacency matrix) is time-consuming and inefficient.

DFS assigns two values to each vertex: the pre-order and post-order numbers. As you visit a vertex, you record its pre-number, increment the counter, and subsequently note its post-number when exiting.

The pre-number is noted as you enter the vertex, and the post-number is recorded upon leaving. This technique helps in understanding the structure of a graph, like identifying cycles or cut vertices by analyzing the timing of visits.

Think of this numbering method as checking in and out of a library. When you enter, you mark the time (pre-number), and when you leave, you mark the time again (post-number). This data can then help analyze traffic patterns in the library.

Using pre-order and post-order numbers, you can determine properties of the graph, such as cycles and cut vertices, which contribute to understanding its structure.

For example, when analyzing a graph with these numbers, if you find that a vertex can disconnect a path (cut vertex), it signifies that this vertex is critical for connectivity. Such metrics enable efficient algorithms for problems in network reliability and connectivity.

Imagine a city's network of roads: identifying a road that, if blocked, would isolate parts of the city. This road would be a 'cut vertex', and knowing its importance can help in city planning and emergency responses.

--