Depth-first search (DFS)

DFS commits to a path until it dead-ends, then backs up. Swap BFS's queue for a stack and you have it; write it recursively and the stack is implicit.

function dfs(graph, node, visited = new Set(), order = []) {
  visited.add(node);
  order.push(node);

  for (const next of graph.get(node) ?? []) {
    if (!visited.has(next)) dfs(graph, next, visited, order);
  }

  return order;
}

O(V + E) time, O(V) space — but that space is the call stack, so a graph with a long path can overflow it. The iterative form removes that risk:

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

  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;      // mark on pop: a node may be stacked twice

    visited.add(node);
    order.push(node);

    for (const next of graph.get(node) ?? []) {
      if (!visited.has(next)) stack.push(next);
    }
  }

  return order;
}

Note the difference from BFS: here you check on pop, because a vertex can legitimately be pushed by several neighbours before being visited.

Cycle detection

For a directed graph, three colours: unvisited, in progress, finished. Meeting an in-progress vertex means a cycle — a back edge.

function hasCycle(graph) {
  const state = new Map();      // 0 unvisited, 1 in progress, 2 done

  const visit = (node) => {
    if (state.get(node) === 1) return true;    // back edge → cycle
    if (state.get(node) === 2) return false;   // already cleared

    state.set(node, 1);
    for (const next of graph.get(node) ?? []) if (visit(next)) return true;
    state.set(node, 2);

    return false;
  };

  return [...graph.keys()].some((node) => state.get(node) !== 2 && visit(node));
}

A plain visited set is not enough — it cannot tell "already finished" from "currently on the stack", and that distinction is the cycle.

For an undirected graph, ignore the edge you arrived on and any other visited neighbour is a cycle.

BFS or DFS?