[Algorithm] 11. Depth-First Search (DFS)

Depth-First Search (DFS)

1. Clone Graph (LeetCode #133)

function cloneGraph(node: _Node | null): _Node | null {
  if (!node) return null;

  const visitedNodes = new Map<_Node, _Node>();

  function dfs(node: _Node, visitedNodes: Map<_Node, _Node>) {
    if (visitedNodes.has(node)) {
      return visitedNodes.get(node)!;
    }

    const clonedNode = new _Node(node.val);
    visitedNodes.set(node, clonedNode);

    for (const neighbor of node.neighbors) {
      clonedNode.neighbors.push(dfs(neighbor, visitedNodes));
    }

    return clonedNode;
  }

  return dfs(node, visitedNodes);
}

2. Path Sum II (LeetCode #113)

// targetSum - node.val
function pathSum1(root: TreeNode | null, targetSum: number): number[][] {
  const result: number[][] = [];

  function dfs(node: TreeNode | null, pathNums: number[], sum: number) {
    if (!node) return;

    pathNums.push(node.val);
    if (!node.left && !node.right && sum === targetSum) {
      result.push([...pathNums]);
    } else {
      dfs(node.left, pathNums, sum - node.val);
      dfs(node.right, pathNums, sum - node.val);
    }

    pathNums.pop();
  }

  dfs(root, [], targetSum);
  return result;
}

// sum + node.val
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
  const result: number[][] = [];

  function dfs(node: TreeNode | null, pathNums: number[], sum: number) {
    if (!node) return;
    pathNums.push(node.val);
    sum += node.val;

    if (!node.left && !node.right) {
      if (sum === targetSum) result.push([...pathNums]);
    }

    if (sum <= targetSum) {
      dfs(node.left, pathNums, sum);
      dfs(node.right, pathNums, sum);
    }

    pathNums.pop();
  }

  dfs(root, [], 0);
  return result;
}

3. Course Schedule II (LeetCode #210)

Kahn's Algorithm for Topological sort of a directed graph
Based on BFS (breadth-first search).
In-degree는 그래프에서 정점에 들어오는 간선의 수
Out-degree는 그래프에서 정점에 나가는 간선의 수

BFS

function findOrderBFS(numCourses: number, prerequisites: number[][]): number[] {
  // Step 1: Build the graph and calculate in-degrees
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree: number[] = new Array(numCourses).fill(0);
  // Build the graph and calculate in-degree for each course

  for (const [course, preReq] of prerequisites) {
    graph[preReq].push(course); // Add course to the list of the prerequisite's neighbors
    inDegree[course]++; // Increment in-degree for the course
  }

  // Step 2: Initialize the queue with courses that have no prerequisites (in-degree 0)

  const queue: number[] = [];

  for (let courseIdx = 0; courseIdx < numCourses; courseIdx++) {
    // if (inDegree[i] === 0) queue.push(i);
    const hasNoPrerequisites = inDegree[courseIdx] === 0;
    if (hasNoPrerequisites) queue.push(courseIdx);
  }

  // Step 3: Perform topological sorting using BFS
  const order: number[] = [];
  while (queue.length > 0) {
    const course = queue.shift()!;
    order.push(course);

    // Process all neighbors of the current course

    for (const neighbor of graph[course]) {
      inDegree[neighbor]--; // Decrease the in-degree of the neighbor
      // if (inDegree[neighbor] === 0) {
      //   queue.push(neighbor); // If in-degree becomes 0, add it to the queue
      // }

      const isReadyToTake = inDegree[neighbor] === 0;
      if (isReadyToTake) queue.push(neighbor);
    }
  }

  return order.length === numCourses ? order : [];
}

DFS

function findOrderDFS(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const visited: number[] = new Array(numCourses).fill(0); // 0 = unvisited, 1 = visiting, 2 = visited
  const result: number[] = [];

  for (const [course, preReq] of prerequisites) {
    graph[preReq].push(course);
  }

  // Step 2: DFS helper function for cycle detection and topological sorting
  function dfsAndFindCycleAndTopologicalSort(course: number): boolean {
    // if (visited[course] === 1) return false; // Cycle detected
    // if (visited[course] === 2) return true; // Already processed

    const isInProgress = visited[course] === 1;
    const isAlreadyProcessed = visited[course] === 2;

    if (isInProgress) return false; // Cycle detected
    if (isAlreadyProcessed) return true; // Already visited

    visited[course] = 1;

    // Explore all the neighbors (courses that depend on the current course)
    for (const neighbor of graph[course]) {
      if (!dfsAndFindCycleAndTopologicalSort(neighbor)) return false;
    }

    visited[course] = 2; // Mark as fully processed
    result.push(course);

    return true;
  }

  // Step 3: Apply DFS on each course
  for (let i = 0; i < numCourses; i++) {
    const cycleDetected =
      visited[i] === 0 && !dfsAndFindCycleAndTopologicalSort(i);
    if (cycleDetected) return []; // If a cycle is detected, return an empty array
  }

  // Step 4: Return the result, reverse the result because we added courses in reverse order
  return result.reverse();
}