BFS Breadth First Search on Graph in DSA Java - Build from Scratch

BFS Breadth First Search on Graph

📖 Scenario: You are working with a simple network of connected places. You want to explore all places starting from one place, visiting neighbors first before going deeper. This helps in finding the shortest path or checking connectivity.

🎯 Goal: Build a Java program that performs Breadth First Search (BFS) on a graph represented by an adjacency list. You will create the graph, set a starting point, run BFS, and print the order of visited nodes.

📋 What You'll Learn

Create a graph using a HashMap with Integer keys and List values

Add edges to represent connections between nodes

Use a Queue to implement BFS

Keep track of visited nodes using a boolean array

Print the order of nodes visited by BFS

💡 Why This Matters

🌍 Real World

BFS is used in social networks to find friends of friends, in GPS to find shortest routes, and in web crawlers to explore websites level by level.

💼 Career

Understanding BFS is essential for software engineers working on search algorithms, network analysis, and solving problems involving shortest paths or connectivity.

1

Create the graph data structure

Create a HashMap called graph with keys of type Integer and values of type List<Integer>. Add these edges exactly: 1 -> 2, 3, 2 -> 4, 3 -> 4, 5, 4 -> 6, 5 -> 6, 6 -> (no edges).

DSA Java

// Your code here to create the graph and add edges

Hint

Use HashMap<> for the graph and Arrays.asList(...) to add neighbors.

2

Set up BFS helper variables

Add an integer variable startNode and set it to 1. Create a boolean array called visited of size 7 (to cover nodes 1 to 6) and initialize all values to false. Also create a Queue<Integer> called queue using LinkedList<>.

DSA Java

import java.util.*;

public class BFSGraph {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4));
        graph.put(3, Arrays.asList(4, 5));
        graph.put(4, Arrays.asList(6));
        graph.put(5, Arrays.asList(6));
        graph.put(6, new ArrayList());

        // Your code here to create startNode, visited array, and queue
    }
}

Hint

Remember to size the visited array to 7 to include node 6 (index 6).

3

Implement BFS traversal logic

Add code to mark startNode as visited, add it to queue, then use a while loop to process nodes until queue is empty. Inside the loop, remove the front node, then for each neighbor in graph.get(currentNode), if not visited, mark visited and add to queue. Store the order of visited nodes in a List<Integer> called order.

DSA Java

import java.util.*;

public class BFSGraph {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4));
        graph.put(3, Arrays.asList(4, 5));
        graph.put(4, Arrays.asList(6));
        graph.put(5, Arrays.asList(6));
        graph.put(6, new ArrayList());

        int startNode = 1;
        boolean[] visited = new boolean[7];
        Queue queue = new LinkedList();

        // Your code here to implement BFS and store visited order
    }
}

Hint

Use a while loop to process nodes in the queue and a for-each loop to visit neighbors.

4

Print the BFS traversal order

Print the order list using System.out.println(order); to show the order in which nodes were visited by BFS.

DSA Java

import java.util.*;

public class BFSGraph {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4));
        graph.put(3, Arrays.asList(4, 5));
        graph.put(4, Arrays.asList(6));
        graph.put(5, Arrays.asList(6));
        graph.put(6, new ArrayList());

        int startNode = 1;
        boolean[] visited = new boolean[7];
        Queue queue = new LinkedList();
        List order = new ArrayList();

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

        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            order.add(currentNode);
            for (int neighbor : graph.get(currentNode)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }

        // Your code here to print the order list
    }
}

Hint

Use System.out.println(order); to print the list of visited 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