BFS - Normal + Level by Level
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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 4 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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.
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 code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Plain BFS | O(V + E) | O(V) |
| Level-by-level BFS | O(V + E) | O(V) |
1Plain BFS
O(V + E)O(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.
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;
}
}class Solution:
def bfs(self, V: int, adj: List[List[int]], start: int) -> List[int]:
order = []
seen = [False] * V
q = deque([start])
seen[start] = True
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if not seen[v]:
seen[v] = True
q.append(v)
return orderclass Solution {
public:
vector<int> bfs(int V, vector<vector<int>>& adj, int start) {
vector<int> order;
vector<bool> seen(V, false);
queue<int> q;
q.push(start);
seen[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u])
if (!seen[v]) { seen[v] = true; q.push(v); }
}
return order;
}
};function bfs(V, adj, start) {
const order = [];
const seen = new Array(V).fill(false);
const q = [start];
let head = 0;
seen[start] = true;
while (head < q.length) {
const u = q[head++];
order.push(u);
for (const v of adj[u])
if (!seen[v]) { seen[v] = true; q.push(v); }
}
return order;
}2Level-by-level BFS
O(V + E)O(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++.
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;
}
}class Solution:
def bfsLevels(self, V: int, adj: List[List[int]], start: int) -> List[List[int]]:
levels = []
seen = [False] * V
q = deque([start])
seen[start] = True
while q:
level = []
for _ in range(len(q)):
u = q.popleft()
level.append(u)
for v in adj[u]:
if not seen[v]:
seen[v] = True
q.append(v)
levels.append(level)
return levelsclass Solution {
public:
vector<vector<int>> bfsLevels(int V, vector<vector<int>>& adj, int start) {
vector<vector<int>> levels;
vector<bool> seen(V, false);
queue<int> q;
q.push(start);
seen[start] = true;
while (!q.empty()) {
vector<int> level;
for (int i = q.size(); i > 0; i--) {
int u = q.front();
q.pop();
level.push_back(u);
for (int v : adj[u])
if (!seen[v]) { seen[v] = true; q.push(v); }
}
levels.push_back(level);
}
return levels;
}
};function bfsLevels(V, adj, start) {
const levels = [];
const seen = new Array(V).fill(false);
let q = [start];
seen[start] = true;
while (q.length > 0) {
const level = [];
const next = [];
for (const u of q) {
level.push(u);
for (const v of adj[u])
if (!seen[v]) { seen[v] = true; next.push(v); }
}
levels.push(level);
q = next;
}
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, Clone Graph, All Paths From Source to Target.
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).