Algorithms from zero
Breadth-first search (BFS)
You learned tree traversal: start at a root, visit children, then grandchildren, in some order. In the last lesson, you learned DFS—depth-first search—which explores as far down as possible along each branch before backtracking. This lesson teaches BFS—breadth-first search—a different order: explore all neighbors at distance 1 before moving to distance 2. Instead of a stack, use a queue (FIFO). Unlike DFS which dives deep, BFS spreads wide, visiting all vertices at the current “level” before stepping to the next. This matters because BFS has a special property: it finds the shortest path (fewest edges) in graphs with no weights.
After this lesson you can write BFS iteratively using a queue. You understand the difference between BFS and DFS: queue vs. stack, level-by-level vs. depth-first. You can trace BFS on a concrete graph and predict the visit order. You understand why the visited set prevents infinite loops and how the mark-on-enqueue discipline works. You know BFS’s time complexity O(V + E) and space complexity O(V). You understand the key property: BFS from a source finds the shortest path (in edges) to every reachable vertex in an unweighted graph. Next lesson is connected components, which uses BFS (or DFS) to find all disjoint parts of a graph.
What is breadth-first search?
Breadth-first search (BFS) is a graph traversal that explores all vertices at distance d from a source before exploring vertices at distance d+1. It visits every vertex reachable from a starting vertex, in level-by-level order. The key data structure is a queue (FIFO): dequeue a vertex, mark and enqueue its unvisited neighbors, repeat.
BFS vs. DFS: queue vs. stack
Both algorithms visit all reachable vertices and have the same time complexity O(V+E). The difference is the order:
- DFS (from the last lesson) uses a stack (LIFO). It goes deep along one branch, then backtracks to explore another branch.
- BFS uses a queue (FIFO). It explores all neighbors at distance 1, then all at distance 2, and so on.
Example: graph with vertices 0, 1, 2, 3 and edges 0→1, 0→2, 1→3, 2→3:
DFS from 0: 0, 1, 3, 2 (depth: goes to 1, then 3, then backtracks to 0, then 2)
BFS from 0: 0, 1, 2, 3 (level-by-level: level 0 = {0}, level 1 = {1,2}, level 2 = {3})The BFS algorithm: mark-on-enqueue
The standard BFS discipline is to mark a vertex visited when it is enqueued, not when it is dequeued. This prevents the same vertex from being enqueued multiple times:
- Start: mark the source visited, enqueue it. queue = [source], visited = {source}.
- While queue is not empty:
- Dequeue a vertex v.
- For each neighbor u of v:
- If u is not visited, mark u visited and enqueue u.
This ensures each vertex enters the queue once and is processed once.
Example graph
Same graph as lesson 02 (DFS):
Adjacency list:
0: [1, 2]
1: [3]
2: [3]
3: [2]
Visual:
0 → 1
↓ ↓
2 → 3
↑ ↓
+---+BFS trace on the example
Starting from vertex 0:
Initial: queue = [0], visited = {0}
Step 1: Dequeue 0. Neighbors: 1, 2.
- 1 not visited: mark visited, enqueue. visited = {0, 1}, queue = [1, 2]
- 2 not visited: mark visited, enqueue. visited = {0, 1, 2}, queue = [1, 2]
Step 2: Dequeue 1. Neighbors: 3.
- 3 not visited: mark visited, enqueue. visited = {0, 1, 2, 3}, queue = [2, 3]
Step 3: Dequeue 2. Neighbors: 3.
- 3 already visited: skip.
Step 4: Dequeue 3. Neighbors: 2.
- 2 already visited: skip.
Step 5: Queue empty. Done.
Visit order (by dequeue): 0, 1, 2, 3
Levels:
- Level 0 (distance 0): {0}
- Level 1 (distance 1): {1, 2}
- Level 2 (distance 2): {3}This is the power of BFS: it naturally computes the shortest path (fewest edges) to each vertex.
BFS vs. tree level-order traversal
In lesson 07 (Trees), you learned level-order traversal—process all nodes at depth d before depth d+1. That is exactly BFS on a tree. BFS is the generalization to graphs: same algorithm, but with a visited set to handle cycles and multiple paths to the same vertex.
BFS with a queue
1
function bfs(startVertex, adj) {
2
const visited = new Set();
3
const queue = [startVertex];
4
5
// Mark the start vertex as visited when enqueueing
6
visited.add(startVertex);
7
8
while (queue.length > 0) {
9
// Dequeue a vertex
10
const vertex = queue.shift();
11
console.log(vertex); // Process the vertex
12
13
// Enqueue all unvisited neighbors
14
for (const neighbor of adj[vertex]) {
15
if (!visited.has(neighbor)) {
16
visited.add(neighbor); // Mark visited when enqueueing
17
queue.push(neighbor);
18
}
19
}
20
}
21
22
return visited;
23
}
- L1 Function takes a starting vertex and an adjacency list.
- L2 Initialize an empty visited set.
- L3 Initialize the queue with the starting vertex.
- L6 Mark the start vertex visited (on enqueue, not on dequeue).
- L8 Process each vertex in the queue.
- L10 Dequeue a vertex from the front of the queue.
- L13 For each neighbor, check if it has been visited.
- L14 Mark the neighbor visited immediately (on enqueue).
- L15 Enqueue the neighbor.
Key point: mark-on-enqueue discipline
Mark a vertex visited when you enqueue it, not when you dequeue it. This ensures each vertex is enqueued exactly once. If you marked it visited only when dequeuing, the same vertex could be enqueued many times (once by each neighbor), wasting queue space and time.
Running BFS on the example graph
1
adj = { 0: [1, 2], 1: [3], 2: [3], 3: [2] };
2
queue = [0];
3
visited = {0};
Time complexity: O(V + E)
BFS enqueues each vertex exactly once (because of the mark-on-enqueue discipline) and examines each edge exactly once. Each vertex is dequeued once, and when dequeued, all its neighbors are examined. Total work: V vertices enqueued + E edges examined = O(V + E).
Example: a graph with 5 vertices and 7 edges runs BFS in O(5 + 7) = O(12) time—independent of whether the graph is sparse or dense.
Space complexity: O(V)
The visited set stores up to V vertices: O(V).
The queue can hold up to V vertices at once (at most all vertices at the current level): O(V).
Total space: O(V).
In a wide, shallow graph (like a star with one central vertex connected to many others), the queue can grow large. In a deep, narrow graph (a long chain), the queue remains small.
Why the mark-on-enqueue discipline
Without mark-on-enqueue, a vertex could be enqueued multiple times:
Bad (mark-on-dequeue):
Vertex 1 has two neighbors: 2 and 3.
Vertex 2 has neighbor 4.
Vertex 3 has neighbor 4.
When dequeuing 1:
- Enqueue 2 (not marked yet).
- Enqueue 3 (not marked yet).
When dequeuing 2:
- Neighbor 4 is not marked, so enqueue 4.
When dequeuing 3:
- Neighbor 4 is not marked, so enqueue 4 again! (duplicate in queue)
Good (mark-on-enqueue):
When processing 1:
- Mark 2 visited, enqueue 2.
- Mark 3 visited, enqueue 3.
When processing 2:
- Mark 4 visited, enqueue 4.
When processing 3:
- 4 is already visited, skip.
4 enters the queue exactly once.What data structure does BFS use to process vertices in the order of increasing distance from the source?
In BFS, when should you mark a vertex as visited?
What does BFS guarantee in an unweighted graph?
What is the time complexity of BFS on a graph with V vertices and E edges?
Why does BFS need a visited set (or array) to avoid infinite loops on cyclic graphs?
A graph has 8 vertices and 12 edges. What is the approximate time complexity O(V + E) in terms of total operations?
lesson.inset.undefined
Why BFS instead of DFS? Both visit all reachable vertices in O(V+E) time. Use BFS when you need the shortest path in an unweighted graph, or when you want to process vertices by distance. Use DFS when you want to detect cycles (more natural with recursion) or when you prefer a simpler code. For this lesson, BFS is essential for understanding shortest paths without weights.
lesson.inset.undefined
Marking visited too late. Forgetting to mark neighbors visited when enqueueing them can lead to the same vertex being enqueued multiple times. Each time a different neighbor discovers an already-enqueued vertex, it gets added again. This wastes queue space and time. Always mark-on-enqueue.
lesson.inset.undefined
Disconnected graphs. If a graph has multiple disconnected components, BFS from one vertex will only visit vertices reachable from that vertex. To visit all vertices in a disconnected graph, you must start a new BFS from an unvisited vertex. This is how the connected-components algorithm works (coming in the next lesson).
lesson.inset.undefined
BFS for shortest paths. BFS answers the question: “What is the shortest path (in edges) from source A to every other reachable vertex?” Run BFS, and track the distance to each vertex (distance increases by 1 each time you move to a neighbor at the next level). This is the foundation for more advanced shortest-path algorithms like Dijkstra (lesson 09/06).
Explain what BFS is, how it differs from DFS, why the visited set and mark-on-enqueue discipline are essential, and describe BFS's key property in unweighted graphs.
Breadth-first search (BFS) explores a graph level by level, processing all vertices at distance d before distance d+1. It uses a queue (FIFO), not a stack, and a visited set to prevent infinite loops and duplicate enqueues.
The mark-on-enqueue discipline: Mark a vertex visited when you enqueue it, ensuring each vertex is enqueued exactly once.
Time: O(V + E). Space: O(V).
Key property: In an unweighted graph, BFS from a source finds the shortest path (fewest edges) to every reachable vertex—the first time you reach a vertex is via the shortest route.
BFS spreads wide. DFS goes deep. Next lesson: connected components—use BFS or DFS to find all disconnected parts of a graph.