Finding Your Way Through a Graph

The plain-language idea

You already know how to explore a tree two ways: diving deep down one path (depth-first), or spreading out ring by ring (breadth-first). Good news — both work on graphs too, with almost no changes.

Here's the catch a tree never gave you. In a maze shaped like a tree, every hallway leads somewhere new — you can never accidentally walk in a circle. A graph doesn't make that promise. Picture an actual maze with loops in it: walk far enough and you can end up back at a hallway you already explored, walking it again, without realizing you're going in circles.

So graph traversal needs one new habit that tree traversal never needed: leaving a mark. Before you walk into a hallway, note that you've already been there. If you reach a hallway you've already marked, turn back — you already know what's down there.

This single idea — remembering where you've been — is the entire difference between traversing a tree and traversing a graph. Everything else about depth-first and breadth-first search stays exactly the same.

See it in a real thing: exploring a maze with loops

const maze = {
  entrance: ["hallwayA", "hallwayB"],
  hallwayA: ["entrance", "junction"], // loops back to the entrance!
  hallwayB: ["junction"],
  junction: ["hallwayA", "hallwayB", "exit"],
  exit: [],
};

function findPath(start) {
  const visited = new Set(); // rooms we've already seen
  const queue = [start];
  visited.add(start);

  while (queue.length > 0) {
    const room = queue.shift();
    console.log("visiting:", room);

    for (const next of maze[room]) {
      if (!visited.has(next)) {
        visited.add(next); // mark it the moment we discover it
        queue.push(next);
      }
    }
  }
}

findPath("entrance"); // visits each room exactly once, even with the loop

What people usually miss

Watch out

• "Why didn't I need this for trees?" Trees don't have cycles by definition, so revisiting a node was never possible there. This isn't a sign you were sloppy before — the problem itself changed.
• Mark a room the moment you discover it, not after you finish visiting it. Marking too late can let the same room get added to the queue twice before either copy is processed.
• The visited set doesn't change the order of the traversal. It only prevents repeats. The "go deep" versus "go wide" logic from before still applies exactly as it did on trees.

The genealogy: two ideas meeting at once

This lesson combines the depth-first and breadth-first traversal from the previous lesson with the graph structure from the lesson before that, plus one new addition they need together: a way to remember where you've been.