BFS (Breadth-First Search)
Breadth-First Search explores a graph level by level, visiting all neighbors of a node before moving deeper. It uses a queue (FIFO) to track which node to visit next, guaranteeing the shortest path in unweighted graphs.
How BFS Works
BFS starts at a chosen source node and explores all nodes at the current depth before moving on to nodes at the next depth level. It relies on a queue data structure to maintain the order of exploration.
The algorithm proceeds as follows:
- Enqueue the starting node and mark it as visited (or "discovered").
- While the queue is not empty, dequeue the front node.
- For each unvisited neighbor of the dequeued node, mark it as visited and enqueue it.
- Repeat until the queue is empty — every reachable node has been visited.
Because BFS visits nodes in order of their distance from the source, it naturally finds the shortest path (in terms of number of edges) from the source to any reachable node. This makes it ideal for problems like finding the shortest route in an unweighted maze or computing the minimum number of moves in a puzzle.
Key insight: The queue ensures that all nodes at distance d are processed before any node at distance d+1, which is why BFS is also called level-order traversal when applied to trees.
Interactive Visualization
Watch BFS traverse a graph level by level. White nodes are unvisited, yellow nodes are in the queue (discovered), and green nodes have been fully visited. The queue contents are shown on the right.
Code Implementation
Below is the standard BFS implementation using an adjacency list representation. The algorithm uses a queue to process nodes level by level and a visited set to avoid revisiting nodes.
from collections import deque
def bfs(graph, start):
"""Perform BFS from start node. Returns list of visited nodes in BFS order."""
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
node = queue.popleft() # Dequeue from front
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) # Enqueue at back
return order
# Example usage
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5, 6],
3: [1],
4: [1],
5: [2],
6: [2]
}
print(bfs(graph, 0)) # Output: [0, 1, 2, 3, 4, 5, 6]
import java.util.*;
public class BFS {
/**
* Performs BFS from start node. Returns visited nodes in BFS order.
*/
public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
List<Integer> order = new ArrayList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll(); // Dequeue from front
order.add(node);
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor); // Enqueue at back
}
}
}
return order;
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(0, 3, 4));
graph.put(2, Arrays.asList(0, 5, 6));
graph.put(3, Arrays.asList(1));
graph.put(4, Arrays.asList(1));
graph.put(5, Arrays.asList(2));
graph.put(6, Arrays.asList(2));
System.out.println(bfs(graph, 0));
// Output: [0, 1, 2, 3, 4, 5, 6]
}
}
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
/**
* Performs BFS from start node. Returns visited nodes in BFS order.
*/
vector<int> bfs(const vector<vector<int>>& graph, int start) {
unordered_set<int> visited;
queue<int> q;
vector<int> order;
visited.insert(start);
q.push(start);
while (!q.empty()) {
int node = q.front(); // Dequeue from front
q.pop();
order.push_back(node);
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor); // Enqueue at back
}
}
}
return order;
}
int main() {
vector<vector<int>> graph = {
{1, 2}, // 0
{0, 3, 4}, // 1
{0, 5, 6}, // 2
{1}, // 3
{1}, // 4
{2}, // 5
{2} // 6
};
vector<int> result = bfs(graph, 0);
for (int node : result) {
cout << node << " ";
}
// Output: 0 1 2 3 4 5 6
cout << endl;
return 0;
}
Complexity Analysis
BFS visits every vertex exactly once and examines every edge exactly once (in an undirected graph, each edge is checked from both endpoints). The queue operations (enqueue and dequeue) are O(1), so the overall complexity depends on the number of vertices and edges.
| Metric | Complexity | Description |
|---|---|---|
| Time | O(V + E) | Each vertex is enqueued/dequeued once; each edge is checked once |
| Space | O(V) | The queue and visited set each hold at most V entries |
Here, V is the number of vertices and E is the number of edges. BFS is optimal for unweighted shortest-path queries because it explores all possibilities at distance d before considering distance d+1. For weighted graphs, Dijkstra's algorithm (a priority-queue extension of BFS) is used instead.
Quiz
Test your understanding of BFS with these questions.
Q1. Which data structure does BFS use to determine the next node to visit?
Q2. What is the time complexity of BFS on a graph with V vertices and E edges?
Q3. BFS guarantees finding the shortest path in which type of graph?
Q4. Given the graph {0:[1,2], 1:[0,3,4], 2:[0,5,6], 3:[1], 4:[1], 5:[2], 6:[2]}, what is the BFS traversal order starting from node 0?
Q5. What happens if you run BFS on a disconnected graph?