BFS Breadth First Search on Graph in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add the starting node to the queue in BFS.

DSA Java

Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
visited[start] = true;
queue.[1](start);

Drag options to blanks, or click blank then click option'

Aoffer

Benqueue

Cpush

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'push' which is for stacks, not queues.

Using 'enqueue' which is not a Java Queue method.

In Java's Queue interface, 'offer' is the preferred method to add elements to the queue safely.

2fill in blank

medium

Complete the code to dequeue the next node in BFS.

DSA Java

while (!queue.isEmpty()) {
    int current = queue.[1]();
    // process current node
}

Drag options to blanks, or click blank then click option'

AremoveLast

Bpoll

Cpop

Dpeek

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' which is for stacks.

Using 'peek' which does not remove the element.

'poll' removes and returns the head of the queue or returns null if empty, suitable for BFS.

3fill in blank

hard

Fix the error in the adjacency list traversal to check neighbors in BFS.

DSA Java

for (int neighbor : graph.get(current)) {
    if (!visited[[1]]) {
        visited[neighbor] = true;
        queue.offer(neighbor);
    }
}

Drag options to blanks, or click blank then click option'

Aneighbor

Bcurrent

Cgraph

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Checking visited[current] inside the loop over neighbors.

Using graph or queue as index which is invalid.

We must check if the neighbor node is visited, not the current node.

4fill in blank

hard

Fill both blanks to correctly initialize the BFS queue and visited array.

DSA Java

boolean[] visited = new boolean[[1]];
Queue<Integer> queue = new [2]<>();

Drag options to blanks, or click blank then click option'

An

Bm

CLinkedList

DArrayList

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'm' which might be edges count for visited array size.

Using ArrayList for queue which is not a Queue implementation.

The visited array size should be the number of nodes 'n'. The queue is best implemented as a LinkedList.

5fill in blank

hard

Fill all three blanks to complete BFS traversal printing nodes in order.

DSA Java

while (!queue.isEmpty()) {
    int current = queue.[1]();
    System.out.print(current + " ");
    for (int neighbor : graph.get(current)) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            queue.[2](neighbor);
        }
    }
}

// Output example: [3]

Drag options to blanks, or click blank then click option'

Apoll

Boffer

Cadd

D1 2 3 4 5

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'add' instead of 'offer' which works but 'offer' is preferred.

Using 'peek' instead of 'poll' which does not remove the element.

'poll' removes the head of the queue, 'offer' adds neighbors, and the output shows BFS order of nodes.

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