Depth-First Search (DFS) for Graphs

Description
Depth-First Search (DFS) is an algorithm used to traverse or search a graph (or tree). Its core idea is to explore a branch of the graph as deeply as possible until its end, then backtrack to the previous node to continue exploring unvisited branches. DFS is commonly used to solve problems like path finding, connectivity detection, and topological sorting.

Step-by-Step Explanation

1. Basic Concepts

   • A graph consists of vertices (nodes) and edges (lines connecting nodes).
   • DFS needs to track whether each vertex has been visited (typically marked with a boolean array).
   • The algorithm follows a "last-in, first-out" recursive or stack structure, prioritizing deep exploration of a branch.

2. Algorithm Procedure
   Step 1: Initialization

   • Create a visited marking array visited[], initialized to false (meaning all vertices are unvisited).
   • Select a starting vertex in the graph.

   Step 2: Explore from the Starting Point

   • Visit the current vertex (e.g., output its value) and mark it as visited.
   • Check all adjacent vertices of the current vertex (i.e., vertices directly connected by edges):
     • If an adjacent vertex is unvisited, recursively perform DFS on that adjacent vertex.
     • If the adjacent vertex is already visited, skip it.

   Step 3: Backtracking and Termination

   • After all adjacent vertices of the current vertex have been visited, backtrack to the previous vertex.
   • The algorithm ends when all vertices have been visited.

3. Example (Undirected Graph)
   Assume the graph is as follows (vertices 0, 1, 2, 3; edges: 0-1, 0-2, 1-3):

     0
    / \
   1   2
   |
   3
   

   Execution Process:

   • Start from vertex 0: mark 0 as visited.
   • Check adjacent vertices of 0 (1 and 2), visit 1 first in order: mark 1 as visited.
   • Check adjacent vertices of 1 (0 and 3), skip already visited 0, visit 3: mark 3 as visited.
   • 3 has no unvisited adjacent vertices, backtrack to 1; all adjacent vertices of 1 have been visited, backtrack to 0.
   • The other adjacent vertex of 0, 2, is unvisited, visit 2: mark 2 as visited.
   • 2 has no unvisited adjacent vertices, backtrack to 0. Algorithm ends.
     Traversal Order: 0 → 1 → 3 → 2.

4. Code Implementation (Recursive Version)

   def dfs(graph, node, visited):
       visited[node] = True  # Mark current node as visited
       print(node)  # Process node (e.g., output)
       for neighbor in graph[node]:  # Iterate through adjacent nodes
           if not visited[neighbor]:
               dfs(graph, neighbor, visited)  # Recursively visit
   
   # Adjacency list representation of the example graph
   graph = {
       0: [1, 2],
       1: [0, 3],
       2: [0],
       3: [1]
   }
   visited = [False] * len(graph)
   dfs(graph, 0, visited)
   

5. Key Points

   • Time Complexity: O(V+E) (V is the number of vertices, E is the number of edges).
   • Space Complexity: O(V) (space for the recursion stack or explicit stack).
   • If the graph is not connected, DFS must be called for each unvisited vertex (to avoid missing any).
   • A non-recursive version requires an explicit stack to simulate the recursive process (pushing nodes onto the stack and processing in a loop).

Summary
DFS implements "depth-first" exploration via recursion or a stack, suitable for scenarios like detecting graph connectivity, finding paths, and solving backtracking problems. Understanding its backtracking mechanism and the order of traversing adjacent vertices is key to mastering this algorithm.