Breadth-First Search (BFS) — Graph Traversal Guide
In this tutorial, you'll learn about Breadth. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth before moving to the next level. It uses a queue to track the frontier of exploration and finds the shortest path in unweighted graphs.
What You'll Learn
You will learn BFS traversal, shortest path finding in unweighted graphs, level-by-level processing, and applications in web crawling, social networks, and puzzle solving.
Why It Matters
BFS is the algorithm of choice for finding shortest paths in unweighted graphs, solving puzzles with minimum moves, web crawling (prioritizing by distance from seed), and network broadcasting.
Real-World Use
Doda Browser's web crawler uses BFS to discover web pages. Starting from a seed URL, it fetches all links on the page (level 1), then all links on those pages (level 2), and so on. BFS ensures the crawler discovers content closest to the seed first.
BFS Flow
graph TD
Q[Queue: A] --> L1[Level 0: A]
L1 --> L2[Level 1: B, C]
L2 --> L3[Level 2: D, E, F, G]
L3 --> L4[Level 3: H, I]
style A fill:#4a90d9,stroke:#333,color:#fff
style Q fill:#e67e22,stroke:#333,color:#fff
BFS visits nodes in order of their distance from the start: A, then B and C, then D, E, F, G, then H and I.
BFS Implementation
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': ['H'],
'E': ['I'],
'F': [],
'G': [],
'H': [],
'I': []
}
print("BFS:", end=" ")
bfs(graph, 'A')
Expected output:
BFS: A B C D E F G H I
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
while (queue.length) {
const node = queue.shift();
process.stdout.write(node + " ");
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return visited;
}
const graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': ['H'],
'E': ['I'],
'F': [],
'G': [],
'H': [],
'I': []
};
process.stdout.write("BFS: ");
bfs(graph, 'A');
console.log();
Expected output:
BFS: A B C D E F G H I
Shortest Path in Unweighted Graph
BFS finds the shortest path (minimum number of edges) between two nodes:
def shortest_path(graph, start, end):
visited = {start}
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
if node == end:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
path = shortest_path(graph, 'A', 'I')
print("Shortest path A -> I:", path)
Expected output:
Shortest path A -> I: ['A', 'B', 'E', 'I']
function shortestPath(graph, start, end) {
const visited = new Set([start]);
const queue = [[start, [start]]];
while (queue.length) {
const [node, path] = queue.shift();
if (node === end) return path;
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, path.concat(neighbor)]);
}
}
}
return null;
}
console.log("Shortest path A -> I:", shortestPath(graph, 'A', 'I'));
Expected output:
Shortest path A -> I: [ 'A', 'B', 'E', 'I' ]
Level-Order Traversal
For trees, BFS is called level-order traversal. It visits nodes level by level:
def level_order(root):
if not root:
return
queue = deque([root])
level = 0
while queue:
size = len(queue)
print(f"Level {level}:", end=" ")
for _ in range(size):
node = queue.popleft()
print(node.value, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
print()
level += 1
BFS on Grid (2D Matrix)
BFS on a grid finds the shortest path through obstacles:
def bfs_grid(grid, start, end):
rows, cols = len(grid), len(grid[0])
visited = set([start])
queue = deque([(start[0], start[1], 0)])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
r, c, dist = queue.popleft()
if (r, c) == end:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != 1 and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
grid = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 0]
]
print("Shortest path length:", bfs_grid(grid, (0, 0), (3, 3)))
Expected output:
Shortest path length: 6
BFS vs DFS
| Aspect | BFS | DFS |
|---|---|---|
| Data structure | Queue | Stack |
| Space | O(width) | O(depth) |
| Shortest path | Yes (unweighted) | No |
| Completeness | Yes | Depth-limited |
| Use case | Shortest path, social networks | Path existence, topological sort |
Common Pitfalls
1. Using Shift() for Queue in JavaScript
JavaScript's shift() on an array is O(n). For large graphs, use a proper deque implementation or index-based circular buffer.
2. Not Marking Visited Before Enqueuing
Mark nodes as visited when they are enqueued, not when dequeued. Otherwise, duplicate entries fill the queue.
3. Assuming BFS Finds Shortest Path in Weighted Graphs
BFS only guarantees shortest paths in unweighted graphs. For weighted graphs, use Dijkstra's algorithm.
4. Ignoring Memory for Wide Graphs
BFS can use O(n) memory for the queue. For very wide graphs (like social networks), this can exceed available RAM.
5. Not Handling Disconnected Graphs
Starting BFS from a single node only visits reachable nodes. Wrap with a loop over all nodes for disconnected graphs.
Practice Questions
1. Find the minimum number of moves for a knight on a chessboard using BFS.
2. Determine if a Binary Tree is a complete Binary Tree using BFS.
3. Rotting oranges problem: given a grid with fresh and rotten oranges, find the minimum time for all oranges to rot.
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
r, c, m = queue.popleft()
minutes = m
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, m + 1))
return minutes if fresh == 0 else -1
4. Challenge: Word ladder: find the shortest sequence of words transforming one word into another, changing one letter at a time, where each intermediate word must be in a dictionary.
5. Real-world task: Doda Browser's download manager shows download progress in a tree view. Write a BFS function that traverses a hierarchical download queue (parent downloads with children dependencies) and returns the optimal parallel download order.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro