Why should you care?
In the previous article, we learned DFS (Depth-First Search).
DFS explores a graph by going as deep as possible before backtracking.
But sometimes we don't want to go deep.
We want to explore the graph level by level.
That's where Breadth-First Search (BFS) comes in.
BFS is useful for:
- Finding shortest paths in unweighted graphs
- Social-network connections
- Finding nearby locations
- Network broadcasting
- Web crawling
- Level-order tree traversal
- Maze solving
- Recommendation systems
- Finding the minimum number of steps between states
The key idea is simple:
Explore everything nearby before going farther away.
The Problem
Consider this graph:
```text id="q7m2ds"
A
/ \
B C
/ \ \
D E F
Starting from `A`, we want to visit every node.
DFS might visit:
```text id="qk5zq0"
A → B → D → E → C → F
BFS takes a different approach.
It first visits nodes at distance 1:
```text id="7lq3h0"
A
↓
B, C
Then nodes at distance 2:
```text id="p3u7qy"
D, E, F
So the traversal becomes:
```text id="u1z4gf"
A → B → C → D → E → F
The exact order can depend on how neighbors are stored, but the **level-by-level behavior** is the important part.
---
## The Concept
BFS stands for:
> **Breadth-First Search**
It explores a graph in layers.
The basic process is:
```text id="q7pv0r"
Start
↓
Visit starting node
↓
Add its neighbors to a queue
↓
Remove the first node from queue
↓
Visit its unvisited neighbors
↓
Repeat
The most important data structure used by BFS is a:
```text id="l1z3j4"
Queue
This gives BFS its characteristic behavior:
```text id="q4o8pf"
First In → First Out
The nodes discovered first are processed first.
Simple Explanation
Imagine a fire spreading through a building.
At time:
```text id="6s2c4z"
0
only the starting room is affected.
At time:
```text id="0v6xqv"
1
the fire reaches all directly connected rooms.
At time:
```text id="6j0z9f"
2
it reaches rooms connected to those rooms.
And so on.
The spread happens in **layers**:
```text id="h6j5r7"
Level 0 → Start
Level 1 → Direct neighbors
Level 2 → Neighbors of neighbors
Level 3 → Next layer
...
BFS explores a graph in exactly this way.
Real-world Analogy
Imagine you're looking for a friend in a social network.
You start with:
```text id="l3g7tc"
You
First, check your direct friends:
```text id="q1y4bd"
You
↓
Your friends
If you don't find the person, check your friends' friends:
```text id="m2z9ab"
You
↓
Friends
↓
Friends of friends
Then:
```text id="n0g1wv"
Friends of friends of friends
You're expanding outward one connection at a time.
This is exactly what BFS does.
Code Example
Let's implement BFS in Java using an adjacency list.
```java id="8g8w2n"
public static void bfs(
String start,
Map> graph) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
String node = queue.poll();
System.out.println(node);
for (String neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
Example graph:
```java id="7o6g8c"
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D", "E"));
graph.put("C", Arrays.asList("A", "F"));
graph.put("D", Arrays.asList("B"));
graph.put("E", Arrays.asList("B"));
graph.put("F", Arrays.asList("C"));
Run BFS:
```java id="r6c8d4"
bfs("A", graph);
Possible output:
```text id="j0l9pp"
A
B
C
D
E
F
Understanding the Code
The first important structure is:
```java id="i8xq8q"
Queue queue = new LinkedList<>();
The queue controls the order in which nodes are processed.
We start with:
```java id="m7o6j5"
queue.add(start);
Suppose:
```text id="w4m8cw"
start = A
The queue contains:
```text id="4u2o5r"
[A]
We remove A:
```java id="f5u0fa"
String node = queue.poll();
Now inspect its neighbors:
```text id="a8o9er"
B
C
Add them to the queue:
```text id="d7r5mw"
[B, C]
Remove `B`:
```text id="f6x4wz"
[C]
B's unvisited neighbors are:
```text id="o8w3vl"
D
E
Add them:
```text id="w1d0g6"
[C, D, E]
Now process C.
Its neighbor:
```text id="u8s4dz"
F
gets added:
```text id="y7q2qm"
[D, E, F]
Eventually:
```text id="u4y8tw"
D → E → F
are processed.
Therefore:
```text id="pr0n7m"
A → B → C → D → E → F
Why Do We Need visited?
Graphs can contain cycles.
Consider:
```text id="q6b3f7"
A → B
↑ ↓
└───C
If we don't track visited nodes:
```text id="qf7z8p"
A → B → C → A → B → C → ...
The algorithm could continue forever.
Therefore:
```java id="2l6w3s"
Set visited
keeps track of nodes that have already been discovered.
An important detail is that we mark a node as visited **when we add it to the queue**, rather than waiting until we remove it.
This prevents the same node from being added multiple times through different paths.
---
## BFS and Shortest Path
One of the most important applications of BFS is finding the **shortest path in an unweighted graph**.
Consider:
```text id="0i7j56"
A ─ B ─ D
\ \
C ─ E
Suppose we want the shortest path from A to E.
BFS explores by distance:
```text id="x4m8c4"
Distance 0:
A
Distance 1:
B, C
Distance 2:
D, E
When BFS reaches `E`, it has found the minimum number of edges needed to reach it.
This works because BFS explores nodes in increasing distance from the starting node.
---
## Finding the Actual Shortest Path
BFS can be extended to store each node's parent.
For example:
```java id="j8d4s5"
Map<String, String> parent = new HashMap<>();
When discovering a new node:
```java id="c1p9s2"
parent.put(neighbor, node);
Suppose:
```text id="g6v7mc"
parent[E] = C
parent[C] = A
We can reconstruct:
```text id="1w4s3r"
E
↑
C
↑
A
Therefore:
```text id="2v0k2p"
A → C → E
is the path.
This technique is widely used in shortest-path problems.
BFS on a Tree
BFS is also called Level-Order Traversal when applied to a tree.
Consider:
```text id="6e9q7r"
A
/ \
B C
/ \ \
D E F
BFS visits:
```text id="f1s9x0"
Level 0 → A
Level 1 → B C
Level 2 → D E F
Traversal:
```text id="c7d3n4"
A → B → C → D → E → F
This is useful when you need to process a tree level by level.
---
## Time Complexity
For a graph represented using an adjacency list:
```text id="q5m6g2"
O(V + E)
where:
```text id="6z9c4q"
V = number of vertices
E = number of edges
Why?
BFS visits each reachable vertex at most once:
```text id="2a5j3y"
O(V)
It also examines each relevant edge:
```text id="4k7t9r"
O(E)
Therefore:
```text id="q8s0j1"
O(V + E)
This is the same asymptotic complexity as DFS.
The difference isn't primarily speed.
It is how the graph is explored.
Space Complexity
BFS needs:
```text id="0o7j1h"
Visited set → O(V)
and a queue.
In the worst case, the queue can contain:
```text id="0k1z7e"
O(V)
vertices.
Therefore:
```text id="9u0f1p"
Space = O(V)
in the worst case.
This is an important difference from DFS in terms of practical memory behavior.
A graph with a very wide level can cause BFS's queue to become large.
---
## Common Mistakes
### Mistake 1: Using a Stack instead of a Queue
BFS requires:
```text id="2qj9tx"
Queue
not:
```text id="8n9w2v"
Stack
A stack gives:
```text id="7j5z6m"
Last In → First Out
which naturally leads toward DFS behavior.
Remember:
```text id="0r4l9g"
DFS → Stack
BFS → Queue
---
### Mistake 2: Marking nodes as visited too late
Consider:
```text id="r5x7m3"
A
/ \
B C
\ /
D
Both B and C can discover D.
If D isn't marked visited until it is removed from the queue, it could be inserted multiple times.
Instead:
```java id="6t0d8h"
visited.add(neighbor);
queue.add(neighbor);
Mark it when it is discovered.
---
### Mistake 3: Assuming BFS always finds the shortest path
BFS guarantees a shortest path in terms of the **number of edges** when the graph is unweighted.
But consider weighted edges:
```text id="5m8n1f"
A ──1── B
\ /
10 1
\ /
C
The path with fewer edges isn't necessarily the path with the smallest total weight.
For weighted shortest-path problems, algorithms such as:
```text id="5y5f3q"
Dijkstra's Algorithm
Bellman-Ford
may be appropriate depending on the graph.
---
### Mistake 4: Forgetting disconnected components
Suppose:
```text id="4tdm7v"
A ─ B ─ C
D ─ E
Starting BFS from A only reaches:
```text id="98s0jv"
A, B, C
It won't automatically reach `D` and `E`.
If you need to traverse the entire graph, you can run BFS from every unvisited vertex.
---
### Mistake 5: Assuming BFS order is always identical
Neighbor ordering affects traversal order.
For example:
```text id="1x7y9m"
A → B, C
could produce:
```text id="ux9m5s"
A B C
while a different adjacency ordering could produce:
```text id="x3w4s8"
A C B
The important property is that nodes are processed according to their distance from the starting node.
Advanced Notes
1. BFS Using an ArrayDeque
In Java, ArrayDeque is generally a better choice for a queue than the legacy Stack class.
For example:
```java id="n6n3d1"
Queue queue = new ArrayDeque<>();
queue.add(start);
while (!queue.isEmpty()) {
String node = queue.poll();
// process node
}
This provides efficient queue operations.
---
### 2. BFS with Distance
We can store the distance from the starting node.
```java id="8j5t1k"
Map<String, Integer> distance = new HashMap<>();
distance.put(start, 0);
When discovering a neighbor:
```java id="r0t7hy"
distance.put(
neighbor,
distance.get(node) + 1
);
Now:
```text id="q6n7b5"
distance[X]
tells us how many edges are required to reach X.
This is extremely useful for shortest-path problems.
3. Multi-Source BFS
BFS doesn't have to start with one node.
Suppose several locations are sources:
```text id="9m5w3k"
A
C
F
We can put all of them into the queue initially:
```text id="q4r9c2"
[A, C, F]
Then perform normal BFS.
This is called Multi-Source BFS.
It can solve problems such as:
- Nearest facility
- Spread simulation
- Multiple starting points
- Distance to the nearest source
4. BFS on a Grid
A 2D grid can be treated as a graph.
For example:
```text id="h8m4p1"
. . .
. # .
. . .
Each cell can represent a vertex.
Neighbors are typically:
```text id="e4g9z6"
up
down
left
right
BFS can then find the shortest path from one cell to another.
This is common in:
- Maze problems
- Grid games
- Robot navigation
- Pathfinding problems
5. Bipartite Graph Detection
BFS can be used to determine whether a graph is bipartite.
A common technique is to assign alternating colors:
```text id="j3x8v5"
A → Color 0
Neighbors → Color 1
Their neighbors → Color 0
If an edge connects two nodes that have the same color, the graph is not bipartite.
This demonstrates how BFS can do much more than simple traversal.
---
### 6. BFS vs DFS
This is the most important comparison.
| Feature | BFS | DFS |
| --------------------------------- | ---------------------- | -------------------- |
| Strategy | Level by level | Depth first |
| Main structure | Queue | Stack |
| Shortest path in unweighted graph | Yes | Not guaranteed |
| Typical use | Levels, shortest paths | Cycles, backtracking |
| Time | O(V + E) | O(V + E) |
| Space | O(V) | O(V) |
The algorithms have the same asymptotic graph traversal complexity, but their behavior is fundamentally different.
---
## The Bigger Picture
BFS connects several concepts we've already learned.
### Queues
We previously learned:
```text id="o0a5b9"
Queue
↓
FIFO
BFS is one of the most important practical applications of a queue.
```text id="1n6j6r"
BFS
↓
Queue
↓
Level-by-level exploration
---
### DFS
We just learned:
```text id="j4r7q2"
DFS → Deep first
BFS gives us the complementary strategy:
```text id="1l9x3v"
BFS → Broad first
Together, they form the two fundamental graph traversal techniques.
---
### Graphs
Our Graph article introduced:
```text id="d7v2q9"
Vertices
+
Edges
BFS gives us a systematic way to navigate those relationships.
```text id="1q6y5w"
Graph
↓
BFS
↓
Traversal
↓
Shortest paths / levels / connectivity
---
### Big-O
From our Big-O article:
```text id="j2g0s7"
BFS = O(V + E)
This demonstrates why graph algorithms are often analyzed in terms of both vertices and edges.
Binary Search
Binary Search taught us to reduce the search space intelligently.
BFS uses a different strategy.
Instead of repeatedly cutting the search space in half, BFS expands outward by distance:
```text id="x5t8w4"
Distance 0
↓
Distance 1
↓
Distance 2
↓
Distance 3
The goal is not the same, but both algorithms demonstrate an important principle:
> **Choose an exploration strategy that matches the structure of the problem.**
---
## The Most Important Mental Model
Don't think of BFS as:
> "DFS but with a queue."
Think:
> **"Explore everything at the current distance before moving farther away."**
Visualize:
```text id="0z2j8q"
A
/ \
B C
/ \ \
D E F
BFS moves:
```text id="8x4g7p"
Level 0:
A
Level 1:
B C
Level 2:
D E F
So:
```text id="z8c5h2"
A → B → C → D → E → F
This is why BFS naturally solves shortest-path problems in unweighted graphs.
If every edge represents one unit of distance, BFS discovers:
```text id="0t5y1c"
closest nodes first
---
## Summary
Breadth-First Search is a graph traversal algorithm that explores nodes **level by level**.
The basic process is:
```text id="w0r7kp"
Start
↓
Queue
↓
Process first node
↓
Add unvisited neighbors
↓
Process next node
↓
Repeat
Key points:
- BFS uses a queue.
- It explores nodes according to their distance from the starting point.
- A visited set prevents repeated processing.
- BFS runs in
O(V + E)with an adjacency-list graph. - Its additional space can be
O(V). - BFS finds shortest paths in unweighted graphs.
- It can perform level-order tree traversal.
- It can be adapted for grids, multi-source problems, and bipartite detection.
- BFS and DFS have the same typical graph traversal complexity but explore the graph differently.
The fundamental comparison is:
```text id="m7y9s4"
DFS
↓
Go deep
↓
Stack
↓
Backtrack
BFS
↓
Go wide
↓
Queue
↓
Next level
Top comments (0)