Depth-First Search (DFS)

Depth-First Search (DFS)

Welcome to Depth-First Search (DFS), another fundamental graph traversal algorithm. Unlike BFS which explores layer by layer, DFS dives as deep as possible down one path before backtracking. This "deep-first" approach makes it a powerful tool for a variety of graph analyses, including cycle detection, topological sorting, and finding connected components.

---

1. The DFS Algorithm: A Deep Dive

DFS explores a graph by starting at a source vertex and following a path until it reaches a dead end. It then backtracks to the last vertex with an unexplored neighbor and continues down that new path. This process is repeated until all reachable vertices have been visited.

This "diving" and "backtracking" behavior can be naturally implemented using a Stack (for an iterative approach) or through Recursion (which uses the call stack).

---

2. Core DFS Process (Recursive)

The recursive approach is often more intuitive to write and understand.

1. Initialization:

   • Create a visited set or array to keep track of visited vertices.
   • Define a recursive function, let's call it go(u).

2. Recursive Function go(u):

   • Mark the current vertex u as visited.
   • Process u (e.g., add it to a traversal list).
   • For each neighbor v of u:
     • If v has not been visited, recursively call go(v).

3. Start Traversal:

   • Call go(start_node) for your starting vertex.
   • If the graph might be disconnected, you may need a loop to call go for each vertex to ensure all components are visited.

---

3. Core DFS Process (Iterative)

The iterative approach uses an explicit stack and avoids potential recursion depth limits.

1. Initialization:

   • Create a stack and push the starting vertex onto it.
   • Create a visited set or array.

2. Traversal Loop:

   • While the stack is not empty:
     • Pop: Remove the vertex at the top of the stack. Let's call it u.
     • If u has not been visited:
       • Mark u as visited.
       • Process u.
       • For each neighbor v of u:
         • If v has not been visited, push v onto the stack.

---

4. DFS Applications

DFS's ability to explore paths to their conclusion makes it suitable for several important problems.

4.1. Cycle Detection

DFS can be used to determine if a graph contains a cycle.

• Undirected Graphs: While performing DFS, if we encounter a visited vertex that is not the immediate parent of the current vertex, we have found a cycle.

• Directed Graphs: We need to keep track of the vertices currently in the recursion stack (the path we are exploring). If we encounter a vertex that is already in the current recursion stack, we have found a back edge, which indicates a cycle.

  function hasCycleDirected(adj) {
    const N = adj.length;
    const visited = new Set();
    const recursionStack = new Set();
  
    function detect(u) {
      visited.add(u);
      recursionStack.add(u);
  
      for (const v of adj[u]) {
        if (!visited.has(v)) {
          if (detect(v)) return true;
        } else if (recursionStack.has(v)) {
          return true; // Cycle detected
        }
      }
  
      recursionStack.delete(u);
      return false;
    }
  
    for (let i = 0; i < N; i++) {
      if (!visited.has(i)) {
        if (detect(i)) return true;
      }
    }
    return false;
  }
  

4.2. Topological Sort

For a Directed Acyclic Graph (DAG), a topological sort is a linear ordering of its vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.

• Concept: We can use DFS to achieve this. After visiting all the descendants of a vertex u, we add u to the front of a list. The final list will be a topologically sorted order.

  function topologicalSort(adj) {
    const N = adj.length;
    const visited = new Set();
    const result = [];
  
    function visit(u) {
      visited.add(u);
      for (const v of adj[u]) {
        if (!visited.has(v)) {
          visit(v);
        }
      }
      result.unshift(u); // Add to the front
    }
  
    for (let i = 0; i < N; i++) {
      if (!visited.has(i)) {
        visit(i);
      }
    }
    return result;
  }
  

---

5. Complexity

• Time Complexity: O(N + M), where N is the number of vertices and M is the number of edges, because each vertex and edge is visited once.
• Space Complexity: O(N) for the visited set and the recursion stack (or explicit stack) in the worst case (for a path graph).

---

Key Takeaway: DFS is a "deep-first" traversal algorithm that uses a stack (often the call stack via recursion). Its path-finding nature makes it excellent for detecting cycles, performing topological sorts, and exploring the connectivity of a graph, all with a time complexity of O(N + M).