BFS Breadth First Search on Graph in DSA Java - Deep Dive

Overview - BFS Breadth First Search on Graph

What is it?

Breadth First Search (BFS) is a way to explore all the points (nodes) in a graph by visiting neighbors level by level. Starting from one node, it visits all nodes directly connected to it before moving to nodes connected further away. This method helps find the shortest path in unweighted graphs and explores all reachable nodes systematically. BFS uses a queue to keep track of nodes to visit next.

Why it matters

Without BFS, finding the shortest path or exploring all connected parts of a graph would be slow and complicated. BFS ensures we visit nodes in the order of their distance from the start, which is crucial in many real-world problems like finding routes, social network connections, or spreading information. Without BFS, many applications would be inefficient or impossible to solve correctly.

Where it fits

Before learning BFS, you should understand what graphs are and how they represent connections between points. After BFS, you can learn about Depth First Search (DFS), shortest path algorithms like Dijkstra's, and graph traversal optimizations.

Mental Model

Core Idea

BFS explores a graph by visiting all neighbors at the current distance before moving to nodes further away, using a queue to track the order.

Think of it like...

Imagine you are in a building and want to visit every room floor by floor. You first visit all rooms on the ground floor, then all rooms on the first floor, and so on, making sure you don't miss any room on a floor before moving up.

Start Node
  │
  ▼
[Queue] -> [Visit neighbors level 1]
  │
  ▼
[Queue] -> [Visit neighbors level 2]
  │
  ▼
... until all reachable nodes are visited

Graph nodes are visited in layers, like waves spreading out.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of nodes (points) connected by edges (lines).

A graph is a collection of nodes connected by edges. Each node can have zero or more neighbors. Graphs can be directed (edges have direction) or undirected (edges are two-way). For BFS, we usually consider undirected or directed graphs where we want to explore reachable nodes.

Result

You can picture a graph as points connected by lines, ready to be explored.

Understanding the structure of graphs is essential before learning how to explore them.

2

Foundation

What is a Queue and Why Use It?

Concept: A queue is a line where the first person in is the first person out (FIFO).

A queue lets us add items at the back and remove from the front. This order helps BFS visit nodes level by level. When we visit a node, we add its neighbors to the queue to visit them later in the correct order.

Result

You understand how BFS keeps track of nodes to visit next.

Knowing how a queue works is key to grasping BFS traversal order.

3

Intermediate

Basic BFS Algorithm Steps

🤔Before reading on: do you think BFS visits nodes in depth-first order or breadth-first order? Commit to your answer.

Concept: BFS visits nodes in layers, starting from the start node and moving outward.

1. Start with a queue containing the start node. 2. Mark the start node as visited. 3. While the queue is not empty: a. Remove the front node from the queue. b. Visit all its unvisited neighbors. c. Mark neighbors as visited and add them to the queue. This ensures nodes closer to the start are visited first.

Result

Nodes are visited in order of their distance from the start node.

Understanding BFS as a layer-by-layer exploration helps solve shortest path problems.

4

Intermediate

Implementing BFS in Java

🤔Before reading on: do you think BFS requires recursion or iteration? Commit to your answer.

Concept: BFS is implemented using iteration and a queue data structure.

```java import java.util.*; public class BFS { public static void bfs(Map> graph, int start) { Queue queue = new LinkedList<>(); Set 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, Collections.emptyList())) { if (!visited.contains(neighbor)) { queue.add(neighbor); visited.add(neighbor); } } } System.out.print("null\n"); } 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()); graph.put(6, Arrays.asList()); bfs(graph, 1); } } ```

Result

Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Seeing BFS implemented concretely clarifies how the queue and visited set work together.

5

Intermediate

Handling Cycles and Visited Nodes

🤔Before reading on: do you think BFS can get stuck in a cycle without tracking visited nodes? Commit to your answer.

Concept: BFS must track visited nodes to avoid infinite loops in graphs with cycles.

Graphs can have cycles where nodes connect back to earlier nodes. Without marking nodes as visited, BFS would revisit the same nodes endlessly. Using a visited set ensures each node is processed once, preventing infinite loops and repeated work.

Result

BFS safely explores graphs with cycles without getting stuck.

Knowing why visited tracking is essential prevents common bugs in graph traversal.

6

Advanced

BFS for Shortest Path in Unweighted Graphs

🤔Before reading on: do you think BFS can find shortest paths in weighted graphs? Commit to your answer.

Concept: BFS finds shortest paths only in graphs where all edges have equal weight (unweighted).

Because BFS visits nodes in order of their distance from the start, the first time it reaches a node is via the shortest path. By storing the parent of each node during BFS, you can reconstruct the shortest path from start to any node. For weighted graphs, BFS does not guarantee shortest paths; algorithms like Dijkstra's are needed.

Result

BFS can be used to find shortest paths in unweighted graphs efficiently.

Understanding BFS's limitation to unweighted graphs guides correct algorithm choice.

7

Expert

Optimizations and BFS Variants

🤔Before reading on: do you think BFS always uses a simple queue or can it be optimized? Commit to your answer.

Concept: BFS can be optimized or adapted for special cases like bidirectional search or layered graphs.

In large graphs, BFS can be slow. Bidirectional BFS runs two simultaneous searches from start and target nodes, meeting in the middle to reduce work. For layered graphs, BFS can be combined with other data structures to handle weights or constraints. Also, BFS can be implemented with adjacency matrices or lists depending on graph density for efficiency.

Result

Advanced BFS techniques improve performance and adapt BFS to complex problems.

Knowing BFS variants prepares you for real-world challenges beyond basic traversal.

Under the Hood

BFS uses a queue to manage nodes in the order they are discovered. When a node is visited, its neighbors are enqueued if unvisited. This queue ensures nodes are processed in layers, guaranteeing the shortest path in unweighted graphs. Internally, the visited set prevents revisiting nodes, avoiding infinite loops. The graph is typically stored as adjacency lists for efficient neighbor lookup.

Why designed this way?

BFS was designed to explore graphs systematically and efficiently. Using a queue fits the need to process nodes in the order they are discovered, unlike DFS which uses a stack or recursion. This design ensures BFS finds shortest paths in unweighted graphs and explores all reachable nodes without repetition. Alternatives like DFS explore depth first but do not guarantee shortest paths.

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐     ┌─────────────┐
│  Queue      │ --> │ Visit Node  │
└──────┬──────┘     └──────┬──────┘
       │                   │
       ▼                   ▼
┌─────────────┐     ┌─────────────┐
│ Enqueue    │<----│ Neighbors   │
│ unvisited  │     │ of Node     │
│ neighbors  │     └─────────────┘
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does BFS always find the shortest path in any graph? Commit yes or no.

Common Belief: BFS always finds the shortest path regardless of edge weights.

Reality: BFS only finds shortest paths in unweighted graphs or graphs where all edges have the same weight.

Why it matters: Using BFS on weighted graphs can give wrong shortest paths, leading to incorrect results in routing or cost calculations.

Quick: Can BFS be implemented using recursion? Commit yes or no.

Common Belief: BFS can be implemented recursively like DFS.

Reality: BFS is naturally iterative and uses a queue; recursion fits DFS better.

Why it matters: Trying to implement BFS recursively can cause confusion and inefficient code.

Quick: Does BFS visit nodes in the order they were added to the graph? Commit yes or no.

Common Belief: BFS visits nodes in the order they were added to the graph.

Reality: BFS visits nodes based on their distance from the start node, not insertion order.

Why it matters: Assuming BFS follows insertion order can lead to wrong expectations about traversal order.

Quick: Does BFS always use an adjacency list? Commit yes or no.

Common Belief: BFS requires adjacency lists to work.

Reality: BFS can work with adjacency matrices or other graph representations, though adjacency lists are more efficient for sparse graphs.

Why it matters: Limiting BFS to adjacency lists restricts understanding of graph representations and their tradeoffs.

Expert Zone

1

BFS's performance depends heavily on graph representation; adjacency lists reduce memory and speed up neighbor lookup in sparse graphs.

2

Bidirectional BFS can reduce search space from O(V+E) to roughly O(b^(d/2)) where b is branching factor and d is distance, a huge optimization.

3

Tracking parents during BFS allows path reconstruction, but forgetting this step loses the ability to retrieve actual shortest paths.

When NOT to use

Avoid BFS for graphs with weighted edges where weights differ; use Dijkstra's or A* algorithms instead. Also, for very deep or infinite graphs, DFS or iterative deepening may be better to limit memory use.

Production Patterns

BFS is used in social networks to find friend suggestions, in GPS systems for shortest routes on unweighted maps, in web crawlers to explore links layer by layer, and in AI for state space exploration where all moves cost the same.

Connections

Depth First Search (DFS)

DFS explores as deep as possible before backtracking, opposite to BFS's layer-by-layer approach.

Understanding BFS helps grasp DFS by contrast, showing how traversal order affects algorithm behavior and use cases.

Queue Data Structure

BFS relies on queues to manage nodes in the correct visiting order.

Mastering queues clarifies BFS mechanics and helps in other algorithms that require ordered processing.

Wave Propagation in Physics

BFS spreading through nodes resembles waves spreading through a medium.

Recognizing BFS as a wave helps understand its layer-by-layer nature and why it finds shortest paths in unweighted graphs.

Common Pitfalls

#1 Not marking nodes as visited causes infinite loops in cyclic graphs.

Wrong approach:

while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " -> ");
for (int neighbor : graph.get(node)) {
queue.add(neighbor); // No visited check
}
}

Correct approach:

while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " -> ");
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
}
}

Root cause:

Failing to track visited nodes misunderstands BFS's need to avoid revisiting nodes.

#2 Using recursion to implement BFS leads to stack overflow or incorrect order.

Wrong approach:

void bfs(int node) {
System.out.print(node + " -> ");
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
bfs(neighbor); // Recursive call
}
}
}

Correct approach:

Use a queue and iterative loop instead of recursion for BFS.

Root cause:

Confusing BFS with DFS causes wrong implementation choice.

#3 Assuming BFS finds shortest paths in weighted graphs.

Wrong approach:

Use BFS to find shortest path in graph with edges of different weights without modification.

Correct approach:

Use Dijkstra's algorithm or A* for weighted graphs to find shortest paths.

Root cause:

Misunderstanding BFS's limitation to unweighted graphs leads to incorrect results.

Key Takeaways

BFS explores graphs level by level using a queue, ensuring nodes closer to the start are visited first.

Tracking visited nodes is essential to prevent infinite loops and repeated visits in graphs with cycles.

BFS finds shortest paths only in unweighted graphs where all edges have equal cost.

Implementing BFS iteratively with a queue is natural and efficient; recursion suits DFS better.

Advanced BFS techniques like bidirectional search improve performance in large graphs.

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