BFS Breadth First Search on Graph in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on a simple graph

What is the output of the BFS traversal starting from node 0 in the given graph?

DSA Java

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer>[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<>();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

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

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int n : adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        g.BFS(0);
    }
}

A [0, 1, 3, 2]

B [0, 1, 2, 3]

C [0, 2, 1, 3]

D [0, 3, 2, 1]

💡 Hint

Remember BFS visits nodes level by level using a queue.

BFS starts at node 0, visits neighbors 1 and 2 in order, then visits neighbor 3 of node 2.

So the order is 0, 1, 2, 3.

❓ Predict Output

intermediate

BFS traversal output on disconnected graph

What is the output of BFS traversal starting from node 1 in this disconnected graph?

DSA Java

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer>[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<>();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

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

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int n : adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

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

        g.BFS(1);
    }
}

A [1, 0]

B [1, 0, 2]

C [1]

D [1, 2]

💡 Hint

BFS only visits nodes reachable from the start node.

Node 1 has no outgoing edges, so BFS visits only node 1.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will occur when running this BFS code?

DSA Java

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer>[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<>();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

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

        while (!queue.isEmpty()) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int n : adj[s]) {
                if (!visited[n]) {
                    queue.add(n);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(3);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 1);

        g.BFS(0);
    }
}

A Infinite loop due to missing visited update

B NullPointerException at queue.poll()

C ArrayIndexOutOfBoundsException

D No error, prints: 0 1 2

💡 Hint

Check if visited nodes are marked before adding to queue.

The code does not mark nodes as visited when adding to the queue, so nodes can be added repeatedly causing infinite loop.

🧠 Conceptual

advanced

BFS traversal order on a cyclic graph

Given a cyclic graph with edges: 0->1, 1->2, 2->0, 2->3, what is the BFS traversal order starting from node 0?

A [0, 2, 1, 3]

B [0, 3, 1, 2]

C [0, 1, 3, 2]

D [0, 1, 2, 3]

💡 Hint

BFS visits neighbors in the order they appear in adjacency list.

Starting at 0, neighbors are 1, then 1's neighbor 2, then 2's neighbor 3.

🚀 Application

expert

Number of nodes visited by BFS in a graph with unreachable nodes

In a graph with 6 nodes and edges: 0->1, 0->2, 1->3, 4->5, how many nodes will BFS visit starting from node 0?

A 4

B 3

C 5

D 6

💡 Hint

BFS visits only nodes reachable from the start node.

From node 0, BFS visits nodes 0,1,2,3. Nodes 4 and 5 are unreachable.

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