BFS Breadth First Search on Graph in DSA Java - Time & Space Complexity

Time Complexity: BFS Breadth First Search on Graph

O(n + m)

Understanding Time Complexity

We want to understand how the time needed to explore a graph grows as the graph gets bigger when using BFS.

Specifically, how does BFS's work change with more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}
    

This code explores all nodes reachable from a start node using BFS, visiting neighbors level by level.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs as long as there are nodes to visit, and inside it, the for loop visits all neighbors of the current node.
• How many times: Each node is visited once, and each edge is checked once when exploring neighbors.

How Execution Grows With Input

As the graph grows, BFS visits every node and edge once.

Input Size (n nodes, m edges)	Approx. Operations
10 nodes, 15 edges	About 10 node visits + 15 edge checks = 25 operations
100 nodes, 200 edges	About 100 + 200 = 300 operations
1000 nodes, 5000 edges	About 1000 + 5000 = 6000 operations

Pattern observation: The work grows roughly in direct proportion to the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + m)

This means BFS takes time proportional to the total nodes plus edges in the graph.

Common Mistake

[X] Wrong: "BFS always takes time proportional to n squared because it checks all pairs of nodes."

[OK] Correct: BFS only checks edges that actually exist, not all pairs. So it depends on edges, not all possible pairs.

Interview Connect

Understanding BFS time complexity helps you explain how graph searches scale, a key skill in many coding problems.

Self-Check

"What if the graph is represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"

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