Graph DFS (Depth-first-search) in javascript

✨ Recursive Algorithm

• using recursive function.

const dfs = (cur) => {
  let res = 0;

  // do some logic

  for (const next of graph[cur]) {
    if (seen.has(next)) continue;

    seen.add(next);
    ans += dfs(next);
  }

  return res;
};

const seen = new Set([START_NODE]);
return dfs(START_NODE);

💡 Tips : Use parent node instead of using [object Object] ([object Object])

const dfs = (cur, parent) => {
  if (!cur) return;

  for (const next of graph[cur]) {
    // Block to move back to parent
    if (next === parent) continue;

    // logic

    dfs(next, cur);
  }
};

dfs(0, -1);

✨ Iterative Algorithm

• using stack.

const dfs = (graph) => {
  const stack = [START_NODE];
  const seen = new Set([START_NODE]);

  let res = 0;

  while (stack.length) {
    const cur = stack.pop();

    // do some logic

    for (const next of graph[cur]) {
      if (seen.has(next)) continue;

      seen.add(next);
      stack.push(next);
    }
  }

  return res;
};

🏷️ Related tags

• #dfs