Breadth-First Search: Taking Care of the Neighborhood First

Chris is developing a feature for a Social Network Service (SNS).

"I want to display a list of recommended friends in order of closeness: my '1st-degree' friends first, then the '2nd-degree' friends (friends of friends), and so on."

He tried using DFS (Depth-First Search), which we learned last time, but a problem arose.

It ended up recommending someone on the other side of the globe whom Chris doesn't know at all, just because they were a friend of a friend of a friend... (Because DFS beats just one path to death!)

"No, I need to scan my immediate surroundings step-by-step!"

What is needed here is BFS (Breadth-First Search). Like ripples spreading in a circle when a stone is thrown into a lake, this method searches nodes starting from those closest to the starting point.

1. Spreading Like Ripples

If DFS is "Maze Solving," BFS is like "Virus Spread" or a "Wi-Fi Signal."

Because it searches by Level (Layer), using BFS guarantees the "Shortest Path with the fewest number of steps."

2. The Core of Implementation: Queue

While DFS used a Stack or Recursion, BFS uses a Queue.

This is because you must line up the neighbors you found first and process them in the order they were discovered (FIFO) to prevent the level order from getting tangled.

JavaScript Implementation (Graph Traversal)

// Graph Data (Adjacency List)
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"]
};

function bfs(startNode) {
  const visited = new Set(); // To keep track of visited nodes
  const queue = [startNode]; // 1. Create Queue and insert start node

  visited.add(startNode); // Mark start node as visited

  // 2. Repeat until Queue is empty
  while (queue.length > 0) {
    // 3. Take one from the front (Shift)
    const currentNode = queue.shift(); 
    console.log("Visit:", currentNode);

    // 4. Check neighbors of the current node
    for (const neighbor of graph[currentNode]) {
      // If it's a place we haven't visited yet?
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // Mark as visited
        queue.push(neighbor);  // Line up in the Queue (Push)
      }
    }
  }
}

bfs("A");
// Output Order: A -> B -> C -> D -> E -> F (Visited by distance)

Caution: shift() in JavaScript arrays requires pulling all remaining elements forward after removing the first one, costing O(N). If the data is very large, it is better to implement a Linked List queue manually. (Reference Chapter 2, Part 2).

3. DFS vs BFS: When to Use Which?

These two algorithms are rivals. You must choose the right one for the situation.

4. Real-World Problem: Finding the Shortest Path

"What is the minimum number of cities I need to pass through to get from Seoul to Busan?"

This kind of problem is unconditionally BFS.

If you solve it with DFS, you might find a path like Seoul → Gangwon-do → ... → Busan, but there is no guarantee that it is the fastest way. With BFS, the first path that reaches Busan is guaranteed to be the shortest path.

Key Takeaways

Now we have learned the basics of pathfinding.

But what if the cost of building roads differs between cities? How can we connect all cities while spending the least amount of money on construction?

Let's look into the method of building the most cost-effective network, the Minimum Spanning Tree (MST).

🔗 References