BFS - Normal + Level by Level

Easy Graphs BFS / DFS Basics

BFS - Normal + Level by Level is a easy graphs problem solved with the bfs / dfs basics pattern. The best approach, level-by-level bfs, runs in O(V + E) time and O(V) space. Below are 2 approaches in Java, from plain bfs up.

Problem

Breadth-first search explores a graph in rings: first the start node, then everything one edge away, then two edges away, and so on. Learn both the plain version and the level-by-level version; most BFS problems use one of them.

Examples

Example 1

Input: adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, start = 0
Output: order [0, 1, 2, 3]; levels [[0], [1, 2], [3]]

Example 2

Input: adj = {0: [1], 1: [0], 2: []}, start = 0
Output: order [0, 1]
Why: Node 2 is unreachable from 0.

Constraints

V vertices, E edges; the adjacency list is the usual input.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Plain BFS	`O(V + E)`	`O(V)`
Level-by-level BFS	`O(V + E)`	`O(V)`

1Plain BFS

TimeO(V + E)

SpaceO(V)

Start from the source, visit its neighbours, then their neighbours, using a FIFO queue. Nodes come out in order of their distance (in edges) from the source.

visited[start] = true; queue = [start].
Poll u, record it, and enqueue each unvisited neighbour, marking it visited.

Java

class Solution {
    public List<Integer> bfs(int V, List<List<Integer>> adj, int start) {
        List<Integer> order = new ArrayList<>();
        boolean[] seen = new boolean[V];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        seen[start] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : adj.get(u))
                if (!seen[v]) { seen[v] = true; q.add(v); }
        }
        return order;
    }
}

2Level-by-level BFS

TimeO(V + E)

SpaceO(V)

Same traversal, but process the queue one level at a time by reading its size first. Each level is the set of nodes at exactly that distance. This version powers shortest paths in unweighted graphs, rotting oranges and tree level order.

While the queue is not empty: size = q.size().
Poll size nodes into the current level, enqueueing unvisited neighbours.
Append the level; distance++.

Java

class Solution {
    public List<List<Integer>> bfsLevels(int V, List<List<Integer>> adj, int start) {
        List<List<Integer>> levels = new ArrayList<>();
        boolean[] seen = new boolean[V];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        seen[start] = true;
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = q.size(); i > 0; i--) {
                int u = q.poll();
                level.add(u);
                for (int v : adj.get(u))
                    if (!seen[v]) { seen[v] = true; q.add(v); }
            }
            levels.add(level);
        }
        return levels;
    }
}

Edge cases to test

Disconnected graph (loop over all start nodes)
Marking visited on dequeue instead of enqueue (nodes get added twice)

Hints

Hint 1

Mark a node visited when you put it in the queue, not when you take it out.

Hint 2

For level by level, read q.size() at the start of each level.

FAQ

What is the best time complexity for BFS - Normal + Level by Level?

Level-by-level BFS runs in O(V + E) time and O(V) extra space.

Which pattern does BFS - Normal + Level by Level use?

It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: DFS - Recursive + Iterative.

Is there a brute force solution for BFS - Normal + Level by Level?

Yes. Plain BFS takes O(V + E) time and O(V) space. Start from the source, visit its neighbours, then their neighbours, using a FIFO queue.

Which edge cases should I test for BFS - Normal + Level by Level?

Disconnected graph (loop over all start nodes); Marking visited on dequeue instead of enqueue (nodes get added twice).