Contents
- How BFS works
- BFS - Implementation
- BFS - Finding shortest path
- Complexity Analysis
- Applications of BFS
BFS starts at a given source node and visits all nodes at the current depth level before moving on to nodes
at the next depth level. It uses a Queue (FIFO) to track which nodes to visit next, and a
visited set to avoid revisiting nodes.
Consider the below undirected graph:
Starting BFS from node 1, the traversal proceeds level by level:
- Level 0: Visit node 1. Add its neighbours to the queue.
- Level 1: Dequeue and visit all direct neighbours of node 1.
- Level 2: Dequeue and visit all unvisited neighbours of level-1 nodes.
- Continue until the queue is empty and all reachable nodes are visited.
BFS uses a Queue (FIFO), which contrasts with DFS that uses a Stack (LIFO).
This level-by-level property guarantees the shortest path (in terms of number of edges) in an unweighted graph.
BFS is always implemented iteratively using a Queue. A Set (or boolean array)
tracks visited nodes to prevent processing the same node more than once.
Algorithm steps:
- Add the start node to the queue and mark it as visited.
- While the queue is not empty, dequeue a node from the front.
- Process the dequeued node.
- Enqueue all unvisited neighbours, marking each as visited before enqueuing.
- Repeat until the queue is empty.
import java.util.*;
public class GraphBFS {
// Adjacency list: node -> list of neighbouring nodes
private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
public void addEdge(int from, int to) {
adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
adjacencyList.computeIfAbsent(to, k -> new ArrayList<>()).add(from); // undirected
}
/** BFS traversal starting from the given start node */
public void bfs(int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " "); // process the node
List<Integer> neighbours = adjacencyList.getOrDefault(node, Collections.emptyList());
for (int neighbour : neighbours) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
queue.offer(neighbour);
}
}
}
}
}
Example usage:
GraphBFS graph = new GraphBFS();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(4, 5);
graph.bfs(1);
// Output: 1 2 3 4 5 (level by level)
Mark nodes visited when they are enqueued, not when they are dequeued.
This prevents the same node from being added to the queue multiple times when it is a neighbour
of several already-visited nodes.
Because BFS explores nodes level by level, the first time it reaches the destination is guaranteed
to be via the shortest path (fewest edges) in an unweighted graph.
We track the path by maintaining a parent map alongside the traversal.
/** Returns the shortest path from start to end, or empty list if no path exists. */
public List<Integer> shortestPath(int start, int end) {
if (start == end) return List.of(start);
Map<Integer, Integer> parent = new HashMap<>();
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
visited.add(start);
queue.offer(start);
parent.put(start, -1);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == end) break;
for (int neighbour : adjacencyList.getOrDefault(node, Collections.emptyList())) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
parent.put(neighbour, node);
queue.offer(neighbour);
}
}
}
if (!parent.containsKey(end)) return Collections.emptyList(); // no path found
// Reconstruct path by following parent pointers back to start
LinkedList<Integer> path = new LinkedList<>();
for (int node = end; node != -1; node = parent.get(node)) {
path.addFirst(node);
}
return path;
}
Example:
System.out.println(graph.shortestPath(1, 5));
// Output: [1, 2, 4, 5] (shortest path with 3 edges)
-
Time complexity: O(V + E) — where V is the number of vertices and
E is the number of edges. Each vertex and each edge is visited at most once.
-
Space complexity: O(V) — the visited set and the queue can hold at most V nodes.
- Shortest path in unweighted graphs — BFS guarantees the minimum number of edges between two nodes.
- Level-order tree traversal — process a binary tree level by level.
- Connected components — find all nodes reachable from a source.
- Web crawling — discover linked pages layer by layer.
- Social network distance — find degrees of separation between people.
- Bipartite graph detection — check if a graph can be 2-coloured.