🏗️ System Design — Synthesis (Expert Phase, Day 106)

Saturday — Deep Dive day. System Design section is in synthesis mode (all 60 curated topics exhausted).

Today's Synthesis Note

Today's Saturday Deep Dive focuses on 图遍历模式 — BFS/DFS 精讲 (Graph Traversal Patterns). The full deep-dive content is in 2026-08-01-deepdive.md (./2026-08-01-deepdive.md).

Graph traversal underpins many system design concepts covered this program: CDN cache invalidation (multi-source BFS), microservice dependency detection (topological sort), geospatial systems (BFS on grids), and distributed systems failure propagation analysis.

🧮 Rotting Oranges (LeetCode #994) — BFS Deep Dive

Note: This is a Saturday. The full content for this topic is in the Saturday Deep Dive (./2026-08-01-deepdive.md). This file is a reference stub.

Quick Summary

• Pattern: Graphs — Multi-Source BFS
• LeetCode: https://leetcode.com/problems/rotting-oranges/
• NeetCode: https://www.youtube.com/watch?v=y704fEOx0s0
• Difficulty: Medium

Core Idea

Multi-source BFS: enqueue all initially rotten oranges simultaneously at time=0, then spread. Track fresh_count to detect unreachable oranges.

See Saturday Deep Dive (./2026-08-01-deepdive.md) for complete theory, implementation, edge cases, and interview Q&A.

💬 Behavioral / Soft Skills — Synthesis (Expert Phase, Day 106)

Saturday — Deep Dive day. Behavioral section is in synthesis mode (all 60 curated questions exhausted).

Today's Synthesis Note

Today's Saturday Deep Dive covers graph traversal patterns. The full deep-dive content is in 2026-08-01-deepdive.md (./2026-08-01-deepdive.md).

Synthesis theme: Graph-structured thinking appears in engineering leadership too — mapping team dependencies (topological sort), understanding how failures propagate across teams (BFS), and finding shortest paths to unblock teammates. The mental models transfer.

🤖 AI Concepts — Synthesis (Expert Phase, Day 106)

Saturday — Deep Dive day. AI section is in synthesis mode (all 30 curated concepts exhausted).

Today's Synthesis Note

Today's Saturday Deep Dive covers graph traversal patterns. The full deep-dive content is in 2026-08-01-deepdive.md (./2026-08-01-deepdive.md).

Synthesis note: Graph traversal is foundational to modern AI systems: knowledge graphs use BFS for entity relationship traversal; RAG pipelines use graph-based chunking; neural network backpropagation is a topological sort over the computation graph; agent planning (ReAct) builds DAGs of tool calls. The patterns learned today are literally inside every major AI framework.

🔬 Saturday Deep Dive: 图遍历模式 — BFS/DFS 精讲 (15 min read)

📊 NeetCode: 84/150 · SysDesign: 60/60 · Behavioral: 60/60 · Frontend: 37/50 · AI: 30/30

🔥 106-day streak!

Overview / 概述

图遍历是算法面试的核心骨架。几乎所有涉及"连通性"、"最短路径"、"依赖关系"的问题，底层都是一张图。掌握图遍历，等于掌握了以下所有题型的通解：岛屿计数、课程表调度、单词接龙、腐烂的橘子……

Graph traversal is the backbone of coding interviews. Nearly every problem involving "connectivity," "shortest path," or "dependencies" is secretly a graph problem. Master BFS/DFS, and you unlock: island counting, course scheduling, word ladders, rotting oranges, and much more.

核心问题 / Core question: 给定起点，你能到达哪里？到达需要多少步？图是否有环？

Core question: From a starting node, what can you reach? In how many steps? Does the graph have a cycle?

Part 1: Theory / 理论基础 (5 min)

两把钥匙 / Two Keys

BFS（广度优先搜索）        DFS（深度优先搜索）
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
数据结构: queue (deque)    数据结构: stack（或递归调用栈）
遍历顺序: 层层扩展          遍历顺序: 一条路走到底
擅长:    最短路径（无权图）   擅长:    连通性、路径枚举、环检测
时间:    O(V+E)            时间:    O(V+E)
空间:    O(V)              空间:    O(V)（栈深度）

BFS 就像石头投入水中的涟漪——从起点向外一圈圈扩散。每一圈代表"距离起点 k 步"的所有节点。

BFS is like ripples in water — it expands outward layer by layer. Each layer = all nodes exactly k steps away.

DFS 就像走迷宫——沿一条路走到底，退回来再走另一条。

DFS is like navigating a maze — go as deep as possible, then backtrack.

图的四种常见形式 / Four Common Graph Forms

visited 集合：防止死循环 / Preventing Infinite Loops

visited = set()
visited.add(start)     # BFS: 入队时标记
visited.add(node)      # DFS: 进入时标记

关键陷阱 / Key trap: BFS 必须在入队时标记 visited，而不是出队时。否则同一节点会被入队多次，时间复杂度退化为指数级。

Key trap: In BFS, mark visited when enqueuing, not when dequeuing. Otherwise the same node gets enqueued multiple times, exploding complexity.

多源 BFS（Multi-Source BFS）

这是今天的重点之一。普通 BFS 从单个起点出发，多源 BFS 从所有起点同时出发。

Standard BFS starts from one source. Multi-source BFS starts from all sources simultaneously — as if they're all at distance 0.

适用场景 / When to use: 当有多个"源"且你想知道每个节点距离"最近的源"有多远时。

Use when: You have multiple "sources" and want the distance from each cell to the nearest source.

例题：腐烂的橘子 (Rotting Oranges, #994) — 多个腐烂橘子同时向外蔓延。

Example: Rotting Oranges (#994) — multiple rotten oranges spread simultaneously.

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

2.1 模板代码 / Template Code

from collections import deque

# ──────────────────────────────────────────────
# BFS Template (single source, returns distances)
# ──────────────────────────────────────────────
def bfs(graph: dict, start) -> dict:
    dist = {start: 0}          # tracks visited + distance
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in dist:   # not visited yet
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)  # mark on enqueue!
    
    return dist


# ──────────────────────────────────────────────
# DFS Template (iterative, single source)
# ──────────────────────────────────────────────
def dfs(graph: dict, start) -> set:
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    
    return visited


# ──────────────────────────────────────────────
# Grid BFS Template (4-directional)
# ──────────────────────────────────────────────
def grid_bfs(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    visited = set()
    visited.add((start_r, start_c))
    queue = deque([(start_r, start_c, 0)])  # (row, col, distance)
    
    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and          # in bounds
                0 <= nc < cols and          # in bounds
                (nr, nc) not in visited and  # not visited
                grid[nr][nc] != 0):          # not blocked
                
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

2.2 Rotting Oranges — 多源 BFS 完整实现

🔗 LeetCode: https://leetcode.com/problems/rotting-oranges/

📹 NeetCode: https://www.youtube.com/watch?v=y704fEOx0s0

问题 / Problem: 网格中，0=空，1=新鲜橘子，2=腐烂橘子。每分钟，腐烂橘子使4邻格的新鲜橘子腐烂。返回所有橘子腐烂所需的最少分钟数，如果不可能则返回 -1。

Grid: 0=empty, 1=fresh orange, 2=rotten orange. Each minute, rotten oranges rot adjacent fresh ones. Return minimum minutes to rot all, or -1 if impossible.

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Step 1: Find all initial rotten oranges (multi-sources)
    # and count fresh oranges
    queue = deque()
    fresh_count = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh_count += 1
    
    # Edge case: no fresh oranges at all
    if fresh_count == 0:
        return 0
    
    # Step 2: Multi-source BFS — all rotten oranges spread simultaneously
    max_time = 0
    
    while queue:
        r, c, time = queue.popleft()
        
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            
            # Check bounds and freshness
            if (0 <= nr < rows and
                0 <= nc < cols and
                grid[nr][nc] == 1):        # only fresh oranges
                
                grid[nr][nc] = 2           # mark as rotten (in-place = visited)
                fresh_count -= 1           # one fewer fresh orange
                max_time = max(max_time, time + 1)
                queue.append((nr, nc, time + 1))
    
    # Step 3: If fresh_count > 0, some oranges are unreachable
    return max_time if fresh_count == 0 else -1

关键洞察 / Key insights:

1. 多源同时出发：把所有初始腐烂橘子一次性加入队列，它们"同时"开始蔓延，自动计算出正确的"最早腐烂时间"。

All sources start simultaneously: Add all initial rotten oranges to the queue at once. They spread at the same rate, so BFS naturally finds the minimum time.

1. 原地标记已访问：直接将 grid[nr][nc] 改为 2 即可标记"已访问"，无需额外的 visited 集合。

In-place visited marking: Mutate grid[nr][nc] = 2 to mark visited — no extra set needed.

1. 最终检查：用 fresh_count 判断是否有孤岛（被 0 包围的新鲜橘子）。

Final check: fresh_count > 0 means isolated fresh oranges exist (surrounded by empty cells).

2.3 相关变体 — 从"腐烂橘子"到"最短路径" / Variants

Walls and Gates (#286)：把所有 gates（值为0的格子）同时加入队列，BFS 向外扩散填写距离。和腐烂橘子完全同构。

Walls and Gates: Add all gates simultaneously, BFS outward to fill distances. Identical structure to Rotting Oranges.

def wallsAndGates(rooms):
    rows, cols = len(rooms), len(rooms[0])
    DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
    INF = 2**31 - 1
    
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:        # gate = source
                queue.append((r, c))
    
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and
                0 <= nc < cols and
                rooms[nr][nc] == INF):   # unvisited room
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

2.4 DFS 的经典用法 — 岛屿计数 / Classic DFS: Number of Islands

🔗 https://leetcode.com/problems/number-of-islands/

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        # Base cases: out of bounds or water or already visited
        if (r < 0 or r >= rows or
            c < 0 or c >= cols or
            grid[r][c] != '1'):
            return
        
        grid[r][c] = '0'   # mark visited (sink the land)
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)   # flood-fill this island
    
    return count

DFS 在这里更自然：我们不关心距离，只关心"连通分量"的数量。每次遇到陆地，DFS 淹没整座岛，count += 1。

DFS is more natural here: We don't care about distances, only the number of connected components. Each time we hit land, DFS floods the whole island, count += 1.

2.5 拓扑排序 — 课程表 / Topological Sort: Course Schedule

🔗 https://leetcode.com/problems/course-schedule/

图论的杀手锏之一：有向无环图（DAG）的拓扑排序，解决"依赖关系"问题。

One of graph theory's most powerful tools: topological sort on a DAG solves dependency ordering problems.

from collections import deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # Build adjacency list and in-degree array
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)   # prereq → course
        in_degree[course] += 1
    
    # Kahn's Algorithm: start with nodes that have no prerequisites
    queue = deque()
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)
    
    completed = 0
    while queue:
        course = queue.popleft()
        completed += 1
        
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:   # all prereqs satisfied
                queue.append(next_course)
    
    # If we completed all courses, no cycle exists
    return completed == numCourses

直觉 / Intuition: 拓扑排序 = BFS on in-degree。每次取"没有前置依赖的节点"，处理后更新其邻居的 in-degree。如果最终处理了所有节点，说明无环。

Intuition: Topological sort = BFS on in-degrees. Take nodes with no remaining prerequisites, process them, then reduce their successors' in-degrees. If all nodes processed → no cycle.

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

🚨 常见错误 / Common Mistakes

1. BFS 出队时才 mark visited（不是入队时）

# ❌ WRONG — same node enqueued multiple times
while queue:
    node = queue.popleft()
    visited.add(node)           # too late!
    for neighbor in graph[node]:
        if neighbor not in visited:
            queue.append(neighbor)

# ✅ CORRECT — mark on enqueue
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)   # mark on enqueue
            queue.append(neighbor)

2. 网格越界检查顺序错误（短路求值救你）

# ✅ bounds check BEFORE accessing grid[nr][nc]
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
#   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
#   Python short-circuits: if bounds fail, grid access never happens

3. 多源 BFS 忘记处理"全部已腐烂"边界

if fresh_count == 0:
    return 0   # Don't run BFS at all — answer is already 0

4. 拓扑排序中漏掉孤立节点

初始化时，所有 in-degree == 0 的节点（包括没有任何依赖的独立课程）都要加入队列。

When initializing, add ALL nodes with in-degree == 0 to the queue, including isolated nodes with no edges.

5. 递归 DFS 的栈溢出

大网格（比如 300×300）可能导致递归深度达到 90000，超出 Python 默认栈限制。生产中优先用迭代 DFS 或 BFS。

Large grids (e.g., 300×300) can push recursion depth to 90,000+, exceeding Python's default limit. Use iterative DFS or BFS in production.

Part 4: Real-World Application / 实际应用 (2 min)

图遍历无处不在，只是通常不叫"BFS/DFS"：

BFS/DFS is everywhere in production — it just doesn't wear the label:

真实案例 / Real example: 当 Netflix 一个微服务宕机时，SRE 工具用 BFS 遍历服务依赖图来计算"受影响的下游服务"。这和腐烂橘子的多源 BFS 在结构上完全相同。

Real example: When a Netflix microservice fails, the SRE tooling uses BFS on the service dependency graph to compute "affected downstream services" — structurally identical to Rotting Oranges' multi-source BFS.

Part 5: Interview Simulation / 面试模拟 (3 min)

Q1: 腐烂橘子为什么用 BFS 而不是 DFS？

Q1: Why BFS instead of DFS for Rotting Oranges?

A: BFS 天然保证"按层扩展"，即每一轮处理的都是同一时刻腐烂的橘子。DFS 会优先向某个方向深入，无法正确模拟"同时蔓延"。凡是"最短时间/步数"问题，首选 BFS。

A: BFS expands level by level, correctly simulating "all oranges rot simultaneously." DFS would go deep in one direction first, giving wrong timing. For "minimum time/steps," always reach for BFS first.

Q2: 什么时候用多源 BFS？

Q2: When do you use multi-source BFS?

A: 当有多个起点，且你想知道每个节点到"最近起点"的距离时。实现方式：初始化时将所有起点同时入队（距离=0），之后标准 BFS 即可。同一个框架适用于：腐烂橘子、Walls and Gates、矩阵中的 01 矩阵（#542）。

A: When you have multiple sources and want each node's distance to the nearest source. Initialize by enqueuing all sources at distance 0, then run standard BFS. Works for: Rotting Oranges, Walls and Gates, 01 Matrix (#542).

Q3: 如何判断一道题是 BFS 还是 DFS？

Q3: How do you decide between BFS and DFS?

A: 经验法则：

• 需要"最短路径"或"最少步数" → BFS
• 需要"是否可达"或"连通分量数" → DFS 或 BFS 均可，DFS 递归更简洁
• 需要"所有路径"或"回溯" → DFS
• 有拓扑依赖/环检测 → BFS（Kahn）或 DFS（颜色标记）

A (rule of thumb):

• "Shortest path / minimum steps" → BFS
• "Reachability / connected components" → either; DFS is simpler recursively
• "All paths / backtracking" → DFS
• "Topological order / cycle detection" → BFS (Kahn's) or DFS (coloring)

Q4: 如果图很大（100万节点），递归 DFS 会有什么问题？

Q4: What's the problem with recursive DFS on a very large graph?

A: Python 默认递归深度限制约 1000（sys.getrecursionlimit()）。百万节点的图会立即栈溢出。解决方案：

1. 迭代 DFS（用显式栈）
2. sys.setrecursionlimit(10**6)（生产代码中不推荐）
3. 换用 BFS（天然迭代）

A: Python's default recursion limit is ~1000 (sys.getrecursionlimit()). A million-node graph stack-overflows immediately. Solutions: (1) iterative DFS with explicit stack, (2) sys.setrecursionlimit() (not recommended in production), (3) use BFS (inherently iterative).

Q5: 请描述 Kahn 算法和 DFS 拓扑排序的区别，各在什么场景下更合适？

Q5: Compare Kahn's algorithm vs DFS-based topological sort — when would you prefer each?

A:

• Kahn（BFS）：迭代，直接输出拓扑序，环检测简单（最后 completed == numNodes），适合生产代码。同时也可以输出所有可能的拓扑序（加个优先队列）。
• DFS 拓扑排序：递归，后序遍历（完成时入栈），代码更短，但需要额外的"颜色标记"（白/灰/黑）来检测环。适合需要递归实现的场景。

A:

• Kahn (BFS): Iterative, outputs topological order directly, simple cycle detection (completed == numNodes). Preferred in production. Also supports lexicographically smallest order with a min-heap.
• DFS topological sort: Recursive, uses post-order (push on finish), shorter code but needs three-color marking (white/gray/black) for cycle detection. Better when recursive style is preferred.

总结 / Summary

本周练习题 / Practice This Week:

• #994 Rotting Oranges → 多源 BFS
• #200 Number of Islands → DFS 连通分量
• #207 Course Schedule → Kahn 拓扑排序
• #127 Word Ladder → 隐式图 BFS（Hard，本模式的终极题）