Breadth-First Search (BFS)

November 19, 2025
#bfs #breadth-first-search #graph-traversal #algorithms #graph #interviewing

Table of Contents

Introduction

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores vertices level by level, visiting all neighbors of a vertex before moving to the next level. Think of it like ripples spreading out in water—you explore all vertices at distance 1, then distance 2, and so on.

BFS is essential for finding shortest paths in unweighted graphs, level-order traversal of trees, and solving maze/puzzle problems. It uses a queue to maintain the order of exploration.

Review Graphs, Queues, and Binary Trees first if needed.

How BFS works

BFS explores a graph in layers:

  1. Start at a source vertex
  2. Visit all neighbors (distance 1)
  3. Visit all neighbors of neighbors (distance 2)
  4. Continue until all reachable vertices are visited

Visual example:

Graph:
    A --- B --- C
    |     |
    D --- E

BFS from A:
Level 0: A
Level 1: B, D (neighbors of A)
Level 2: C, E (neighbors of B and D)

Order: A, B, D, C, E

BFS algorithm

Key components:

  • Queue: Maintains vertices to visit (FIFO)
  • Visited set: Tracks visited vertices to avoid cycles
  • Level tracking (optional): Track distance from source

Steps:

  1. Enqueue starting vertex and mark as visited
  2. While queue is not empty:
    • Dequeue a vertex
    • Process it
    • Enqueue all unvisited neighbors
    • Mark neighbors as visited

BFS implementation

BFS on a graph

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }

  // BFS traversal
  bfs(start) {
    const visited = new Set();
    const queue = [start];
    const result = [];

    visited.add(start);

    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    return result;
  }

  // BFS with levels
  bfsLevels(start) {
    const visited = new Set();
    const queue = [[start, 0]]; // [vertex, level]
    const levels = {};

    visited.add(start);

    while (queue.length > 0) {
      const [vertex, level] = queue.shift();

      if (!levels[level]) levels[level] = [];
      levels[level].push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([neighbor, level + 1]);
        }
      }
    }

    return levels;
  }
}

// Example usage
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'D');
graph.addEdge('B', 'C');
graph.addEdge('B', 'E');
graph.addEdge('D', 'E');

console.log(graph.bfs('A'));  // ['A', 'B', 'D', 'C', 'E']
console.log(graph.bfsLevels('A'));
// { 0: ['A'], 1: ['B', 'D'], 2: ['C', 'E'] }

from collections import deque

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adjacency_list[v1].append(v2)
        self.adjacency_list[v2].append(v1)

    def bfs(self, start):
        """BFS traversal"""
        visited = set()
        queue = deque([start])
        result = []

        visited.add(start)

        while queue:
            vertex = queue.popleft()
            result.append(vertex)

            for neighbor in self.adjacency_list.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        return result

    def bfs_levels(self, start):
        """BFS with levels"""
        visited = set()
        queue = deque([(start, 0)])  # (vertex, level)
        levels = {}

        visited.add(start)

        while queue:
            vertex, level = queue.popleft()

            if level not in levels:
                levels[level] = []
            levels[level].append(vertex)

            for neighbor in self.adjacency_list.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, level + 1))

        return levels

# Example usage
graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('A', 'D')
graph.add_edge('B', 'C')
graph.add_edge('B', 'E')
graph.add_edge('D', 'E')

print(graph.bfs('A'))  # ['A', 'B', 'D', 'C', 'E']
print(graph.bfs_levels('A'))
# {0: ['A'], 1: ['B', 'D'], 2: ['C', 'E']}

import java.util.*;

public class Graph {
    private Map<String, List<String>> adjacencyList;

    public Graph() {
        adjacencyList = new HashMap<>();
    }

    public void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String v1, String v2) {
        addVertex(v1);
        addVertex(v2);
        adjacencyList.get(v1).add(v2);
        adjacencyList.get(v2).add(v1);
    }

    // BFS traversal
    public List<String> bfs(String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        List<String> result = new ArrayList<>();

        visited.add(start);
        queue.offer(start);

        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            result.add(vertex);

            for (String neighbor : adjacencyList.getOrDefault(vertex,
                                    new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        return result;
    }

    // BFS with levels
    public Map<Integer, List<String>> bfsLevels(String start) {
        Set<String> visited = new HashSet<>();
        Queue<Object[]> queue = new LinkedList<>();
        Map<Integer, List<String>> levels = new HashMap<>();

        visited.add(start);
        queue.offer(new Object[]{start, 0});

        while (!queue.isEmpty()) {
            Object[] curr = queue.poll();
            String vertex = (String) curr[0];
            int level = (int) curr[1];

            levels.putIfAbsent(level, new ArrayList<>());
            levels.get(level).add(vertex);

            for (String neighbor : adjacencyList.getOrDefault(vertex,
                                    new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(new Object[]{neighbor, level + 1});
                }
            }
        }

        return levels;
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "D");
        graph.addEdge("B", "C");
        graph.addEdge("B", "E");
        graph.addEdge("D", "E");

        System.out.println(graph.bfs("A"));
        // [A, B, D, C, E]
        System.out.println(graph.bfsLevels("A"));
        // {0=[A], 1=[B, D], 2=[C, E]}
    }
}

BFS on a binary tree

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function bfsTree(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.value);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

// Level-order with levels
function levelOrderTree(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.value);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}

// Example
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(bfsTree(root));  // [1, 2, 3, 4, 5]
console.log(levelOrderTree(root));  // [[1], [2, 3], [4, 5]]

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def bfs_tree(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.value)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result

def level_order_tree(root):
    """Level-order with levels"""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.value)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

# Example
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(bfs_tree(root))  # [1, 2, 3, 4, 5]
print(level_order_tree(root))  # [[1], [2, 3], [4, 5]]

import java.util.*;

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class BFSTree {
    public static List<Integer> bfsTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.value);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        return result;
    }

    public static List<List<Integer>> levelOrderTree(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.value);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println(bfsTree(root));  // [1, 2, 3, 4, 5]
        System.out.println(levelOrderTree(root));
        // [[1], [2, 3], [4, 5]]
    }
}

Finding shortest path with BFS

function shortestPath(graph, start, end) {
  const visited = new Set();
  const queue = [[start, [start]]]; // [vertex, path]

  visited.add(start);

  while (queue.length > 0) {
    const [vertex, path] = queue.shift();

    if (vertex === end) {
      return path;
    }

    for (const neighbor of graph.adjacencyList.get(vertex) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return null; // No path found
}

console.log(shortestPath(graph, 'A', 'E'));  // ['A', 'B', 'E']

def shortest_path(graph, start, end):
    visited = set()
    queue = deque([(start, [start])])  # (vertex, path)

    visited.add(start)

    while queue:
        vertex, path = queue.popleft()

        if vertex == end:
            return path

        for neighbor in graph.adjacency_list.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path found

print(shortest_path(graph, 'A', 'E'))  # ['A', 'B', 'E']

public static List<String> shortestPath(Graph graph,
                                        String start, String end) {
    Set<String> visited = new HashSet<>();
    Queue<Object[]> queue = new LinkedList<>();

    visited.add(start);
    queue.offer(new Object[]{start, Arrays.asList(start)});

    while (!queue.isEmpty()) {
        Object[] curr = queue.poll();
        String vertex = (String) curr[0];
        List<String> path = (List<String>) curr[1];

        if (vertex.equals(end)) {
            return path;
        }

        for (String neighbor : graph.getNeighbors(vertex)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                List<String> newPath = new ArrayList<>(path);
                newPath.add(neighbor);
                queue.offer(new Object[]{neighbor, newPath});
            }
        }
    }

    return null; // No path found
}

Common BFS problems

1. Number of islands (2D grid)

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function bfs(r, c) {
    const queue = [[r, c]];
    grid[r][c] = '0'; // Mark as visited

    const directions = [[0,1], [1,0], [0,-1], [-1,0]];

    while (queue.length > 0) {
      const [row, col] = queue.shift();

      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;

        if (newRow >= 0 && newRow < rows &&
            newCol >= 0 && newCol < cols &&
            grid[newRow][newCol] === '1') {
          grid[newRow][newCol] = '0';
          queue.push([newRow, newCol]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        bfs(r, c);
        count++;
      }
    }
  }

  return count;
}

2. Word ladder (shortest transformation)

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  const queue = [[beginWord, 1]]; // [word, level]
  const visited = new Set([beginWord]);

  while (queue.length > 0) {
    const [word, level] = queue.shift();

    if (word === endWord) return level;

    // Try changing each character
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) { // 'a' to 'z'
        const newWord = word.slice(0, i) +
                       String.fromCharCode(c) +
                       word.slice(i + 1);

        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, level + 1]);
        }
      }
    }
  }

  return 0; // No path
}

BFS vs DFS comparison

Feature BFS DFS
Data structure Queue (FIFO) Stack/Recursion (LIFO)
Order Level by level Depth first
Shortest path ✅ Yes (unweighted) ❌ No
Space O(width) O(height)
Use cases Shortest path, level-order Detect cycles, topological sort

Complexity analysis

  • Time: O(V + E) where V = vertices, E = edges
  • Space: O(V) for queue and visited set

Common pitfalls

  • Not marking as visited: Leads to infinite loops
  • Marking too late: Mark when adding to queue, not when dequeuing
  • Forgetting disconnected components: May need to run BFS from multiple starting points
  • Using DFS when BFS needed: BFS guarantees shortest path in unweighted graphs

When to use BFS

  • Finding shortest path in unweighted graphs
  • Level-order traversal of trees
  • Finding all nodes at distance k
  • Connected components in undirected graphs
  • Solving maze or grid problems
  • Peer-to-peer networks (broadcasting)

Practice problems

  1. Binary tree level order traversal
  2. Binary tree right side view
  3. Binary tree zigzag level order traversal
  4. Rotting oranges (grid BFS)
  5. Shortest path in binary matrix
  6. Word ladder
  7. Open the lock (BFS with states)
  8. Minimum knight moves
  9. Shortest bridge
  10. 01 Matrix (distance to nearest 0)
  11. Walls and gates
  12. Snakes and ladders
  13. Shortest path visiting all nodes
  14. Bus routes
  15. Minimum genetic mutation

Complexity summary

  • Time: O(V + E) — visit each vertex and edge once
  • Space: O(V) — queue and visited set

BFS is essential for graph traversal and guarantees the shortest path in unweighted graphs. Master BFS and you’ll be able to solve a wide range of graph and tree problems efficiently.

Thanks for visiting
We are actively updating content to this site. Thanks for visiting! Please bookmark this page and visit again soon.
Sponsor