BFS Breadth First Search on Graph in DSA Java - Execution Trace

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Mark source as visited

↓

Add source to queue

↓

While queue not empty

↓

Dequeue node

↓

Visit all unvisited neighbors

↓

Mark neighbors visited & enqueue

↓

Repeat until queue empty

↓

Traversal complete

BFS starts at a node, visits neighbors level by level using a queue, marking nodes visited to avoid repeats.

Execution Sample

DSA Java

Queue<Node> queue = new LinkedList<>();
Set<Node> visited = new HashSet<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
  Node current = queue.poll();
  for (Node n : current.neighbors) {
    if (!visited.contains(n)) {
      visited.add(n);
      queue.add(n);
    }
  }
}

This code performs BFS on a graph starting from 'start' node, visiting nodes level by level.

Execution Table

Step	Current Node	Visited Set	Queue Contents	Action	Graph State
1	A	[A]	[A]	Start BFS: mark A visited, enqueue A	A---B---C | | | D---E---F
2	A	[A]	[B, D]	Dequeue A; enqueue unvisited neighbors B, D	A---B---C | | | D---E---F
3	B	[A,B,D]	[D, C, E]	Dequeue B; enqueue unvisited neighbors C, E	A---B---C | | | D---E---F
4	D	[A,B,D,C,E]	[C, E]	Dequeue D; enqueue unvisited neighbor E (already visited, skip)	A---B---C | | | D---E---F
5	C	[A,B,D,C,E]	[E, F]	Dequeue C; enqueue unvisited neighbor F	A---B---C | | | D---E---F
6	E	[A,B,D,C,E,F]	[F]	Dequeue E; neighbors B, D, F visited, skip	A---B---C | | | D---E---F
7	F	[A,B,D,C,E,F]	[]	Dequeue F; neighbors C, E visited, skip	A---B---C | | | D---E---F
8	-	[A,B,C,D,E,F]	[]	Queue empty, BFS complete	A---B---C | | | D---E---F

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Current Node	-	A	B	D	C	E	F	-	-
Visited Set	{}	{A}	{A,B,D}	{A,B,D,C,E}	{A,B,D,C,E}	{A,B,D,C,E,F}	{A,B,D,C,E,F}	{A,B,D,C,E,F}	{A,B,D,C,E,F}
Queue	[]	[A]	[B, D]	[D, C, E]	[C, E]	[E, F]	[F]	[]	[]

Key Moments - 3 Insights

Why do we mark nodes as visited before adding them to the queue?

Marking nodes visited before enqueueing (see Step 2 and Step 3 in execution_table) prevents adding the same node multiple times, avoiding repeated visits and infinite loops.

Why does BFS use a queue instead of a stack?

BFS uses a queue (FIFO) to explore nodes level by level, ensuring neighbors are visited in order of distance from the start. Using a stack would change the order to depth-first.

What happens if the graph has disconnected parts?

BFS starting from one node only visits nodes reachable from it. Disconnected parts remain unvisited unless BFS is restarted from those nodes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what nodes are in the queue?

A [C, E]

B [B, D]

C [D, C, E]

D [E, F]

💡 Hint

Check the 'Queue Contents' column at Step 3 in execution_table

At which step does the BFS visit node F for the first time?

A Step 7

B Step 6

C Step 5

D Step 8

💡 Hint

Look at the 'Current Node' column and 'Action' at Step 5 in execution_table

If node C was not connected to node F, what would happen to the queue after Step 5?

A Queue would contain [E]

B Queue would be empty

C Queue would contain [F]

D Queue would contain [C, E]

💡 Hint

Refer to the queue changes in execution_table and consider neighbors enqueued

Concept Snapshot

BFS (Breadth First Search) explores graph nodes level by level.
Uses a queue to track nodes to visit next.
Marks nodes visited when enqueued to avoid repeats.
Stops when queue is empty (all reachable nodes visited).
Good for shortest path in unweighted graphs.
Traversal order depends on graph structure and start node.

Full Transcript

Breadth First Search (BFS) starts at a chosen node and explores all its neighbors before moving to the next level neighbors. It uses a queue to keep track of nodes to visit next and a visited set to avoid revisiting nodes. At each step, BFS dequeues a node, visits its unvisited neighbors by marking them visited and enqueueing them. This process repeats until the queue is empty, meaning all reachable nodes have been visited. BFS is useful for finding shortest paths in unweighted graphs and exploring nodes in layers. The execution table shows the queue and visited set changes step by step, helping visualize the traversal order and how BFS progresses through the graph.

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