Breadth-First Search (BFS) explores nodes level by level.

Its biggest advantage is:

BFS guarantees the shortest path in an unweighted graph.

Focus on recognizing:

“Minimum steps” + “Unweighted graph” = BFS

Pattern Table

Pattern	Typical Questions	Trigger
Basic BFS	Graph traversal	Visit all neighbors
Shortest Path	Minimum edges	Unweighted shortest path
Multi-Source BFS	Nearest source	Multiple starting nodes
Level BFS	Distance / layers	Process level-by-level
Grid BFS	Matrix traversal	4/8-direction movement

Mental Trigger

Queue + Level-by-Level + Minimum Steps → BFS

1. Generic Java BFS Template (Base)

This is the main template to remember.

Watch it work before reading the code — notice how the queue drains level by level, and that nodes are marked visited before entering the queue:

Breadth-First Search

Level-order traversal and unweighted shortest paths.

Mark the start visited, enqueue it; poll the front, then enqueue all unvisited neighbours (mark them visited BEFORE enqueueing to avoid duplicates). First-in-first-out gives level-by-level order and guarantees shortest unweighted paths.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        queue = [A]; visited = {A}
                      
                        2
                        while queue not empty:
                      
                        3
                          node = queue.poll()
                      
                        4
                          for each neighbour of node:
                      
                        5
                            if neighbour not visited:
                      
                        6
                              visited.add(neighbour)
                      
                        7
                              queue.add(neighbour)

public void bfs(List<List<Integer>> graph, int start) {
    int n = graph.size();

    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<>();

    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

from collections import deque

def bfs(graph, start):
    n = len(graph)

    visited = [False] * n
    queue = deque()

    queue.append(start)
    visited[start] = True

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

void bfs(vector<vector<int>>& graph, int start) {
    int n = graph.size();

    vector<bool> visited(n, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

function bfs(graph, start) {
  const n = graph.length;

  const visited = new Array(n).fill(false);

  // ponytail: shift() is O(n), fine at this scale; use head-index deque if profiling matters
  const queue = [];

  queue.push(start);
  visited[start] = true;

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

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
}

Everything else in BFS is a modification of this template.

Pattern 1: Basic BFS Traversal

Java Code

public List<Integer> bfsTraversal(List<List<Integer>> graph, int start) {
    int n = graph.size();

    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<>();
    List<Integer> order = new ArrayList<>();

    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();

        order.add(node);

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }

    return order;
}

from collections import deque

def bfs_traversal(graph, start):
    n = len(graph)

    visited = [False] * n
    queue = deque()
    order = []

    queue.append(start)
    visited[start] = True

    while queue:
        node = queue.popleft()

        order.append(node)

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

    return order

vector<int> bfsTraversal(vector<vector<int>>& graph, int start) {
    int n = graph.size();

    vector<bool> visited(n, false);
    queue<int> q;
    vector<int> order;

    q.push(start);
    visited[start] = true;

    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;
}

function bfsTraversal(graph, start) {
  const n = graph.length;

  const visited = new Array(n).fill(false);
  const queue = [];
  const order = [];

  queue.push(start);
  visited[start] = true;

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

    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }

  return order;
}

What Changed from the Base Template?

Store traversal order

Added:

List<Integer> order = new ArrayList<>();

because we need to return the order in which nodes are visited.

Record each node

Added:

order.add(node);

because the traversal result must contain every visited node.

Basic Traversal = Base BFS + Store node order.

Pattern 2: Shortest Path in an Unweighted Graph

Java Code

public int[] shortestPath(List<List<Integer>> graph, int start) {
    int n = graph.size();

    int[] distance = new int[n];
    Arrays.fill(distance, -1);

    Queue<Integer> queue = new ArrayDeque<>();

    queue.offer(start);
    distance[start] = 0;

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int neighbor : graph.get(node)) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[node] + 1;
                queue.offer(neighbor);
            }
        }
    }

    return distance;
}

from collections import deque

def shortest_path(graph, start):
    n = len(graph)

    distance = [-1] * n

    queue = deque()

    queue.append(start)
    distance[start] = 0

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    return distance

vector<int> shortestPath(vector<vector<int>>& graph, int start) {
    int n = graph.size();

    vector<int> distance(n, -1);

    queue<int> q;

    q.push(start);
    distance[start] = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : graph[node]) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[node] + 1;
                q.push(neighbor);
            }
        }
    }

    return distance;
}

function shortestPath(graph, start) {
  const n = graph.length;

  const distance = new Array(n).fill(-1);

  const queue = [];

  queue.push(start);
  distance[start] = 0;

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

    for (const neighbor of graph[node]) {
      if (distance[neighbor] === -1) {
        distance[neighbor] = distance[node] + 1;
        queue.push(neighbor);
      }
    }
  }

  return distance;
}

What Changed from the Base Template?

Replace `visited[]` with `distance[]`

Base:

boolean[] visited = new boolean[n];

Changed:

int[] distance = new int[n];
Arrays.fill(distance, -1);

because we need to know how far every node is from the source.

Source starts at distance 0

Base:

visited[start] = true;

Changed:

distance[start] = 0;

Distance increases by one edge

Base:

queue.offer(neighbor);

Changed:

distance[neighbor] = distance[node] + 1;
queue.offer(neighbor);

Because BFS processes nodes in increasing distance order, the first time we reach a node is its shortest distance.

Shortest Path BFS = Base BFS + Distance instead of visited.

Pattern 3: Multi-Source BFS

Java Code

public int[] multiSourceBFS(
        List<List<Integer>> graph,
        List<Integer> sources) {

    int n = graph.size();

    int[] distance = new int[n];
    Arrays.fill(distance, -1);

    Queue<Integer> queue = new ArrayDeque<>();

    for (int source : sources) {
        queue.offer(source);
        distance[source] = 0;
    }

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int neighbor : graph.get(node)) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[node] + 1;
                queue.offer(neighbor);
            }
        }
    }

    return distance;
}

from collections import deque

def multi_source_bfs(graph, sources):
    n = len(graph)

    distance = [-1] * n

    queue = deque()

    for source in sources:
        queue.append(source)
        distance[source] = 0

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    return distance

vector<int> multiSourceBFS(
        vector<vector<int>>& graph,
        vector<int>& sources) {

    int n = graph.size();

    vector<int> distance(n, -1);

    queue<int> q;

    for (int source : sources) {
        q.push(source);
        distance[source] = 0;
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : graph[node]) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[node] + 1;
                q.push(neighbor);
            }
        }
    }

    return distance;
}

function multiSourceBFS(graph, sources) {
  const n = graph.length;

  const distance = new Array(n).fill(-1);

  const queue = [];

  for (const source of sources) {
    queue.push(source);
    distance[source] = 0;
  }

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

    for (const neighbor of graph[node]) {
      if (distance[neighbor] === -1) {
        distance[neighbor] = distance[node] + 1;
        queue.push(neighbor);
      }
    }
  }

  return distance;
}

What Changed from the Base Template?

Multiple starting nodes

Base:

queue.offer(start);

Changed:

for (int source : sources) {
    queue.offer(source);
    distance[source] = 0;
}

because all sources begin at distance 0 and expand simultaneously.

Why does this work?

Imagine:

        A
        |
        B
        |
S1 ---- C ---- S2
        |
        D

Both S1 and S2 start in the queue.

The BFS expands outward from both sources at the same time.

Therefore:

Every node gets its distance from the nearest source.

Multi-Source BFS = Shortest Path BFS + Multiple sources initialized at distance 0.

Pattern 4: Level-Order BFS

Sometimes we don’t need the exact distance array.

We only need to process:

Level 0
Level 1
Level 2
Level 3
...

Java Code

public void levelBFS(List<List<Integer>> graph, int start) {
    int n = graph.size();

    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<>();

    queue.offer(start);
    visited[start] = true;

    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int node = queue.poll();

            // Process node at this level.

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }

        level++;
    }
}

from collections import deque

def level_bfs(graph, start):
    n = len(graph)

    visited = [False] * n
    queue = deque()

    queue.append(start)
    visited[start] = True

    level = 0

    while queue:
        size = len(queue)

        for _ in range(size):
            node = queue.popleft()

            # Process node at this level.

            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

        level += 1

void levelBFS(vector<vector<int>>& graph, int start) {
    int n = graph.size();

    vector<bool> visited(n, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    int level = 0;

    while (!q.empty()) {
        int size = q.size();

        for (int i = 0; i < size; i++) {
            int node = q.front();
            q.pop();

            // Process node at this level.

            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }

        level++;
    }
}

function levelBFS(graph, start) {
  const n = graph.length;

  const visited = new Array(n).fill(false);
  const queue = [];

  queue.push(start);
  visited[start] = true;

  let level = 0;

  while (queue.length > 0) {
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const node = queue.shift();

      // Process node at this level.

      for (const neighbor of graph[node]) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      }
    }

    level++;
  }
}

What Changed from the Base Template?

Capture current level size

Added:

int size = queue.size();

At this moment, the queue contains exactly the nodes belonging to the current BFS level.

Process exactly that level

Added:

for (int i = 0; i < size; i++) {
    ...
}

Newly discovered nodes are added to the queue, but they are processed in the next iteration.

Level BFS = Base BFS + queue.size() batching.

Pattern 5: Grid BFS

A grid can be viewed as an implicit graph.

Each cell is a node, and neighboring cells are edges.

For a 4-direction grid:

       up
       ↑
left ← cell → right
       ↓
      down

Java Code

private static final int[][] DIRS = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

public int gridBFS(int[][] grid, int sr, int sc) {
    int n = grid.length;
    int m = grid[0].length;

    Queue<int[]> queue = new ArrayDeque<>();
    boolean[][] visited = new boolean[n][m];

    queue.offer(new int[]{sr, sc});
    visited[sr][sc] = true;

    int distance = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();

            int r = cell[0];
            int c = cell[1];

            for (int[] dir : DIRS) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr < 0 || nr >= n ||
                    nc < 0 || nc >= m ||
                    visited[nr][nc]) {
                    continue;
                }

                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc});
            }
        }

        distance++;
    }

    return distance - 1;
}

from collections import deque

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def grid_bfs(grid, sr, sc):
    n = len(grid)
    m = len(grid[0])

    queue = deque([(sr, sc)])
    visited = [[False] * m for _ in range(n)]

    visited[sr][sc] = True

    distance = 0

    while queue:
        size = len(queue)

        for _ in range(size):
            r, c = queue.popleft()

            for dr, dc in DIRS:
                nr = r + dr
                nc = c + dc

                if (
                    nr < 0 or nr >= n
                    or nc < 0 or nc >= m
                    or visited[nr][nc]
                ):
                    continue

                visited[nr][nc] = True
                queue.append((nr, nc))

        distance += 1

    return distance - 1

const int DIRS[4][2] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

int gridBFS(vector<vector<int>>& grid, int sr, int sc) {
    int n = grid.size();
    int m = grid[0].size();

    queue<pair<int, int>> q;
    vector<vector<bool>> visited(
        n, vector<bool>(m, false));

    q.push({sr, sc});
    visited[sr][sc] = true;

    int distance = 0;

    while (!q.empty()) {
        int size = q.size();

        for (int i = 0; i < size; i++) {
            auto [r, c] = q.front();
            q.pop();

            for (auto& dir : DIRS) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr < 0 || nr >= n ||
                    nc < 0 || nc >= m ||
                    visited[nr][nc]) {
                    continue;
                }

                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }

        distance++;
    }

    return distance - 1;
}

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

function gridBFS(grid, sr, sc) {
  const n = grid.length;
  const m = grid[0].length;

  const queue = [[sr, sc]];
  const visited = Array.from({ length: n }, () =>
    new Array(m).fill(false)
  );

  visited[sr][sc] = true;

  let distance = 0;

  while (queue.length > 0) {
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift();

      for (const [dr, dc] of DIRS) {
        const nr = r + dr;
        const nc = c + dc;

        if (
          nr < 0 || nr >= n ||
          nc < 0 || nc >= m ||
          visited[nr][nc]
        ) {
          continue;
        }

        visited[nr][nc] = true;
        queue.push([nr, nc]);
      }
    }

    distance++;
  }

  return distance - 1;
}

Important Note

The above method returns the maximum distance from the starting cell to any reachable cell, not necessarily the shortest path to a particular destination.

For a shortest-path grid problem, stop when you reach the target.

Example: Shortest Path to Target

public int shortestGridPath(
        int[][] grid,
        int sr,
        int sc,
        int tr,
        int tc) {

    int n = grid.length;
    int m = grid[0].length;

    Queue<int[]> queue = new ArrayDeque<>();
    boolean[][] visited = new boolean[n][m];

    queue.offer(new int[]{sr, sc});
    visited[sr][sc] = true;

    int distance = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();

            int r = cell[0];
            int c = cell[1];

            if (r == tr && c == tc) {
                return distance;
            }

            for (int[] dir : DIRS) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr < 0 || nr >= n ||
                    nc < 0 || nc >= m ||
                    visited[nr][nc] ||
                    grid[nr][nc] == 1) {
                    continue;
                }

                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc});
            }
        }

        distance++;
    }

    return -1;
}

from collections import deque

def shortest_grid_path(grid, sr, sc, tr, tc):
    n = len(grid)
    m = len(grid[0])

    queue = deque([(sr, sc)])
    visited = [[False] * m for _ in range(n)]

    visited[sr][sc] = True

    distance = 0

    while queue:
        size = len(queue)

        for _ in range(size):
            r, c = queue.popleft()

            if r == tr and c == tc:
                return distance

            for dr, dc in DIRS:
                nr = r + dr
                nc = c + dc

                if (
                    nr < 0 or nr >= n
                    or nc < 0 or nc >= m
                    or visited[nr][nc]
                    or grid[nr][nc] == 1
                ):
                    continue

                visited[nr][nc] = True
                queue.append((nr, nc))

        distance += 1

    return -1

int shortestGridPath(
        vector<vector<int>>& grid,
        int sr, int sc, int tr, int tc) {

    int n = grid.size();
    int m = grid[0].size();

    queue<pair<int, int>> q;
    vector<vector<bool>> visited(
        n, vector<bool>(m, false));

    q.push({sr, sc});
    visited[sr][sc] = true;

    int distance = 0;

    while (!q.empty()) {
        int size = q.size();

        for (int i = 0; i < size; i++) {
            auto [r, c] = q.front();
            q.pop();

            if (r == tr && c == tc) {
                return distance;
            }

            for (auto& dir : DIRS) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr < 0 || nr >= n ||
                    nc < 0 || nc >= m ||
                    visited[nr][nc] ||
                    grid[nr][nc] == 1) {
                    continue;
                }

                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }

        distance++;
    }

    return -1;
}

function shortestGridPath(grid, sr, sc, tr, tc) {
  const n = grid.length;
  const m = grid[0].length;

  const queue = [[sr, sc]];
  const visited = Array.from({ length: n }, () =>
    new Array(m).fill(false)
  );

  visited[sr][sc] = true;

  let distance = 0;

  while (queue.length > 0) {
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift();

      if (r === tr && c === tc) {
        return distance;
      }

      for (const [dr, dc] of DIRS) {
        const nr = r + dr;
        const nc = c + dc;

        if (
          nr < 0 || nr >= n ||
          nc < 0 || nc >= m ||
          visited[nr][nc] ||
          grid[nr][nc] === 1
        ) {
          continue;
        }

        visited[nr][nc] = true;
        queue.push([nr, nc]);
      }
    }

    distance++;
  }

  return -1;
}

What Changed from the Base Template?

Nodes became cells

Base:

int node

Changed:

int[] cell

because a grid position needs two coordinates:

(row, column)

Neighbors are generated using directions

Base:

for (int neighbor : graph.get(node))

Changed:

for (int[] dir : DIRS)

because the grid does not explicitly store adjacency lists.

Added boundary checking

if (nr < 0 || nr >= n ||
    nc < 0 || nc >= m)

because grid coordinates must stay inside the matrix.

Grid BFS = Graph BFS where cells are nodes and directions generate neighbors.

Pattern 6: Connected Components with BFS

If the graph can be disconnected, a single BFS only explores one component.

Java Code

public int countComponents(List<List<Integer>> graph) {
    int n = graph.size();

    boolean[] visited = new boolean[n];
    int components = 0;

    for (int start = 0; start < n; start++) {
        if (visited[start]) {
            continue;
        }

        components++;

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }

    return components;
}

from collections import deque

def count_components(graph):
    n = len(graph)

    visited = [False] * n
    components = 0

    for start in range(n):
        if visited[start]:
            continue

        components += 1

        queue = deque([start])
        visited[start] = True

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

    return components

int countComponents(vector<vector<int>>& graph) {
    int n = graph.size();

    vector<bool> visited(n, false);
    int components = 0;

    for (int start = 0; start < n; start++) {
        if (visited[start]) {
            continue;
        }

        components++;

        queue<int> q;
        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }

    return components;
}

function countComponents(graph) {
  const n = graph.length;

  const visited = new Array(n).fill(false);
  let components = 0;

  for (let start = 0; start < n; start++) {
    if (visited[start]) {
      continue;
    }

    components++;

    const queue = [start];
    visited[start] = true;

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

      for (const neighbor of graph[node]) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      }
    }
  }

  return components;
}

What Changed from the Base Template?

Add an outer loop

Base:

bfs(graph, start);

Changed:

for (int start = 0; start < n; start++) {
    if (!visited[start]) {
        // BFS
    }
}

because we need to start another BFS whenever we discover an unvisited component.

Disconnected Graph = BFS + Outer loop over all vertices.

BFS Pattern Evolution

                     Base BFS
                        │
          ┌─────────────┼─────────────┐
          ↓             ↓             ↓
     Traversal      Shortest Path   Components
     (+ order)      (+ distance)    (+ outer loop)
                        │
                        ↓
                 Multi-Source BFS
                 (+ multiple sources)
                        │
                        ↓
                  Level BFS
                 (+ queue.size())
                        │
                        ↓
                    Grid BFS
              (+ coordinates + dirs)

Common Mistakes

1. Marking visited after polling

❌ Wrong:

int node = queue.poll();
visited[node] = true;

This can put the same node into the queue multiple times.

✅ Correct:

visited[neighbor] = true;
queue.offer(neighbor);

Mark it when enqueuing.

2. Using BFS for weighted shortest paths

BFS guarantees shortest paths when every edge has the same cost.

For:

A --1-- B
A --10- C
B --1-- C

BFS is not the correct weighted shortest-path algorithm.

Think:

Unweighted → BFS Non-negative weighted → Dijkstra Negative edges → Bellman-Ford

3. Forgetting disconnected components

This:

bfs(graph, 0);

only explores the component containing 0.

For all components:

for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        bfs(graph, i);
    }
}

4. Confusing level count with distance

The source is at:

distance = 0

Its neighbors are:

distance = 1

Their neighbors:

distance = 2

So be careful with code that increments level after processing a layer.

5. Forgetting grid boundaries

Always validate:

0 <= row < n
0 <= col < m

before accessing:

grid[row][col]

Complexity

For a graph with V vertices and E edges:

Time

O(V + E)

Every vertex and edge is processed at most a constant number of times.

Space

O(V)

for:

queue
visited array
distance array, if used

For a grid with R × C cells:

Time:  O(R × C)
Space: O(R × C)

Recognition Cheat Sheet

If you see…	Think…
Minimum edges	BFS
Unweighted shortest path	BFS
Nearest source	Multi-Source BFS
Spread / infection / fire	Multi-Source BFS
Level-by-level processing	Level BFS
Matrix + directions	Grid BFS
Number of components	BFS + outer loop
Weighted non-negative edges	Dijkstra
Negative edge weights	Bellman-Ford

Earn Premium with Referrals

Pattern Table

Mental Trigger

1. Generic Java BFS Template (Base)

Breadth-First Search

Pattern 1: Basic BFS Traversal

Java Code

What Changed from the Base Template?

Store traversal order

Record each node

Pattern 2: Shortest Path in an Unweighted Graph

Java Code

What Changed from the Base Template?

Replace visited[] with distance[]

Source starts at distance 0

Distance increases by one edge

Pattern 3: Multi-Source BFS

Java Code

What Changed from the Base Template?

Multiple starting nodes

Why does this work?

Pattern 4: Level-Order BFS

Java Code

What Changed from the Base Template?

Capture current level size

Process exactly that level

Pattern 5: Grid BFS

Java Code

Important Note

Example: Shortest Path to Target

What Changed from the Base Template?

Nodes became cells

Neighbors are generated using directions

Added boundary checking

Pattern 6: Connected Components with BFS

Java Code

What Changed from the Base Template?

Add an outer loop

BFS Pattern Evolution

Common Mistakes

1. Marking visited after polling

2. Using BFS for weighted shortest paths

3. Forgetting disconnected components

4. Confusing level count with distance

5. Forgetting grid boundaries

Complexity

Time

Space

Recognition Cheat Sheet

Premium Content

My Private Notes

Replace `visited[]` with `distance[]`