Breadth First Search (BFS)

Imagine you're standing in the middle of a city and want to find the nearest hospital.

You wouldn't first travel through one road for 50 kilometers before checking anything nearby. Instead, you'd first check places one road away, then places two roads away, then three roads away, and so on.

That's the basic idea behind Breadth First Search, or BFS.

Breadth First Search is a graph traversal algorithm that explores vertices level by level, visiting all nearby vertices before moving farther away.

BFS is one of the most important algorithms in DSA because it is especially useful for shortest paths in unweighted graphs, level-order exploration, and minimum-step problems.

How BFS Works

Consider this graph:

If we start BFS from 0, we first visit:

Then all of its immediate neighbors:

1, 2

Then the next level:

3, 4, 5

So the traversal is:

0 → 1 → 2 → 3 → 4 → 5

The exact order among nodes at the same level can vary depending on the adjacency-list order.

The important part is:

Level 0 → 0
Level 1 → 1, 2
Level 2 → 3, 4, 5

That's why it's called Breadth First Search.

BFS Uses a Queue

The most important thing to remember about BFS is:

BFS uses a Queue.

A queue follows:

FIFO
First In, First Out

For example:

10 → 20 → 30
↑
Front

10 leaves first because it entered first.

This behavior is exactly what BFS needs to explore nodes level by level.

Why Does BFS Need a Queue?

Let's use:

Start with:

Queue:
[0]

Remove 0.

Its neighbors are 1 and 2:

Queue:
[1, 2]

Remove 1.

Its unvisited neighbors are 3 and 4:

Queue:
[2, 3, 4]

Remove 2.

Then:

Queue:
[3, 4]

Then 3, then 4.

The queue naturally makes BFS process nodes in the order they were discovered.

The BFS Algorithm

The basic BFS process is:

Start with a vertex
        ↓
Mark it as visited
        ↓
Put it into a queue
        ↓
Remove a vertex from the queue
        ↓
Visit its unvisited neighbors
        ↓
Mark them as visited
        ↓
Add them to the queue
        ↓
Repeat until queue is empty

In pseudocode:

BFS(start):

    mark start as visited
    add start to queue

    while queue is not empty:

        node = remove from queue

        process node

        for each neighbor:

            if neighbor is not visited:

                mark neighbor visited
                add neighbor to queue

Why Do We Need `visited[]`?

Graphs can contain cycles.

Consider:

A ─ B
|   |
C ─ D

We can travel:

A → B → D → C → A

If BFS doesn't remember which vertices it has already visited, it could keep adding the same vertices again.

So we use:

boolean[] visited =
    new boolean[vertices];

When we discover a vertex:

visited[neighbor] = true;

This prevents it from being added to the queue repeatedly.

BFS in Java

Let's implement BFS using an adjacency list.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Main {

    static void bfs(
        int start,
        ArrayList<ArrayList<Integer>> graph
    ) {

        boolean[] visited =
            new boolean[graph.size()];

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

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

        while (!queue.isEmpty()) {

            int node = queue.remove();

            System.out.print(node + " ");

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

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    queue.add(neighbor);
                }
            }
        }
    }
}

The most important part is:

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

Then:

while (!queue.isEmpty())

continues processing until every reachable vertex has been explored.

Building the Graph

Suppose our graph is:

We can create the adjacency list:

int vertices = 6;

ArrayList<ArrayList<Integer>> graph =
    new ArrayList<>();

for (int i = 0; i < vertices; i++) {
    graph.add(new ArrayList<>());
}

For an undirected graph:

graph.get(0).add(1);
graph.get(1).add(0);

graph.get(0).add(2);
graph.get(2).add(0);

graph.get(1).add(3);
graph.get(3).add(1);

graph.get(1).add(4);
graph.get(4).add(1);

graph.get(2).add(5);
graph.get(5).add(2);

Then:

bfs(0, graph);

One possible output:

0 1 2 3 4 5

A Complete BFS Program

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Main {

    static void addEdge(
        ArrayList<ArrayList<Integer>> graph,
        int u,
        int v
    ) {

        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    static void bfs(
        int start,
        ArrayList<ArrayList<Integer>> graph
    ) {

        boolean[] visited =
            new boolean[graph.size()];

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

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

        while (!queue.isEmpty()) {

            int node = queue.remove();

            System.out.print(node + " ");

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

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {

        int vertices = 6;

        ArrayList<ArrayList<Integer>> graph =
            new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 1, 4);
        addEdge(graph, 2, 5);

        bfs(0, graph);
    }
}

Output:

0 1 2 3 4 5

Understanding BFS Step by Step

Let's manually execute the algorithm.

Graph:

Start:

Queue = [0]
Visited = {0}

Step 1

Remove 0.

Process → 0

Add 1 and 2.

Queue = [1, 2]
Visited = {0, 1, 2}

Step 2

Remove 1.

Process → 1

Add 3 and 4.

Queue = [2, 3, 4]
Visited = {0, 1, 2, 3, 4}

Step 3

Remove 2.

Process → 2

Add 5.

Queue = [3, 4, 5]
Visited = {0, 1, 2, 3, 4, 5}

Then:

Process → 3
Process → 4
Process → 5

Queue becomes empty.

Traversal is complete.

BFS and Levels

One of the most useful properties of BFS is that it naturally processes a graph in levels.

Consider:

          0
        /   \
       1     2
      / \     \
     3   4     5
    /
   6

BFS gives:

Level 0 → 0
Level 1 → 1, 2
Level 2 → 3, 4, 5
Level 3 → 6

This makes BFS perfect for problems involving:

"How many steps away is this node?"

or:

"Find all nodes at distance K."

BFS for Shortest Path

This is probably the most important application of BFS.

Suppose every edge has the same cost.

A ─ B ─ D
|       |
C ───── E

If we start from A, BFS explores based on the number of edges traveled.

Distance 0:
A

Distance 1:
B, C

Distance 2:
D, E

Therefore, if we want to reach D:

A → B → D

requires:

2 edges

BFS guarantees the shortest number of edges in an unweighted graph.

BFS with a Distance Array

We can explicitly store the distance of every node from the starting vertex.

static void bfs(
    int start,
    ArrayList<ArrayList<Integer>> graph
) {

    int[] distance =
        new int[graph.size()];

    boolean[] visited =
        new boolean[graph.size()];

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

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

    while (!queue.isEmpty()) {

        int node = queue.remove();

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

            if (!visited[neighbor]) {

                visited[neighbor] = true;

                distance[neighbor] =
                    distance[node] + 1;

                queue.add(neighbor);
            }
        }
    }
}

If:

distance[0] = 0

then its direct neighbors have:

distance = 1

their neighbors:

distance = 2

and so on.

Finding the Actual Shortest Path

Sometimes knowing the distance isn't enough.

We may also want to know the actual path.

For example:

A → B → D

We can use a parent[] array.

Whenever we discover a new node:

parent[neighbor] = node;

For example:

parent[B] = A
parent[D] = B

Then we can reconstruct the path backward:

D
↑
B
↑
A

and reverse it:

A → B → D

This technique is extremely common in shortest-path problems.

BFS Level-by-Level Traversal

Sometimes we need to process an entire level at once.

For example:

We can process:

Level 0 → [0]
Level 1 → [1, 2]
Level 2 → [3, 4, 5]

In Java, we can use the queue size to determine the current level:

while (!queue.isEmpty()) {

    int levelSize = queue.size();

    for (int i = 0;
         i < levelSize;
         i++) {

        int node = queue.remove();

        System.out.print(node + " ");

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

            if (!visited[neighbor]) {

                visited[neighbor] = true;

                queue.add(neighbor);
            }
        }
    }

    System.out.println();
}

This produces output such as:

0
1 2
3 4 5

This pattern is extremely useful in level-based problems.

BFS on a Grid

BFS isn't limited to traditional graphs.

A 2D grid can also be treated as a graph.

For example:

S . . #
. # . .
. . . E

Each cell can represent a vertex.

You can move between neighboring cells.

Then BFS can find the shortest path from:

S → E

when each move has equal cost.

This idea is used in:

Maze problems
Grid shortest paths
Robot movement
Game maps
Flood fill
Multi-source BFS

Multi-Source BFS

Normal BFS starts from one source.

But sometimes we have multiple starting points.

For example:

🔥 . . . 🔥
. . . . .
. . . . .

Suppose fire spreads one cell per minute.

We can put all fire cells into the queue initially:

Queue:
[fire1, fire2]

Then BFS expands from both simultaneously.

This is called Multi-Source BFS.

It is useful for problems involving:

Multiple starting points
Fire spreading
Rotting oranges
Nearest source
Distance from multiple locations

BFS for Connected Components

Suppose:

0 ─ 1       3 ─ 4
|             \
2              5

There are two components.

We can run BFS from every unvisited vertex:

for each vertex:

    if not visited:

        BFS(vertex)

        componentCount++

The first BFS explores:

0, 1, 2

The second explores:

3, 4, 5

Therefore:

components = 2

BFS for Bipartite Graphs

BFS can also help determine whether a graph is bipartite.

The idea is to color vertices using two colors.

For example:

Color A → Red
Color B → Blue

When we visit a neighbor:

Current = Red
Neighbor = Blue

If we ever discover that two adjacent vertices require the same color, the graph isn't bipartite.

A common BFS implementation uses:

int[] color =
    new int[vertices];

with values such as:

-1 → Not colored
 0 → Color 0
 1 → Color 1

BFS then alternates colors between adjacent vertices.

BFS vs DFS

This is one of the most important comparisons in DSA.

BFS	DFS
Breadth first	Depth first
Uses Queue	Uses Stack/Recursion
Level by level	Goes deep first
Excellent for unweighted shortest path	Useful for deep exploration
Naturally iterative	Naturally recursive
Good for minimum number of edges	Good for components, cycles, backtracking

Think of them like this:

BFS:

        Start
       /     \
      ↓       ↓
    Near    Near
      ↓       ↓
    Far     Far

while DFS behaves more like:

Start
  ↓
  A
  ↓
  B
  ↓
  C
  ↓
Backtrack

BFS vs Dijkstra

BFS and Dijkstra can both be used for shortest-path problems, but they solve different cases.

BFS

Use BFS when:

Every edge has equal cost

For example:

A ─ B ─ C

Every move costs 1.

Dijkstra

Use Dijkstra when edges have non-negative but potentially different weights:

A --5-- B
|       |
2       10
|       |
C --1-- D

The edge costs aren't all equal.

So:

Unweighted → BFS
Weighted, non-negative → Dijkstra

BFS Complexity

For an adjacency-list representation:

Time Complexity → O(V + E)

Why?

BFS may visit every vertex:

and inspect every edge:

Therefore:

O(V + E)

Space complexity is also:

O(V)

for the queue and visited array in the usual adjacency-list implementation, excluding the graph's own storage.

So remember:

Time  → O(V + E)
Space → O(V)

BFS with an Adjacency Matrix

If we use an adjacency matrix instead of an adjacency list, BFS may need to scan all V possible neighbors for every vertex.

Therefore:

Time → O(V²)

So for sparse graphs:

Adjacency List
      ↓
BFS
      ↓
O(V + E)

is usually preferable.

Common BFS Problems

Once you understand basic BFS, you'll encounter many variations.

1. Shortest Path

Find the minimum number of edges between two vertices.

2. Level Order Traversal

Process nodes one level at a time.

3. Connected Components

Find separate groups in a graph.

4. Multi-Source BFS

Start BFS from multiple sources simultaneously.

5. Bipartite Graph

Color a graph using two colors.

6. Grid Problems

Find the shortest route through a matrix.

7. Minimum Steps

Find the minimum number of moves required to reach a target.

8. Flood Fill

Expand through neighboring cells.

These are all variations of the same fundamental BFS idea.

A Simple Real-Life Example

Imagine a social network:

You
├── Alice
├── Bob
└── Charlie

Their friends:

Alice → David
Bob   → Emma
Charlie → Frank

If you're looking for someone who is closest to you, BFS is a natural approach.

First:

Distance 0:
You

Then:

Distance 1:
Alice
Bob
Charlie

Then:

Distance 2:
David
Emma
Frank

BFS naturally searches outward from you.

The Main Idea

Breadth First Search (BFS) explores a graph level by level.

The fundamental pattern is:

Start
 ↓
Mark visited
 ↓
Put into Queue
 ↓
Remove from Queue
 ↓
Visit unvisited neighbors
 ↓
Add them to Queue
 ↓
Repeat

The most important relationship is:

BFS
 ↓
Queue
 ↓
FIFO
 ↓
Level-by-level exploration

Its most important application is:

Unweighted Graph
       ↓
Shortest Path
       ↓
BFS

And its standard complexity with an adjacency list is:

Time  → O(V + E)
Space → O(V)

Remember these four things:

1. BFS uses a Queue.
2. BFS uses a visited array/set.
3. BFS explores level by level.
4. BFS finds shortest paths in unweighted graphs.

If a DSA problem asks for the minimum number of steps, moves, or edges in an unweighted graph, BFS should immediately come to mind.

How BFS Works

BFS Uses a Queue

Why Does BFS Need a Queue?

The BFS Algorithm

Why Do We Need visited[]?

BFS in Java

Building the Graph

A Complete BFS Program

Understanding BFS Step by Step

Step 1

Step 2

Step 3

BFS and Levels

BFS for Shortest Path

BFS with a Distance Array

Finding the Actual Shortest Path

BFS Level-by-Level Traversal

BFS on a Grid

Multi-Source BFS

BFS for Connected Components

BFS for Bipartite Graphs

BFS vs DFS

BFS vs Dijkstra

BFS

Dijkstra

BFS Complexity

BFS with an Adjacency Matrix

Common BFS Problems

1. Shortest Path

2. Level Order Traversal

3. Connected Components

4. Multi-Source BFS

5. Bipartite Graph

6. Grid Problems

7. Minimum Steps

8. Flood Fill

A Simple Real-Life Example

The Main Idea

Why Do We Need `visited[]`?