Digging Until the Dead End: Depth-First Search (DFS)

Chris is building a 'Category Menu' for a shopping mall.

Categories can go endlessly deep, like [Electronics > Computers > Laptops > Gaming Laptops].

Chris wants to find a specific category called "Gaming Laptops" and display it on the screen.

However, the data structure is tangled in a Tree form.

"For arrays, I can just use a for loop, but how do I traverse data that branches out like this?"

There are two main search methods used in this situation:

Today, let's first look at DFS, the standard for maze solving and the flower of recursive functions.

1. The Standard of Maze Solving: "Go Deep Down One Path"

The principle of DFS is exactly like solving a maze.

When you encounter a fork in the road, you unconditionally choose one path (e.g., Left) and go straight until you hit a dead end.

What happens when you reach a dead end? You Backtrack to the immediate previous fork and explore the other path you didn't take.

It is an impatient algorithm that says, "Let's see the end of this path first."

2. The Core of Implementation: Stack & Recursion

The easiest way to implement DFS is to use a Recursive Function.

When a function calls another function, tasks pile up in the computer's Call Stack. This stack structure perfectly matches the "returning to the previous path" process of DFS.

JavaScript Implementation (Tree Traversal)

Let's assume there is a simple tree object.

const tree = {
  name: "Root",
  children: [
    {
      name: "A",
      children: [
        { name: "A-1", children: [] },
        { name: "A-2", children: [] }
      ]
    },
    {
      name: "B",
      children: [
        { name: "B-1", children: [] }
      ]
    }
  ]
};

function dfs(node) {
  // 1. Process current node (Write in guestbook)
  console.log("Visit:", node.name);

  // 2. Recursively call children in order (Go deeper)
  if (node.children) {
    node.children.forEach(child => {
      dfs(child);
    });
  }
}

dfs(tree);
// Output Order: Root -> A -> A-1 -> A-2 -> B -> B-1

The code is surprisingly simple. The moment you call a child with forEach, the execution flow gets sucked deep into the child node first. This is DFS.

3. When Should You Use It? (Use Cases)

DFS is advantageous when you need to store "Characteristics of the Path" or need to "Visit All Nodes".

4. Caution: The Swamp of Infinite Loops

If the data is not a Tree but a Graph form where nodes bite each other's tails, you must be careful.

What if A points to B, and B points back to A?

dfs(A) → dfs(B) → dfs(A) → ... It will never end.

To prevent this, Visited tracking is essential.

const visited = new Set(); // Place to stamp your visit

function dfsGraph(node) {
  if (visited.has(node)) return; // If already visited, go back!
  
  visited.add(node); // Stamp it
  console.log(node);

  node.neighbors.forEach(neighbor => dfsGraph(neighbor));
}

Key Takeaways

"Wait, I want to find the fastest way from Seoul to Busan!"

If you need to guarantee the shortest distance, DFS, which digs only one well, is not a good choice.

Like ripples spreading in a circle when a stone is thrown into a lake, let's learn BFS (Breadth-First Search), which searches step-by-step from the nearest places.

🔗 References