Breadth-First Search (BFS) in Graphs

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores the neighbor nodes level by level. Given a starting node in a graph, BFS visits all its adjacent nodes, then moves on to their neighbors, and so on.

BFS is commonly used for finding the shortest path in unweighted graphs, level order traversal of trees, and in many other scenarios where step-wise discovery is important.

Understanding the Problem

Breadth-First Search (BFS) is a fundamental algorithm used to traverse or search nodes in a graph or tree. The core idea is to explore all nodes at the current depth level before moving on to the next level. BFS uses a queue to keep track of the order in which to visit nodes and ensures each node is visited exactly once using a visited set or array.

Let’s say you’re given a graph as an adjacency list, and you need to traverse all its nodes starting from a given source. The problem becomes even more interesting when you have disconnected graphs or cycles.

Our goal is to understand how BFS works step-by-step and handle these special scenarios properly.

Step-by-Step Solution with Example

step 1: Define the Graph

We will represent the graph using an adjacency list. For example:

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

step 2: Understand the Starting Point

We start BFS from node 'A'. This means we will visit 'A' first and then its neighbors — 'B' and 'C'.

step 3: Use a Queue and a Visited Set

We use a queue to manage the order of visiting nodes, and a set to keep track of visited nodes to avoid revisiting.

const queue = ['A'];
const visited = new Set(['A']);

step 4: Begin the Traversal

We dequeue 'A', visit its neighbors 'B' and 'C', and add them to the queue and the visited set.

while (queue.length > 0) {
  const current = queue.shift();
  console.log(current); // print visited node

  for (const neighbor of graph[current]) {
    if (!visited.has(neighbor)) {
      queue.push(neighbor);
      visited.add(neighbor);
    }
  }
}

step 5: Track the Order of Visit

In this example, the BFS traversal order will be: A → B → C → D.

step 6: Print or Store the Result

You can print each visited node, or store them in an array for further analysis.

Edge Cases

1. Disconnected Graph

If the graph has multiple disconnected components, starting BFS from one node will only cover its connected component. To visit all nodes, run BFS for each unvisited node:

for (const node in graph) {
  if (!visited.has(node)) {
    bfs(node);
  }
}

2. Graph with Cycles

Cycles can cause infinite loops if visited nodes are not tracked. Always use a visited set to mark nodes that have already been added to the queue.

3. Self-loops

A node may have an edge to itself (e.g., A: ['A']). The visited set will ensure it’s not processed again and again.

4. Empty Graph

If the graph is empty, return an empty traversal list. Always check for this condition before starting BFS.

Finally

BFS is a powerful and intuitive graph traversal algorithm especially useful for problems involving levels, shortest paths in unweighted graphs, or connectivity checks. By thinking of BFS like spreading a message — where each person tells all their immediate friends first — you can intuitively understand how it works. With careful use of a queue and visited tracking, you can avoid pitfalls like cycles or missed components in disconnected graphs.

Always test your implementation against edge cases like cycles, disconnected graphs, and empty inputs to ensure robustness.

1. Initialize a queue and a visited set.
2. Enqueue the starting node and mark it as visited.
3. While the queue is not empty:
1. Dequeue the front node.
2. Process or record the node.
3. For each adjacent node of the current node:
1. If it is not visited, enqueue it and mark it as visited.
4. Repeat until the queue is empty.

O(V)

Explanation: The space complexity is proportional to the number of vertices because the queue and visited set each store up to V elements.