BFS Breadth First Search on Graph in DSA Java

Mental Model

BFS explores all neighbors of a node before moving to the next level, like spreading out evenly layer by layer.

Analogy: Imagine you are in a building and want to visit every room floor by floor, starting from the entrance. You first check all rooms on the first floor, then all rooms on the second floor, and so on.

Graph nodes connected:
  1
 / \
2   3
|    |
4    5

Start at node 1, explore neighbors 2 and 3 first, then their neighbors.

Dry Run Walkthrough

Input: Graph: 1 connected to 2 and 3; 2 connected to 4; 3 connected to 5; start BFS from node 1

Goal: Visit all nodes in order of their distance from node 1 using BFS

Step 1: Start BFS at node 1, enqueue it

Queue: [1]
Visited: {1}

Why: We begin from the start node and mark it visited to avoid repeats

Step 2: Dequeue node 1, enqueue its neighbors 2 and 3

Queue: [2, 3]
Visited: {1, 2, 3}

Why: Explore all neighbors of node 1 before moving deeper

Step 3: Dequeue node 2, enqueue its neighbor 4

Queue: [3, 4]
Visited: {1, 2, 3, 4}

Why: Continue exploring neighbors level by level

Step 4: Dequeue node 3, enqueue its neighbor 5

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

Why: Visit all neighbors of node 3 after node 2

Step 5: Dequeue node 4, no new neighbors to enqueue

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

Why: Node 4 has no unvisited neighbors

Step 6: Dequeue node 5, no new neighbors to enqueue

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

Why: Node 5 has no unvisited neighbors, BFS ends

Result:

Visited order: 1 -> 2 -> 3 -> 4 -> 5

Annotated Code

DSA Java

import java.util.*;

class Graph {
    private final int vertices;
    private final List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src); // undirected graph
    }

    public List<Integer> bfs(int start) {
        boolean[] visited = new boolean[vertices];
        List<Integer> order = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

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

        while (!queue.isEmpty()) {
            int current = queue.poll(); // dequeue
            order.add(current); // visit node

            for (int neighbor : adjList.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // mark visited
                    queue.add(neighbor); // enqueue neighbor
                }
            }
        }
        return order;
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(6); // nodes 0 to 5
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);

        List<Integer> bfsOrder = graph.bfs(1);
        for (int node : bfsOrder) {
            System.out.print(node + " -> ");
        }
        System.out.print("null\n");
    }
}

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

Initialize BFS by marking start node visited and enqueue it

int current = queue.poll(); // dequeue order.add(current); // visit node

Dequeue node to visit it and record visitation order

for (int neighbor : adjList.get(current)) { if (!visited[neighbor]) { visited[neighbor] = true; // mark visited queue.add(neighbor); // enqueue neighbor } }

Enqueue all unvisited neighbors to explore next

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(V + E) because BFS visits every vertex and edge once

Space: O(V) for the queue and visited array to track nodes

vs Alternative: Compared to DFS which uses a stack and explores depth first, BFS uses a queue and explores breadth first, making BFS better for shortest path in unweighted graphs

Edge Cases

Empty graph (no nodes)

BFS returns empty list as there are no nodes to visit

DSA Java

visited[start] = true; // mark start visited

Start node with no edges

BFS visits only the start node and stops

DSA Java

while (!queue.isEmpty()) { ... }

Graph with disconnected components

BFS visits only nodes reachable from start node

DSA Java

if (!visited[neighbor]) { ... }

When to Use This Pattern

When you need to explore nodes layer by layer or find shortest paths in unweighted graphs, BFS is the pattern to use because it visits nodes in order of their distance from the start.

Common Mistakes

Mistake: Forgetting to mark nodes as visited before enqueueing causes repeated visits and infinite loops.
Fix: Mark nodes as visited immediately when enqueueing to prevent revisiting.

Summary

BFS visits all nodes in a graph level by level starting from a given node.

Use BFS when you want to find shortest paths or explore nodes in order of distance.

The key insight is to use a queue to explore neighbors before moving deeper.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A priority queue

B. A stack data structure

C. A queue data structure

D. A hash map

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, visiting all neighbors before moving deeper.

2. Step 2: Identify the data structure used

   To maintain the order of visiting nodes level-wise, BFS uses a queue which follows FIFO (First In First Out).

3. Final Answer:

   A queue data structure -> Option C

4. Quick Check:

   BFS uses queue = A [OK]

Hint: BFS uses FIFO order, so it needs a queue [OK]

Common Mistakes:

• Confusing BFS with DFS which uses a stack
• Thinking BFS uses a priority queue
• Assuming BFS uses a hash map to order nodes

2. Which of the following is the correct Java syntax to add a node to the BFS queue named queue?

easy

A. queue.push(node);

B. queue.add(node);

C. queue.enqueue(node);

D. queue.insert(node);

Solution

1. Step 1: Identify Java Queue method to add elements

   Java's Queue interface uses add() or offer() to insert elements.

2. Step 2: Match given options with Java syntax

   push() is for stacks, enqueue() and insert() are not standard Queue methods in Java.

3. Final Answer:

   queue.add(node); -> Option B

4. Quick Check:

   Java Queue add method = add() [OK]

Hint: Java Queue uses add() to insert elements [OK]

Common Mistakes:

• Using push() which is for stacks
• Using enqueue() which is not a Java Queue method
• Using insert() which does not exist for Queue

3. Consider the following Java code snippet for BFS on a graph starting from node 0:

import java.util.*;

public class GraphBFS {
    public static void bfs(int start, Map graph) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.add(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Map graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(2));
        graph.put(2, Arrays.asList(0, 3));
        graph.put(3, Arrays.asList(3));
        bfs(0, graph);
    }
}

What is the output printed by this program?

medium

A. 0 1 2 3

B. 0 2 1 3

C. 0 1 3 2

D. 0 3 2 1

Solution

1. Step 1: Start BFS from node 0 and enqueue neighbors

   Start with queue=[0], visited={0}. Dequeue 0, print 0. Enqueue neighbors 1 and 2, visited={0,1,2}.

2. Step 2: Dequeue next nodes and enqueue their neighbors

   Dequeue 1, print 1. Neighbor 2 already visited, skip. Dequeue 2, print 2. Neighbors 0 and 3; 0 visited, enqueue 3, visited={0,1,2,3}. Dequeue 3, print 3. Neighbor 3 already visited.

3. Final Answer:

   0 1 2 3 -> Option A

4. Quick Check:

   BFS order from 0 = 0 1 2 3 [OK]

Hint: Follow queue order and mark visited nodes [OK]

Common Mistakes:

• Visiting nodes out of BFS order
• Not marking visited nodes causing repeats
• Confusing BFS with DFS order

4. The following BFS code snippet has a bug. What is the error?

Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(start);

while (!queue.isEmpty()) {
    int node = queue.poll();
    System.out.print(node + " ");
    for (int neighbor : graph.get(node)) {
        if (!visited.contains(neighbor)) {
            queue.add(neighbor);
        }
    }
}

medium

A. Using poll() instead of peek() on queue

B. Not initializing the queue

C. Not checking if queue is empty before polling

D. Missing adding start node to visited set

Solution

1. Step 1: Check visited set usage

   The code adds neighbors to queue only if not visited, but never adds nodes to visited set after enqueueing.

2. Step 2: Identify missing visited addition for start node

   Start node is added to queue but not to visited set, so it may be revisited or cause infinite loops.

3. Final Answer:

   Missing adding start node to visited set -> Option D

4. Quick Check:

   Visited set must include start node [OK]

Hint: Always add nodes to visited when enqueued [OK]

Common Mistakes:

• Forgetting to add start node to visited
• Adding to visited only after dequeueing
• Using peek() instead of poll() incorrectly

5. You want to find the shortest path length from node 0 to node 4 in an unweighted graph using BFS. Which modification to the BFS algorithm below will correctly compute the shortest distance?

Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
Map distance = new HashMap<>();
queue.add(0);
visited.add(0);
distance.put(0, 0);

while (!queue.isEmpty()) {
    int node = queue.poll();
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            queue.add(neighbor);
            visited.add(neighbor);
            // What to add here?
        }
    }
}
System.out.println(distance.getOrDefault(4, -1));

hard

A. distance.put(neighbor, distance.get(node) + 1);

B. distance.put(neighbor, distance.get(neighbor) + 1);

C. distance.put(neighbor, 1);

D. distance.put(neighbor, distance.get(node));

Solution

1. Step 1: Understand BFS for shortest path in unweighted graph

   BFS visits nodes in order of increasing distance from start. Distance to neighbor = distance to current node + 1.

2. Step 2: Assign correct distance value when visiting neighbor

   Set neighbor's distance as current node's distance + 1 to reflect shortest path length.

3. Final Answer:

   distance.put(neighbor, distance.get(node) + 1); -> Option A

4. Quick Check:

   Neighbor distance = current + 1 [OK]

Hint: Distance to neighbor = current node distance + 1 [OK]

Common Mistakes:

• Using neighbor's old distance instead of current node's
• Setting distance always to 1 ignoring path length
• Not updating distance map at all