CS Glossary

Breadth-First Search (BFS)

A graph/tree traversal that explores all neighbors at the current depth before moving to the next level, using a queue.

Time: O(V + E) where V = vertices, E = edges Space: O(V)

Overview

Breadth-First Search (BFS) explores a graph or tree level by level. It starts at a source node, visits all its neighbors, then visits all neighbors of those neighbors, and so on. BFS uses a queue (FIFO) to maintain the frontier of nodes to visit. It is the standard algorithm for finding the shortest path in unweighted graphs — the first time you reach a node via BFS, you have found the shortest path to it.

How It Works

1 Initialize a queue with the starting node and mark it as visited.
2 Dequeue the front node and process it (check if it is the target, record its level, etc.).
3 Enqueue all unvisited neighbors of the dequeued node and mark them as visited.
4 Repeat steps 2-3 until the queue is empty or the target is found.
5 For level-order traversal, process nodes level by level by tracking the queue size at each level.

Complexity Analysis

Time: O(V + E) where V = vertices, E = edges Space: O(V)

Each vertex is enqueued and dequeued at most once (O(V)), and each edge is examined at most once (O(E)). The queue stores at most V vertices at any time, giving O(V) space.

When to Use

→Finding the shortest path in an unweighted graph
→Level-order traversal of a binary tree
→Finding connected components in a graph
→Solving "minimum steps" or "minimum moves" problems (e.g., rotting oranges)
→Bipartiteness checking (two-coloring)
→Web crawling and social network analysis

Common Mistakes

⚠Forgetting to mark nodes as visited when enqueuing (not when dequeuing)
⚠Using DFS (stack/recursion) instead of BFS when shortest path is needed
⚠Not handling disconnected components (need to loop over all nodes)
⚠Forgetting to track levels for level-order problems
⚠Enqueuing the same node multiple times before it is visited

Code Examples

List<Integer> bfs(List<List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    visited.add(start);
    queue.add(start);
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.add(neighbor);
            }
        }
    }
    return order;
}

vector<int> bfs(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    visited[start] = true;
    q.push(start);
    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return order;
}

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

Related Patterns

▷ Queue / BFS 🌲 Trees / DFS ◉ Graphs

Practice Problems

Number of Islands	Medium
Rotting Oranges	Medium
Binary Tree Level Order Traversal	Medium
Course Schedule	Medium

Frequently Asked Questions

What is BFS and when should I use it?

BFS (Breadth-First Search) is a graph/tree traversal that explores all neighbors at the current depth before moving deeper. Use BFS when you need: (1) shortest path in an unweighted graph, (2) level-order traversal, (3) minimum steps/moves problems, or (4) checking connectivity. BFS guarantees the shortest path because it explores nodes in order of their distance from the source.

What is the difference between BFS and DFS?

BFS explores level by level using a queue — it finds shortest paths in unweighted graphs. DFS explores as deep as possible before backtracking using a stack/recursion — it uses less memory and is better for cycle detection, topological sort, and path existence problems. BFS is O(V+E) time and O(V) space; DFS is also O(V+E) time but O(V) space (or O(H) for trees).

How do I implement BFS for level-order traversal?

Track the queue size at the start of each level: process exactly queue.size() nodes before moving to the next level. For each level, collect the values in a temporary list and add it to the result after processing all nodes at that depth.

Master this concept with practice

Browse all patterns and problems to build systematic interview intuition.

All Patterns Roadmap