Graphs: Representations, BFS, and DFS

BFS (queue, level-by-level) and DFS (stack/recursion, depth-first) over the same adjacency-list graph, both tracking a visited set to handle cycles safely.

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

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // mark visited when ENQUEUED, not when dequeued -- avoids duplicate enqueues
        queue.push(neighbor);
      }
    }
  }
  return order;
}

function dfs(graph, start, visited = new Set(), order = []) {
  visited.add(start);
  order.push(start);
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, order); // recursive call = implicit stack
    }
  }
  return order;
}

console.log(bfs(graph, "A")); // ["A", "B", "C", "D", "E"] -- level by level
console.log(dfs(graph, "A")); // ["A", "B", "D", "C", "E"] -- as deep as possible first

Add a new node F connected only to E, and confirm both bfs and dfs from A eventually reach it.

Write bfs(graph, start) returning the visit order (an array), correctly handling a graph with a cycle using a visited set (mark a node visited when it's ENQUEUED, not when dequeued, to avoid enqueuing the same node twice).

Checks: visits nodes in correct level order · terminates correctly and visits each node exactly once even with a cycle · handles a single isolated node with no edges

Write hasPath(graph, start, end) using DFS (recursive, with a visited set) to determine whether ANY path exists from start to end (return true if start === end trivially). Then write hasCycle(graph) for an UNDIRECTED graph (every edge appears in both directions in the adjacency list) that detects whether any cycle exists, using DFS and tracking each node's parent to correctly ignore the trivial 'came right back the way I arrived' case.

Checks: finds a path that exists through an intermediate node · correctly reports no path to a disconnected node · a node trivially has a path to itself · correctly reports no cycle in a simple chain · correctly detects a genuine cycle (a triangle)