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).
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.
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
Queue (FIFO Order)
Visited Set
Shortest Path Guarantee
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.
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.
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
currentthat is NOT invisited: - — 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.
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.
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.
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.
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.
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]}Queue<Integer> queue = new LinkedList<>() and a Set<Integer> visited = new HashSet<>(). We add the start node 1 to both.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.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 |
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 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.
Practice Problems
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.Lesson 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.