7a:T4c7,Imagine you're standing at the entrance of a vast, interconnected labyrinth. How do you explore it systematically to understand its complete structure? Do you plunge deep down one corridor until you hit a dead end, then backtrack? Or do you first examine all the rooms immediately adjacent to you, then all the rooms adjacent to those, expanding outward in concentric circles like ripples from a stone dropped in still water? **Breadth-First Search (BFS)** embodies the second approach—a methodical, level-by-level exploration that guarantees you visit every reachable vertex exactly once, always discovering vertices in order of their distance from your starting point. This seemingly simple idea—"explore all neighbors before going deeper"—forms the foundation for some of the most powerful algorithms in computer science. BFS is not merely an academic exercise. It's the algorithm your GPS uses to find the shortest route when all roads take equal time. It's how web crawlers systematically discover every page on the internet. It's the mechanism behind finding the minimum number of moves to solve a Rubik's cube. Understanding BFS deeply means understanding a fundamental paradigm of computational exploration.7b:T5ca,Before examining BFS mechanically, let's understand *why* breadth-first exploration is a distinct and valuable approach. **The problem BFS solves:** Given a graph G = (V, E) and a source vertex s, we want to: 1. **Discover** every vertex reachable from s 2. **Compute** the minimum number of edges needed to reach each vertex from s 3. **Produce** a breadth-first tree rooted at s that encodes shortest paths The key constraint that makes BFS special is the notion of **distance**. In an unweighted graph, the distance between two vertices is the minimum number of edges on any path connecting them. BFS computes these distances naturally as a byproduct of its exploration order. **The "wavefront" mental model:** Think of BFS as dropping a pebble into a still pond. The ripples expand outward uniformly—first reaching points at distance 1 from impact, then distance 2, then distance 3, and so on. No point at distance 3 gets wet before all points at distance 2 are reached. Similarly, BFS explores vertices in "waves" based on their distance from the source: - **Wave 0**: The source vertex itself (distance 0) - **Wave 1**: All vertices directly connected to source (distance 1) - **Wave 2**: All undiscovered vertices connected to Wave 1 vertices (distance 2) - **Wave k**: All undiscovered vertices connected to Wave (k-1) vertices This layered structure is what distinguishes BFS from Depth-First Search (DFS), which explores as deeply as possible before backtracking.7c:T417,Let's specify BFS with precision. Given a graph G = (V, E) and source vertex s, BFS maintains several data structures: **State tracking for each vertex u ∈ V:** - **color[u]**: Tracks discovery state - WHITE: Undiscovered (never seen) - GRAY: Discovered but not fully processed (in the queue) - BLACK: Fully processed (all neighbors examined) - **distance[u]**: The computed distance from s to u (∞ initially) - **parent[u]**: The predecessor of u on the shortest path from s (null initially) **The queue Q:** - A FIFO (First-In-First-Out) data structure - Stores vertices that are discovered (GRAY) but not yet fully processed **Why these states matter:** The three colors encode the exploration frontier: - WHITE vertices are unexplored territory—we haven't reached them yet - GRAY vertices form the current "wavefront"—discovered but still yielding new discoveries - BLACK vertices are behind the wavefront—all their neighbors have been considered This classification ensures each vertex and edge is processed exactly once.7d:T4c0,**Line-by-line analysis:** **Lines 2-5 (Initialization):** Every vertex starts WHITE (undiscovered), with infinite distance and no parent. This O(V) initialization sets up our clean slate. **Lines 7-9 (Source setup):** The source is our starting point—distance 0, discovered (GRAY), but with no parent since it's the root of our exploration tree. **Lines 11-12 (Queue creation):** We create our FIFO queue and seed it with the source. The queue is the heart of BFS—it enforces the level-by-level exploration order. **Line 15 (Main loop):** We continue while there are discovered-but-not-processed vertices. When the queue empties, we've explored everything reachable. **Line 16 (Dequeue):** We extract the front vertex. FIFO order ensures we always process vertices in distance order—all distance-k vertices before any distance-(k+1) vertices. **Lines 18-23 (Neighbor examination):** For each edge (u, v), if v is undiscovered (WHITE), we: - Discover it (mark GRAY) - Set its distance as parent's distance + 1 - Record u as its parent (for path reconstruction) - Enqueue it for future processing **Line 25 (Mark complete):** After examining all of u's neighbors, u is BLACK—we'll never visit it again.7e:T5cb,The queue is not an arbitrary choice—it's the *only* data structure that produces breadth-first exploration. Understanding why requires understanding how different data structures affect exploration order. **Why FIFO enforces level-order:** Consider what happens with a queue: 1. We start with just source s (distance 0) in the queue 2. We dequeue s, examine its neighbors (all at distance 1), and enqueue them 3. Now the queue contains only distance-1 vertices 4. We dequeue the first distance-1 vertex, enqueue its undiscovered neighbors (distance 2) 5. These distance-2 vertices go to the *back* of the queue 6. We continue processing distance-1 vertices (at the front) before reaching distance-2 vertices The key insight: **new discoveries (distance d+1) go behind existing discoveries (distance d)**. FIFO ensures we process all distance-d vertices before any distance-(d+1) vertices. **What if we used a stack (LIFO)?** If we replaced the queue with a stack, new discoveries would go to the *front*, and we'd process them *before* finishing the current level. This produces **depth-first** exploration—going as deep as possible before backtracking. The change from FIFO to LIFO completely changes the exploration pattern! **What if we used a priority queue?** If we used a priority queue ordered by some weight, we'd get **Dijkstra's algorithm**—a generalization of BFS for weighted graphs. BFS is actually a special case of Dijkstra where all edges have weight 1.7f:T865,from collections import deque from typing import List, Dict, Set, Optional def bfs(graph: Dict[int, List[int]], source: int) -> tuple[Dict[int, int], Dict[int, Optional[int]]]: """ Perform BFS from source vertex. Args: graph: Adjacency list representation {vertex: [neighbors]} source: Starting vertex Returns: distance: Dict mapping each vertex to its distance from source parent: Dict mapping each vertex to its parent in BFS tree """ # Initialize data structures visited: Set[int] = set() distance: Dict[int, int] = {} parent: Dict[int, Optional[int]] = {} queue: deque = deque() # Initialize source visited.add(source) distance[source] = 0 parent[source] = None queue.append(source) # BFS main loop while queue: u = queue.popleft() # Dequeue from front (FIFO) for v in graph.get(u, []): if v not in visited: visited.add(v) distance[v] = distance[u] + 1 parent[v] = u queue.append(v) return distance, parent def reconstruct_path(parent: Dict[int, Optional[int]], target: int) -> List[int]: """ Reconstruct the shortest path from source to target. Args: parent: Parent dictionary from BFS target: Destination vertex Returns: List of vertices on the path from source to target Empty list if target is unreachable """ if target not in parent: return [] # Target was never discovered path = [] current = target while current is not None: path.append(current) current = parent[current] return path[::-1] # Reverse to get source-to-target order # Example usage if __name__ == "__main__": # Graph: 0 -- 1 -- 2 # | | # 3 -- 4 graph = { 0: [1, 3], 1: [0, 2, 4], 2: [1], 3: [0, 4], 4: [1, 3] } dist, parent = bfs(graph, 0) print(f"Distances from 0: {dist}") print(f"Path to 2: {reconstruct_path(parent, 2)}")80:T733,interface BFSResult { distance: Map; parent: Map; } function bfs(graph: Map, source: number): BFSResult { /** * Perform BFS from source vertex. * Returns distance and parent maps for path reconstruction. */ const visited = new Set(); const distance = new Map(); const parent = new Map(); const queue: number[] = []; // Initialize source visited.add(source); distance.set(source, 0); parent.set(source, null); queue.push(source); // BFS main loop while (queue.length > 0) { const u = queue.shift()!; // Dequeue from front (FIFO) const neighbors = graph.get(u) ?? []; for (const v of neighbors) { if (!visited.has(v)) { visited.add(v); distance.set(v, distance.get(u)! + 1); parent.set(v, u); queue.push(v); } } } return { distance, parent }; } function reconstructPath(parent: Map, target: number): number[] { /** * Reconstruct shortest path from source to target. */ if (!parent.has(target)) { return []; // Target unreachable } const path: number[] = []; let current: number | null = target; while (current !== null) { path.push(current); current = parent.get(current) ?? null; } return path.reverse(); } // Example usage const graph = new Map([ [0, [1, 3]], [1, [0, 2, 4]], [2, [1]], [3, [0, 4]], [4, [1, 3]] ]); const { distance, parent } = bfs(graph, 0); console.log("Distances:", Object.fromEntries(distance)); console.log("Path to 2:", reconstructPath(parent, 2));81:T9fe,import java.util.*; public class BFS { public static class BFSResult { public Map distance; public Map parent; public BFSResult() { this.distance = new HashMap<>(); this.parent = new HashMap<>(); } } /** * Perform BFS from source vertex. * * @param graph Adjacency list representation * @param source Starting vertex * @return BFSResult with distance and parent maps */ public static BFSResult bfs(Map> graph, int source) { BFSResult result = new BFSResult(); Set visited = new HashSet<>(); Queue queue = new LinkedList<>(); // Initialize source visited.add(source); result.distance.put(source, 0); result.parent.put(source, null); queue.offer(source); // BFS main loop while (!queue.isEmpty()) { int u = queue.poll(); List neighbors = graph.getOrDefault(u, Collections.emptyList()); for (int v : neighbors) { if (!visited.contains(v)) { visited.add(v); result.distance.put(v, result.distance.get(u) + 1); result.parent.put(v, u); queue.offer(v); } } } return result; } /** * Reconstruct shortest path from source to target. */ public static List reconstructPath(Map parent, int target) { if (!parent.containsKey(target)) { return Collections.emptyList(); } List path = new ArrayList<>(); Integer current = target; while (current != null) { path.add(current); current = parent.get(current); } Collections.reverse(path); return path; } public static void main(String[] args) { Map> graph = new HashMap<>(); graph.put(0, Arrays.asList(1, 3)); graph.put(1, Arrays.asList(0, 2, 4)); graph.put(2, Arrays.asList(1)); graph.put(3, Arrays.asList(0, 4)); graph.put(4, Arrays.asList(1, 3)); BFSResult result = bfs(graph, 0); System.out.println("Distances: " + result.distance); System.out.println("Path to 2: " + reconstructPath(result.parent, 2)); } }82:T597,It's tempting to accept that BFS finds shortest paths because "it explores level by level." But let's prove this rigorously—understanding the proof deepens your intuition and helps you verify whether BFS is applicable to new problems. **Theorem:** For any vertex v reachable from source s, BFS computes distance[v] = δ(s, v), where δ(s, v) is the true shortest path distance. **Proof sketch:** We prove by induction on the true distance δ(s, v). **Base case:** δ(s, s) = 0, and BFS sets distance[s] = 0 during initialization. ✓ **Inductive step:** Assume the claim holds for all vertices u with δ(s, u) < k. Consider a vertex v with δ(s, v) = k. Let p = s → ... → u → v be a shortest path from s to v. Then: - δ(s, u) = k - 1 (u is one edge before v on a shortest path) - By inductive hypothesis, distance[u] = k - 1 - Therefore u is discovered and enqueued when some vertex at distance k-2 is processed When u is dequeued and processed: - v is examined as a neighbor of u - If v is still undiscovered, distance[v] is set to distance[u] + 1 = k ✓ - If v was already discovered, it was discovered via another shortest path (since all paths that discover v have length ≤ k), so distance[v] = k ✓ **Key insight:** BFS's shortest path guarantee relies on: 1. All edges having the same "weight" (cost of 1) 2. FIFO processing order ensuring distance-d vertices are processed before distance-(d+1) vertices72:{"json":{"id":"seed_e006ec53eb400bc7932c13ed5eb822fe","slug":"bfs-algorithm-applications","category":"Data Structures & Algorithms","topic":"Breadth-First Search (BFS)","title":"Breadth-First Search (BFS) — Algorithm & Applications","description":"Master Breadth-First Search, the foundational graph traversal algorithm that explores vertices level-by-level using a queue. Learn the algorithm mechanics, understand queue-based exploration, analyze time complexity O(V+E), and apply BFS to solve shortest path problems in unweighted graphs.","difficulty":"INTERMEDIATE","estimatedMinutes":75,"pages":[{"id":"seed_8e6d03b20be741e2b5bd7225b45b5127","title":"BFS Algorithm — The Mechanics of Level-Order Exploration","order":0,"content":[{"id":"opening-hook","title":"The Art of Systematic Exploration","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the BFS algorithm at a deep, intuitive level. You'll know exactly how the queue orchestrates exploration, why BFS naturally discovers shortest paths in unweighted graphs, and how to implement BFS correctly for any graph representation. This foundation prepares you to wield BFS as a powerful tool across dozens of problem domains.","variant":"info"},"type":"callout"}]},{"id":"fundamental-insight","title":"The Fundamental Insight: Why Breadth, Not Depth?","content":[{"data":{"content":"$7b"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Core Guarantee","content":"BFS guarantees that when you first discover a vertex, you've discovered it via a shortest path from the source. This property makes BFS the algorithm of choice for unweighted shortest path problems—a guarantee DFS cannot provide.","variant":"tip"},"type":"callout"},{"data":{"content":"**Why depth-first fails for shortest paths:**\n\nConsider a simple graph: A—B—C where A is also directly connected to C (A—C). If we use DFS starting from A and happen to explore B first, we might discover C via A→B→C (distance 2) before exploring the direct edge A→C (distance 1). DFS doesn't track distances—it simply explores as far as possible along each branch.\n\nBFS, by contrast, processes vertices in distance order. From A, we first consider all immediate neighbors (B and C at distance 1). Only after all distance-1 vertices are processed do we move to distance-2 vertices. The direct edge A→C is always discovered before any 2-hop path to C.\n\nThis \"level-by-level\" processing is the essence of BFS and requires careful orchestration—which brings us to the queue."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"algorithm-detail","title":"The BFS Algorithm: Complete Specification","content":[{"data":{"content":"$7c"},"type":"text"},{"data":{"fileName":"bfs-algorithm.pseudo","languages":[{"code":"BFS(G, s):\n // Initialize all vertices\n for each vertex u in V[G]:\n color[u] = WHITE\n distance[u] = ∞\n parent[u] = NULL\n \n // Initialize source vertex\n color[s] = GRAY\n distance[s] = 0\n parent[s] = NULL\n \n // Create empty queue and enqueue source\n Q = empty queue\n ENQUEUE(Q, s)\n \n // Main BFS loop\n while Q is not empty:\n u = DEQUEUE(Q)\n \n // Examine all neighbors of u\n for each vertex v in Adj[u]:\n if color[v] == WHITE: // v is undiscovered\n color[v] = GRAY // Mark as discovered\n distance[v] = distance[u] + 1\n parent[v] = u\n ENQUEUE(Q, v)\n \n color[u] = BLACK // u is fully processed\n \n return (distance, parent)","label":"Pseudocode","value":"pseudo"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"$7d"},"type":"text"},{"data":{"icon":"Info","title":"The Distance Invariant","content":"The queue always contains vertices in at most two consecutive \"levels\". If the front of the queue has distance d, all other queue elements have distance d or d+1. This invariant is maintained because we only add distance-(d+1) vertices when processing distance-d vertices. This is why the simple formula distance[v] = distance[u] + 1 correctly computes shortest paths.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"queue-mechanics","title":"Queue-Based Exploration: The Engine of BFS","content":[{"data":{"content":"$7e"},"type":"text"},{"data":{"rows":[["Queue (FIFO)","First-In-First-Out","Level-by-level (breadth-first)","BFS"],["Stack (LIFO)","Last-In-First-Out","Deep before wide (depth-first)","DFS (iterative)"],["Priority Queue","By edge weight","Lowest total cost first","Dijkstra's Algorithm"],["Priority Queue","By heuristic","Estimated best path first","A* Search"]],"caption":"Data Structure vs. Exploration Pattern","headers":["Data Structure","Order","Exploration Pattern","Resulting Algorithm"]},"type":"table"},{"data":{"content":"**Visualizing the queue's state:**\n\nLet's trace through a concrete example. Consider a simple graph where A connects to B and C, B connects to D, and C connects to D and E.\n\n```\n A\n / \\\n B C\n | |\\\n D---+ E\n```\n\n**Initial state:**\n- Queue: [A]\n- Distance: A=0, all others=∞\n\n**After processing A:**\n- Dequeue A, examine neighbors B and C\n- Queue: [B, C]\n- Distance: A=0, B=1, C=1\n\n**After processing B:**\n- Dequeue B, examine neighbor D (C already discovered)\n- Queue: [C, D]\n- Distance: A=0, B=1, C=1, D=2\n\n**After processing C:**\n- Dequeue C, examine neighbors D (already discovered) and E (new!)\n- Queue: [D, E]\n- Distance: A=0, B=1, C=1, D=2, E=2\n\n**After processing D:**\n- Dequeue D, no new neighbors\n- Queue: [E]\n- All neighbors already discovered\n\n**After processing E:**\n- Dequeue E, no neighbors\n- Queue: []\n- **BFS complete!**\n\nNotice how all distance-1 vertices (B, C) were fully processed before any distance-2 vertices (D, E). This is the queue's magic."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Common Implementation Mistake","content":"A frequent bug is checking for discovery when dequeuing rather than when enqueuing. If you mark vertices as discovered only when you dequeue them (instead of when you enqueue them), the same vertex might be enqueued multiple times by different neighbors. This wastes memory and time, and can produce incorrect results if not handled carefully. Always mark as discovered (GRAY) immediately upon enqueueing.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"implementation-patterns","title":"Implementation Patterns: From Theory to Code","content":[{"data":{"content":"The pseudocode above is mathematically precise but includes more state than practical implementations typically need. Let's examine real implementations that balance clarity and efficiency.\n\n**Simplification: Replacing colors with visited set**\n\nIn practice, we rarely need three colors. A simple \"visited\" boolean or set suffices:\n- Not in visited = WHITE (undiscovered)\n- In visited = GRAY or BLACK (discovered, don't re-process)\n\nThe distinction between GRAY and BLACK matters for some applications (like edge classification) but not for basic BFS."},"type":"text"},{"data":{"fileName":"bfs-implementation","languages":[{"code":"$7f","label":"Python","value":"python"},{"code":"$80","label":"TypeScript","value":"typescript"},{"code":"$81","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Implementation notes:**\n\n1. **Queue choice matters for performance**\n - Python: Use `collections.deque` (O(1) popleft), not list.pop(0) (O(n)!)\n - TypeScript: `shift()` is O(n)—for large graphs, use a proper queue implementation\n - Java: `LinkedList` with `poll()` provides O(1) dequeue\n\n2. **Graph representation**\n - Adjacency list is ideal for BFS—we iterate through neighbors frequently\n - Adjacency matrix works but wastes time checking non-edges\n\n3. **Visited check timing**\n - Always check and mark visited *before* enqueueing, not when dequeuing\n - This prevents duplicate entries and reduces queue size"},"type":"text"}],"titleType":"number","titleNumber":4},{"id":"correctness-properties","title":"Correctness: Why BFS Finds Shortest Paths","content":[{"data":{"content":"$82"},"type":"text"},{"data":{"icon":"AlertCircle","title":"When BFS Fails for Shortest Paths","content":"BFS does NOT find shortest paths in weighted graphs where edges have different costs. If edge (A, B) has cost 1 and edge (A, C) has cost 10, BFS might claim both B and C are \"distance 1\" from A. For weighted graphs, you need Dijkstra's algorithm (non-negative weights) or Bellman-Ford (any weights). The unweighted case where BFS works is a special case where Dijkstra degenerates to BFS.","variant":"warning"},"type":"callout"},{"data":{"content":"**The BFS Tree:**\n\nBFS produces more than just distances—it produces a tree:\n\nThe **parent pointers** (parent[v] = u means v was discovered from u) form a **BFS tree** rooted at the source. This tree has important properties:\n\n1. **Shortest path encoding**: The path from s to any vertex v in the BFS tree *is* a shortest path in the original graph\n\n2. **Unique distances**: The tree depth of any vertex equals its distance from s\n\n3. **Tree edges vs. cross edges**: In the BFS tree:\n - Tree edges connect vertices at consecutive levels (distance d to distance d+1)\n - Non-tree edges connect vertices at the same level or consecutive levels (never skip levels)\n\nThe third property is subtle but important: in BFS, you'll never find an edge connecting a distance-2 vertex directly to a distance-5 vertex. If such an edge existed, the distance-5 vertex would have been discovered as a distance-3 vertex instead!"},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"summary-path-forward","title":"Summary: The BFS Algorithm","content":[{"data":{"content":"We've established a deep understanding of the BFS algorithm's mechanics. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**BFS explores level-by-level** — Vertices are discovered and processed in order of their distance from the source, like ripples expanding outward.","**The queue is essential** — FIFO ordering ensures all distance-d vertices are processed before any distance-(d+1) vertices. Replace the queue with a stack, and you get DFS instead.","**BFS computes shortest paths** — In unweighted graphs, BFS naturally discovers shortest paths because it visits vertices in distance order.","**Mark visited upon enqueueing** — To avoid duplicate processing and correctness issues, mark vertices as discovered immediately when adding to the queue.","**The BFS tree encodes paths** — Parent pointers form a tree where every root-to-vertex path is a shortest path in the original graph.","**Only works for unweighted graphs** — BFS assumes all edges have equal cost. For weighted graphs, use Dijkstra's or Bellman-Ford algorithm."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nNow that we understand the BFS algorithm mechanically, the next page explores **Queue-Based Exploration** in greater depth—examining the queue invariants, memory behavior, and optimization techniques that make BFS practical for large-scale graphs."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a deep understanding of the BFS algorithm's mechanics. You understand how the queue orchestrates level-by-level exploration, why this naturally produces shortest paths in unweighted graphs, and how to implement BFS correctly. Next, we'll explore queue-based exploration in greater depth.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":6}],"isLocked":false},{"id":"seed_278367f6f5ed1dcd380afb2cc24a1c16","title":"Queue-Based Exploration — The Engine Behind Level-Order Traversal","order":1,"content":null,"isLocked":true},{"id":"seed_c96248ef149c6c2ab0e70c929697bf5a","title":"Level-by-Level Traversal — The Power of Layered Exploration","order":2,"content":null,"isLocked":true},{"id":"seed_1b13ce0c76166f761ac7e271c8cc3473","title":"Time Complexity O(V + E) — Understanding Why BFS Is Efficient","order":3,"content":null,"isLocked":true},{"id":"seed_8be4db65c11696eba341104728d5839f","title":"BFS Applications — Shortest Path (Unweighted) and Beyond","order":4,"content":null,"isLocked":true}]}}