Breadth-First Search (BFS) — Implement BFS using a Queue and visited set (intro) - Java

SECTION 1

Historical Context & Motivation

Imagine you are lost in a maze and want to find the shortest way out. You could rush down one hallway as far as possible, but that might lead you into a dead end. A smarter strategy is to check every hallway one step away from you first, then every hallway two steps away, and so on. This layer-by-layer exploration is exactly the idea behind Breadth-First Search (BFS). The algorithm has deep roots in mathematics and computer science, emerging from the study of graph theory — the branch of math that models relationships between objects using dots (vertices) connected by lines (edges).

1736 • Euler & the Königsberg Bridges

Leonhard Euler solved the famous Seven Bridges of Königsberg problem, founding graph theory and giving us the vocabulary of vertices and edges still used today.

1945 • Konrad Zuse's Graph Exploration

German engineer Konrad Zuse experimented with systematic graph traversal techniques while developing some of the world's earliest programmable computers.

1959 • Moore's BFS Algorithm

Edward F. Moore formally published the BFS algorithm for finding the shortest path through a maze, establishing BFS as a standard tool in computer science.

1961 • Lee's Routing Algorithm

C. Y. Lee adapted BFS to route wires on circuit boards, showing that BFS has powerful real-world engineering applications beyond abstract math.

The central question BFS answers is: starting from one node, how do we systematically visit every reachable node in the shortest number of steps? To solve this efficiently, we need two data structures working together — a Queue to manage the order of exploration and a visited set to remember which nodes we have already seen.

SECTION 2

Core Principles & Definitions

Before diving into code, let's nail down the key ideas that make BFS work. A graph is a collection of nodes (also called vertices) connected by edges. Think of a social network: each person is a node, and a friendship is an edge. BFS explores this network layer by layer, starting from a chosen source node.

Level-by-Level Exploration

BFS visits all neighbors of the source first (level 1), then all neighbors of those neighbors (level 2), and so on. It never jumps ahead to a deeper level before finishing the current one.

Queue (FIFO Order)

A queue is a First-In-First-Out structure — like a line at a cafeteria. The node that enters the queue first is processed first, which guarantees the level order.

Visited Set

A visited set is a collection that tracks every node we have already added to the queue. Without it, we could revisit nodes and loop forever in graphs with cycles.

Shortest Path Guarantee

Because BFS expands layer by layer, the first time it reaches any node is guaranteed to be along a shortest path (fewest edges) from the source.

✦

KEY TAKEAWAY

Think of BFS like dropping a stone into a still pond. The ripples spread outward in concentric circles — first the ring closest to the stone, then the next ring, and so on. The queue holds the nodes on the current ripple, and the visited set makes sure no part of the pond is counted twice.

SECTION 3

Visual Explanation — BFS in Action

The following diagram shows a small graph with seven nodes labeled A through G. We start BFS from node A and watch the algorithm explore the graph level by level. Nodes change color as they move from undiscovered, to queued, to fully visited.

Starting from A (red, level 0), BFS first visits neighbors B and C (cyan, level 1). Then it visits D and E (violet, level 2), which are neighbors of B. Finally, F and G (amber, level 3) are reached. Notice how the algorithm completes each level before moving to the next.

In the diagram above, each color band represents one level of BFS. The algorithm discovers A first (level 0), then its direct neighbors B and C (level 1). From B it discovers D and E at level 2. Finally, from C and E it finds F, and from D it finds G, both at level 3. The visit order shown at the bottom is the exact sequence nodes leave the queue — this order is guaranteed to explore shorter paths before longer ones.

SECTION 4

How BFS Works — The Algorithm Step by Step

BFS follows a simple loop. You start by placing the source node in the queue and marking it as visited. Then, while the queue is not empty, you remove the front node, examine all of its neighbors, and add any unvisited neighbor to both the queue and the visited set. Let's formalize this with pseudocode and then look at the Java implementation.

Pseudocode

1. Create an empty queue Q and an empty set visited
2. Add the source node to Q and mark it in visited
3. While Q is not empty:
a. Remove the front node from Q (call it current)
b. Process current (e.g., print it)
c. For each neighbor of current that is NOT in visited:
— Add neighbor to Q and to visited

Java Implementation

In Java, we use LinkedList<String> as our Queue (it implements the Queue interface) and HashSet<String> as our visited set. The graph is stored as an adjacency list — a Map<String, List<String>> where each key is a node and its value is the list of neighbors.

ℹ

Java BFS Code

import java.util.*;

public class BFSExample {
  public static void bfs(Map<String, List<String>> graph, String start) {
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    queue.add(start);
    visited.add(start);

    while (!queue.isEmpty()) {
      String current = queue.poll(); // remove front
      System.out.print(current + " ");

      for (String neighbor : graph.get(current)) {
        if (!visited.contains(neighbor)) {
          visited.add(neighbor);
          queue.add(neighbor);
        }
      }
    }
  }
}

Notice that we add a neighbor to visited at the same moment we add it to the queue — not when we remove it. This is important: if you wait until removal, multiple copies of the same node could pile up in the queue, wasting time and potentially causing incorrect behavior.

TIME COMPLEXITY

O(V + E)

V = number of vertices (nodes), E = number of edges. Each node is enqueued and dequeued at most once (O(V)), and each edge is examined at most twice (O(E) for an undirected graph).

SPACE COMPLEXITY

O(V)

The queue and visited set each store at most V nodes, so the extra memory used is proportional to the number of nodes in the graph.

SECTION 5

Detailed Breakdown — Queue & Visited Set Trace

To truly understand BFS, it helps to trace exactly what happens inside the queue and visited set at every step. The diagram below shows the state of both data structures as we run BFS on the same graph from Section 3, starting from node A.

Each row shows one iteration of the BFS loop. The DEQUEUE column shows which node leaves the front of the queue. The QUEUE column shows the queue contents after adding new neighbors. The VISITED SET grows each time a new node is discovered.

At step 0, we initialize the queue with just A. At step 1, A is dequeued and its neighbors B and C are added. Steps 2 through 4 expand B, then C, then D — each time only adding neighbors that are not already in the visited set. By step 7, the queue is empty and every reachable node has been visited exactly once.

SECTION 6

Worked Example — BFS on a Small Graph

Let's walk through a complete BFS implementation in Java. We will build a graph, run BFS from a starting node, and trace every queue operation.

BFS on a 5-Node Graph Starting from Node 1

1
Step 1 — Build the Adjacency List

We create a graph with 5 nodes (1 through 5) and the following edges: 1–2, 1–3, 2–4, 3–4, 3–5. In Java, we use a Map<Integer, List<Integer>> to store this. For example, key 1 maps to the list [2, 3].

graph = {1:[2,3], 2:[1,4], 3:[1,4,5], 4:[2,3], 5:[3]}
2
Step 2 — Initialize Queue and Visited Set

We create a Queue<Integer> queue = new LinkedList<>() and a Set<Integer> visited = new HashSet<>(). We add the start node 1 to both.

Queue: [1] | Visited: {1}
3
Step 3 — First Iteration (Dequeue 1)

We call queue.poll() which returns 1. Node 1's neighbors are 2 and 3. Neither is in visited, so both are added to the queue and the visited set.

Output: 1 | Queue: [2, 3] | Visited: {1, 2, 3}
4
Step 4 — Second Iteration (Dequeue 2)

We dequeue 2. Its neighbors are 1 and 4. Node 1 is already visited, so only 4 is added to the queue and visited set.

Output: 1 2 | Queue: [3, 4] | Visited: {1, 2, 3, 4}
5
Step 5 — Remaining Iterations

We dequeue 3 — its unvisited neighbor is 5, which gets added. Then we dequeue 4, but its neighbors (2, 3) are all visited. Finally, we dequeue 5, and its only neighbor (3) is visited. The queue is now empty and BFS terminates.

Final BFS output: 1 2 3 4 5

💡

Why Not DFS?

If we used a stack instead of a queue, we would get Depth-First Search (DFS), which dives deep before backtracking. DFS does not guarantee shortest paths. The choice of data structure — queue vs. stack — is the key difference between BFS and DFS.

SECTION 7

Strengths, Limitations & BFS vs. DFS

BFS is a powerful tool, but it's not always the best choice. Understanding when to use BFS versus its cousin DFS (Depth-First Search) is a core skill in computer science. The table below summarizes the trade-offs.

Feature	BFS	DFS
Data Structure	Queue (FIFO)	Stack (LIFO) or recursion
Exploration Order	Level by level (breadth)	As deep as possible first (depth)
Shortest Path?	Yes (unweighted graphs)	No guarantee
Memory Usage	Can be high — stores entire level in queue	Lower — stores one path at a time
Best For	Shortest path, level-order tasks, nearby nodes	Cycle detection, topological sort, maze solving

BFS vs. DFS comparison

✦

KEY TAKEAWAY

Think of BFS like searching for your lost phone by checking every room on the first floor before going upstairs. DFS is like sprinting to the attic first and then working your way back down. BFS is slower in memory but guarantees the shortest path in an unweighted graph.

SECTION 8

Connection to Advanced Graph Algorithms

Once you master basic BFS, you are ready to tackle more advanced algorithms that build on the same idea. BFS is actually a special case of more general shortest-path algorithms. In a weighted graph — where edges have different costs or distances — plain BFS no longer finds the shortest path. That's where algorithms like Dijkstra's algorithm come in.

Feature	BFS (This Lesson)	Dijkstra's Algorithm
Graph Type	Unweighted	Weighted (non-negative)
Data Structure	Simple Queue	Priority Queue (min-heap)
Time Complexity	O(V + E)	O((V + E) log V)
Shortest Path?	Yes (fewest edges)	Yes (lowest total weight)

BFS vs. Dijkstra's Algorithm

BFS also appears as a building block in algorithms you may encounter later, such as bidirectional BFS (which searches from both the start and the goal simultaneously) and A* search (which adds a heuristic to guide the search toward the goal). Understanding the simple queue-and-visited-set pattern from this lesson gives you a solid foundation for all of these.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Why does BFS use a queue instead of a stack? Explain in your own words how the FIFO property of the queue ensures level-by-level exploration.

Show answer

A queue processes elements in the order they were added (First-In-First-Out). When BFS discovers neighbors of a node, those neighbors are added to the back of the queue. Since all nodes at the current level were already in the queue before these new neighbors, they will all be processed first. This guarantees that BFS finishes exploring every node at distance d before moving to nodes at distance d + 1. If a stack were used instead, the last neighbor added would be processed first, causing the algorithm to dive deeper before exploring all same-level nodes — that's DFS behavior.

Question 2: BASIC CALCULATION

Consider a graph with nodes {1, 2, 3, 4} and edges: 1–2, 1–3, 2–4, 3–4. If BFS starts from node 1 and processes neighbors in numerical order, write the exact order in which nodes are printed and the contents of the queue after each dequeue.

Show answer

Start: Queue = [1], Visited = {1}. Dequeue 1 → print 1, add 2 and 3 → Queue = [2, 3], Visited = {1, 2, 3}. Dequeue 2 → print 2, neighbor 1 is visited, add 4 → Queue = [3, 4], Visited = {1, 2, 3, 4}. Dequeue 3 → print 3, neighbors 1 and 4 are both visited → Queue = [4]. Dequeue 4 → print 4, neighbors 2 and 3 are visited → Queue = []. BFS output: 1 2 3 4. The key insight is that node 4 is added when processing node 2, not node 3, because the visited set prevents duplicate additions.

Question 3: INTERMEDIATE

Write a Java method that takes an adjacency list (as a Map<String, List<String>>) and two node names, start and target, and returns the shortest distance (number of edges) between them. Return −1 if no path exists.

Show answer

Use BFS but track the distance. One approach: store pairs of (node, distance) in the queue. Initialize with (start, 0). Each time you enqueue a neighbor, its distance is the current node's distance + 1. When you dequeue target, return its distance. If the queue empties without reaching target, return −1. In code: Queue<String[]> queue = new LinkedList<>(); queue.add(new String[]{start, "0"}); An alternative is to use a separate Map<String, Integer> that records the distance when a node is first visited. Both approaches run in O(V + E) time. The visited set ensures each node is processed at most once, so the first time we reach target is guaranteed to be the shortest distance.

Question 4: APPLIED

A video game has a grid map that is 5 rows × 5 columns. The player starts at cell (0, 0) and wants to reach cell (4, 4). Some cells are walls. Explain how you would model this grid as a graph and use BFS to find the shortest path. What would the nodes, edges, and adjacency list look like?

Show answer

Each cell (row, col) is a node. Two nodes are connected by an edge if they are adjacent (up, down, left, right) and neither is a wall. The adjacency list maps each non-wall cell to a list of its non-wall neighbors. For example, cell (0,0) connects to (0,1) and (1,0) if those cells aren't walls. BFS starts at (0,0), and we explore all cells reachable in 1 step, then 2 steps, etc. When (4,4) is first dequeued, the distance in steps is the shortest possible. To reconstruct the actual path, maintain a parent map: when adding a neighbor to the queue, record which node it came from. After reaching the goal, trace backwards through the parent map from (4,4) to (0,0). This is exactly how many game pathfinding systems work.

Question 5: CRITICAL THINKING

Suppose you forget to use a visited set and run BFS on a graph that contains a cycle (e.g., A–B–C–A). What happens? Trace through the first several iterations and explain the consequences. Then explain why marking a node as visited when it enters the queue (rather than when it leaves) is important.

Show answer

Without a visited set on the cycle A–B–C–A, BFS starting at A would add B and C. Then dequeuing B adds A and C again (since there's no check), and dequeuing C adds A and B again. These duplicate entries generate more duplicates in subsequent iterations, causing the queue to grow without bound — an infinite loop. The program would run out of memory or run forever. Marking a node visited when it enters the queue (not when it exits) is critical because it prevents the same node from being added to the queue by multiple parents during the same level expansion. If you wait until dequeue time to mark visited, a node could be added to the queue several times before being dequeued, wasting memory and time. Both issues highlight that the visited set is not just an optimization — it is essential for correctness in any graph with cycles.

SUMMARY

Lesson Summary

Summary

Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes level by level, starting from a source node. It relies on two core data structures: a queue (FIFO) that controls the order of exploration, and a visited set that prevents re-processing nodes. The algorithm adds the source to both structures, then repeatedly dequeues the front node, processes it, and enqueues any unvisited neighbors.

BFS guarantees the shortest path in an unweighted graph because it finishes all nodes at distance d before exploring distance d + 1. Its time complexity is O(V + E) and space complexity is O(V). In Java, LinkedList implements the Queue interface, and HashSet provides an efficient visited set. Mastering BFS prepares you for more advanced algorithms like Dijkstra's, bidirectional BFS, and A* search.