Clone Graph

<aside> 💡 Run a DFS that additionally creates a copy and returns it at the end of every recursion call. To avoid infinite loop, return already visited (and therefore created) node at the beginning.

</aside>

https://leetcode.com/problems/clone-graph/

const visited = {};

function dfs(node) {

  // 1. check if visited
  if (visited[node.val]) {
    return visited[node.val];
  }

  // 2. create a copy and add to hashmap
  const copy = new Node(node.val);
  visited[node.val] = copy;

  // 3. visit neighbors
  for (neighbor of node.neighbors) {
    const neighborCopy = dfs(neighbor);
    copy.neighbors.push(neighborCopy);
  }

  // 4. return copy
  return copy;

}

• Intuition
• Solution
• Image

Number of Connected Components in an Undirected Graph

<aside> 💡 Create adjacency list, run a DFS on all vertices. Before running a DFS, check if a vertex is in visited list.

</aside>

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

function dfs(node) {

  // still on recursion stack and seen again (a cycle)
  if (state[node] === "visiting") return false;

  // left recursion stack and all neighbors are visited
  if (state[node] === "visited") return true;

  state[node] = "visiting";

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

  // leaving recursion stack
  state[node] = "visited";

  // no cycles
  return true;

}

• Solution