Traversing Graphs with DFS

1. Understanding Graph DFS

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It's commonly used for pathfinding, cycle detection, and topological sorting.

Property	Description	Notes
Time Complexity	O(V + E)	V = vertices, E = edges
Space Complexity	O(V)	For recursion stack and visited set
Traversal Order	Stack-based (LIFO)	Can be implemented recursively or iteratively

Example: Basic DFS Implementation (Recursive)

function dfsRecursive(graph, startNode) {
  const visited = new Set();
  const result = [];

  function dfs(node) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);

    for (const neighbor of graph[node] || []) {
      dfs(neighbor);
    }
  }

  dfs(startNode);
  return result;
}

// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['G'],
  'F': [],
  'G': []
};

console.log(dfsRecursive(graph, 'A')); // ['A', 'B', 'D', 'E', 'G', 'C', 'F']

Example: DFS with Path Tracking

function dfsWithPath(graph, startNode) {
  const visited = new Set();
  const path = [];

  function dfs(node, currentPath) {
    if (visited.has(node)) return;
    visited.add(node);
    currentPath.push(node);

    for (const neighbor of graph[node] || []) {
      dfs(neighbor, currentPath);
    }

    path.push([...currentPath]);
    currentPath.pop();
  }

  dfs(startNode, []);
  return path;
}

// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['G'],
  'F': [],
  'G': []
};

console.log(dfsWithPath(graph, 'A'));
// [['A', 'B', 'D'], ['A', 'B', 'E', 'G'], ['A', 'C', 'F']]

Note: DFS can be used to detect cycles in directed graphs by tracking the recursion stack or using a "color" marking system (white, gray, black).

2. Implementing Recursive DFS

Property	Description	Example
function dfs(node, visited)	Recursive depth-first search function	`dfs(node, visited)`
visited	Set to track visited nodes	`new Set()`

Example: Recursive DFS Implementation

function dfs(node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node.value);

  for (let neighbor of node.neighbors) {
    dfs(neighbor, visited);
  }
}

3. Implementing Iterative DFS

Component	Description	Code Example
Stack	Used to simulate the call stack in recursive DFS	`const stack = [startNode];`
Visited Set	Tracks visited nodes to prevent cycles	`const visited = new Set();`
Process Node	Function to handle node processing logic	`function processNode(node) { console.log(node); }`

Example: Iterative DFS Implementation

function iterativeDFS(graph, start) {
  const stack = [start];
  const visited = new Set();
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop();
    
    if (!visited.has(node)) {
      visited.add(node);
      result.push(node);
      
      // Push neighbors to stack in reverse order for consistent traversal
      const neighbors = graph[node] || [];
      for (let i = neighbors.length - 1; i >= 0; i--) {
        stack.push(neighbors[i]);
      }
    }
  }

  return result;
}

Note: The order of neighbors pushed to the stack affects traversal order. Pushing in reverse ensures left-to-right processing.

4. Detecting Cycle in Undirected Graph

Property	Description	Notes
Algorithm	DFS-based cycle detection	Uses recursion and visited tracking
Time Complexity	O(V + E)	V = vertices, E = edges
Space Complexity	O(V)	For visited array and recursion stack

Example: Detecting Cycle in Undirected Graph

function hasCycle(graph) {
  const visited = new Array(graph.length).fill(false);
  const recStack = new Array(graph.length).fill(false);

  for (let i = 0; i < graph.length; i++) {
    if (!visited[i] && isCyclicUtil(graph, i, visited, recStack)) {
      return true;
    }
  }

  return false;
}

function isCyclicUtil(graph, node, visited, recStack) {
  visited[node] = true;
  recStack[node] = true;

  for (let neighbor of graph[node]) {
    if (!visited[neighbor]) {
      if (isCyclicUtil(graph, neighbor, visited, recStack)) {
        return true;
      }
    } else if (recStack[neighbor]) {
      return true;
    }
  }

  recStack[node] = false;
  return false;
}

// Example usage:
const graph = [
  [1, 2],
  [0, 3],
  [0, 3],
  [1, 2]
];

console.log(hasCycle(graph)); // true

Note: The recStack array is used to track the recursion stack during DFS traversal. If a node is encountered that is already in the recursion stack, it indicates a cycle.

5. Detecting Cycle in Directed Graph

Property	Description	Notes
Algorithm	DFS-based cycle detection in directed graph	Uses recursion stack to track visited nodes
Time Complexity	O(V + E)	V = vertices, E = edges
Space Complexity	O(V)	For recursion stack and visited array

Example: Detecting Cycle in Directed Graph

function hasCycle(graph) {
    const visited = new Array(graph.length).fill(false);
    const recStack = new Array(graph.length).fill(false);

    for (let i = 0; i < graph.length; i++) {
        if (!visited[i] && isCyclicUtil(graph, i, visited, recStack))
            return true;
    }
    return false;
}

function isCyclicUtil(graph, node, visited, recStack) {
    visited[node] = true;
    recStack[node] = true;

    for (let neighbor of graph[node]) {
        if (!visited[neighbor] && isCyclicUtil(graph, neighbor, visited, recStack))
            return true;
        else if (recStack[neighbor])
            return true;
    }

    recStack[node] = false;
    return false;
}

// Example usage:
const graph = [
    [1],       // Node 0 → 1
    [2],       // Node 1 → 2
    [0],       // Node 2 → 0 (cycle)
];

console.log(hasCycle(graph)); // true

Note: The recursion stack (recStack) is used to keep track of the current DFS path. If we encounter a node that's already in the recursion stack, it means there is a back edge and thus a cycle.

6. Finding Connected Components

Property	Description	Usage
visited	Tracks nodes already visited during traversal	Prevents revisiting nodes in connected component
component	Stores nodes in current connected component	Groups all nodes in same component together

Example: Finding Connected Components in Undirected Graph

const graph = {
  'A': ['B', 'C'],
  'B': ['A'],
  'C': ['A'],
  'D': ['E'],
  'E': ['D']
};

function findConnectedComponents(graph) {
  const visited = new Set();
  const components = [];

  for (const node in graph) {
    if (!visited.has(node)) {
      const component = [];
      dfs(node, graph, visited, component);
      components.push(component);
    }
  }

  return components;
}

function dfs(node, graph, visited, component) {
  visited.add(node);
  component.push(node);

  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, graph, visited, component);
    }
  }
}

console.log(findConnectedComponents(graph));
// Output: [['A', 'B', 'C'], ['D', 'E']]

Note: For directed graphs, connected components are called strongly connected components (SCCs). Use Kosaraju's or Tarjan's algorithm for SCCs.

7. Finding Strongly Connected Components

Strongly Connected Components (SCCs) are maximal subgraphs where every vertex is reachable from every other vertex within the component.

Property	Description	Notes
Kosaraju's Algorithm	Uses two DFS traversals to find SCCs.	First DFS on reversed graph, second on original graph.
Tarjan's Algorithm	Uses a single DFS with a stack to find SCCs.	Efficient, O(V + E) time complexity.

Example: Kosaraju's Algorithm Implementation

function kosaraju(graph) {
  const visited = new Set();
  const stack = [];
  const sccs = [];

  // First DFS to fill the stack
  function dfs1(node) {
    visited.add(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) dfs1(neighbor);
    }
    stack.push(node);
  }

  // Reverse graph
  const reverseGraph = {};
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      if (!reverseGraph[neighbor]) reverseGraph[neighbor] = [];
      reverseGraph[neighbor].push(node);
    }
  }

  // Fill stack with first DFS
  for (const node in graph) {
    if (!visited.has(node)) dfs1(node);
  }

  // Second DFS on reversed graph
  visited.clear();
  function dfs2(node, component) {
    visited.add(node);
    component.push(node);
    for (const neighbor of reverseGraph[node] || []) {
      if (!visited.has(neighbor)) dfs2(neighbor, component);
    }
  }

  // Extract SCCs
  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited.has(node)) {
      const component = [];
      dfs2(node, component);
      sccs.push(component);
    }
  }

  return sccs;
}

Example: Tarjan's Algorithm Implementation

function tarjan(graph) {
  const index = {};
  const lowLink = {};
  const stack = [];
  const onStack = new Set();
  const sccs = [];
  let currentIndex = 0;

  function strongconnect(node) {
    index[node] = currentIndex;
    lowLink[node] = currentIndex;
    currentIndex++;
    stack.push(node);
    onStack.add(node);

    for (const neighbor of graph[node] || []) {
      if (index[neighbor] === undefined) {
        strongconnect(neighbor);
        lowLink[node] = Math.min(lowLink[node], lowLink[neighbor]);
      } else if (onStack.has(neighbor)) {
        lowLink[node] = Math.min(lowLink[node], index[neighbor]);
      }
    }

    if (lowLink[node] === index[node]) {
      const component = [];
      let w;
      do {
        w = stack.pop();
        onStack.delete(w);
        component.push(w);
      } while (w !== node);
      sccs.push(component);
    }
  }

  for (const node in graph) {
    if (index[node] === undefined) {
      strongconnect(node);
    }
  }

  return sccs;
}

Note: Kosaraju's algorithm is simpler to understand but requires two graph traversals. Tarjan's algorithm is more efficient with one traversal and uses a stack to track components.

8. Implementing DFS Path Finding

Property	Description	Example
dfsPathFinding(graph, start, end)	Finds a path from start to end using DFS	`dfsPathFinding(graph, 'A', 'D')`

Example: Basic DFS Path Finding

function dfsPathFinding(graph, start, end) {
  const visited = new Set();
  const path = [];

  function dfs(node) {
    if (node === end) return true;
    visited.add(node);
    path.push(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) return true;
      }
    }

    path.pop();
    return false;
  }

  const found = dfs(start);
  return found ? path : null;
}

const graph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': [],
  'E': []
};

console.log(dfsPathFinding(graph, 'A', 'D')); // ['A', 'B', 'D']

Note: This implementation returns the first path found, not necessarily the shortest one.

9. Finding All Paths

Property	Description	Example
Algorithm	Finds all paths from source to target in a graph using DFS	`findAllPaths(graph, start, end)`
Time Complexity	O(2^N * N) where N is the number of nodes	Exponential due to path duplication
Space Complexity	O(N) for recursion stack and path storage	Recursive call stack depth

Example: Finding All Paths in a Directed Graph

function findAllPaths(graph, start, end) {
  const result = [];
  const path = [];

  function dfs(node) {
    path.push(node);
    
    if (node === end) {
      result.push([...path]);
    } else {
      for (const neighbor of graph[node] || []) {
        dfs(neighbor);
      }
    }

    path.pop();
  }

  dfs(start);
  return result;
}

// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['D'],
  'D': []
};

const paths = findAllPaths(graph, 'A', 'D');
console.log(paths); // [['A', 'B', 'D'], ['A', 'C', 'D']]

Note: This approach generates all paths but may be inefficient for large graphs due to exponential path growth.

10. Solving Island Problems

Island problems involve counting or modifying connected components in a 2D grid where cells are either land (1) or water (0). Depth-First Search (DFS) is commonly used to traverse and mark visited cells.

Problem	Description	Solution Approach
Number of Islands	Count connected components of `1`s in a grid.	Use DFS to mark all connected `1`s as visited and increment count for each unvisited `1`.
Max Area of Island	Find the largest connected component of `1`s in a grid.	For each unvisited `1`, perform DFS to calculate area and track maximum.
Closed Islands	Count islands that are completely surrounded by water.	Use DFS to check if an island touches the grid boundary. Only count islands not touching boundaries.

Example: Number of Islands

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;
    grid[r][c] = '0'; // Mark as visited
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

// Example usage:
const grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
];
console.log(numIslands(grid)); // Output: 1

Example: Max Area of Island

function maxAreaOfIsland(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let maxArea = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return 0;
    grid[r][c] = '0'; // Mark as visited
    let area = 1;
    area += dfs(r + 1, c);
    area += dfs(r - 1, c);
    area += dfs(r, c + 1);
    area += dfs(r, c - 1);
    return area;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        maxArea = Math.max(maxArea, dfs(r, c));
      }
    }
  }

  return maxArea;
}

// Example usage:
const grid2 = [
  [1,1,0,0,0],
  [1,1,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
];
console.log(maxAreaOfIsland(grid2)); // Output: 4

11. Finding Articulation Points

An articulation point (or cut vertex) in a graph is a vertex whose removal increases the number of connected components in the graph. Finding articulation points is crucial for identifying critical nodes in networks such as communication systems or transportation grids.

Property	Description	Notes
Articulation Point	A vertex in a graph whose removal increases the number of connected components	Used to identify critical nodes in network topology

Example: DFS-based Algorithm to Find Articulation Points

function findArticulationPoints(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(0);
  const low = new Array(n).fill(0);
  const parent = new Array(n).fill(-1);
  const articulationPoints = new Set();
  let time = 0;

  function dfs(u) {
    let children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;

    for (let v of graph[u]) {
      if (!visited[v]) {
        parent[v] = u;
        children++;
        dfs(v);

        low[u] = Math.min(low[u], low[v]);

        if (parent[u] === -1 && children > 1) {
          articulationPoints.add(u);
        }

        if (parent[u] !== -1 && low[v] >= disc[u]) {
          articulationPoints.add(u);
        }
      } else if (v !== parent[u]) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i);
    }
  }

  return Array.from(articulationPoints);
}

Note: The algorithm uses DFS to compute discovery times and low values. A vertex is an articulation point if it is the root of DFS with more than one child, or if it has a child whose low value is greater than or equal to the discovery time of the vertex.

12. Validating Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two graph vertices within the same set are adjacent. This property can be validated using a graph coloring approach with two colors.

Property	Description	Notes
Bipartite Check	Using DFS to color nodes with two colors and ensure no adjacent nodes have the same color	Time Complexity: O(V + E), Space Complexity: O(V)

Example: Bipartite Validation Using DFS

function isBipartite(graph) {
    const color = new Array(graph.length).fill(-1);
    
    function dfs(node, c) {
        color[node] = c;
        for (let neighbor of graph[node]) {
            if (color[neighbor] === -1) {
                if (!dfs(neighbor, 1 - c)) return false;
            } else if (color[neighbor] === c) {
                return false;
            }
        }
        return true;
    }

    for (let i = 0; i < graph.length; i++) {
        if (color[i] === -1) {
            if (!dfs(i, 0)) return false;
        }
    }
    return true;
}

// Example usage:
const graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]];
console.log(isBipartite(graph)); // false

Note: The algorithm uses a two-coloring approach where each node is assigned one of two colors. If any adjacent nodes have the same color, the graph is not bipartite.