🔄 复习日 / Review Day 120 — 2026-08-26
📊 NeetCode: 94/150 · SysDesign: 60/40 · Behavioral: 60/40 · Frontend: 37/50 · AI: 30/30
🔥 2-day streak!
🔄 复习日 / Review Day
今天是复习日！回顾过去4天的内容。
过去4天全是图算法精华 — Union-Find、双向BFS、最小生成树、Dijkstra。全部融会贯通了吗？
📝 Quick Quiz — 3 Mini-Reviews
Q1: [💻 Algorithms — Union-Find] Day 116: Redundant Connection
在一棵有 n 个节点的树上多加了一条边，构成了一个图。你的 Union-Find 解法需要找到这条"冗余边"。
问题： union(u, v) 时，你发现 find(u) == find(v)，这意味着什么？为什么这条边就是答案？
When running Union-Find on edges in order, what does it mean when find(u) == find(v) before calling union(u, v)? Why is this edge the answer?
<details><summary>显示答案 / Show Answer</summary>
find(u) == find(v) 意味着 u 和 v 已经在同一个连通分量中，即加这条边之前它们已经连通。所以这条边是"多余的"——它创造了环。
在遍历所有边并依次 union 的过程中，第一条导致 find(u) == find(v) 的边，就是形成环的那条边，也就是题目要返回的冗余连接。
关键洞察： Union-Find 天然适合检测环——每次 union 前先 find，相同则有环。时间复杂度近似 O(n·α(n))，α 是反阿克曼函数，实际上接近 O(1)。
It means u and v are already in the same connected component — they were connected before this edge was added. So this edge creates a cycle and is therefore "redundant." The first edge where find(u) == find(v) is the answer. Key insight: Union-Find is the perfect cycle-detection tool for undirected graphs.
</details>
Q2: [🔍 Graph Search — BFS] Day 117: Word Ladder (双向 BFS Deep Dive)
单向 BFS 从 beginWord 出发，搜索整个词图。双向 BFS 则从两端同时出发。
问题： 为什么双向 BFS 在最坏情况下比单向 BFS 快？用 branching factor b 和最短路径长度 d 来量化说明。
Why is bidirectional BFS faster than unidirectional BFS in the worst case? Quantify using branching factor b and shortest path length d.
<details><summary>显示答案 / Show Answer</summary>
单向 BFS 在深度 d 处最多扩展 O(b^d) 个节点。
双向 BFS 从两端同时搜索，每端只需搜到深度 d/2，两端各扩展 O(b^(d/2)) 个节点，总共 O(2 · b^(d/2)) = O(b^(d/2))。
当 b=26（26个字母替换）、d=10 时：
- 单向：26^10 ≈ 141万亿个节点
- 双向：2 × 26^5 ≈ 2376万个节点 — 快了约594万倍！
实现技巧： 每轮选择较小的那一端来扩展，保证两端平衡增长，效果最佳。终止条件：扩展出的邻居出现在对面的 visited set 中。
Unidirectional BFS explores O(b^d) nodes. Bidirectional only goes to depth d/2 from each end: O(b^(d/2)) each, total O(b^(d/2)) — exponentially faster. With b=26, d=10: unidirectional ~1.4 trillion vs bidirectional ~24 million nodes.
</details>
Q3: [📡 Graph Algorithms — Shortest Path] Days 118–119: MST vs Dijkstra
Day 118 用 Prim's/Kruskal's 求"最小生成树"（Min Cost to Connect All Points）；Day 119 用 Dijkstra 求"最短路径"（Network Delay Time）。
问题： 这两类问题看起来很像，但目标完全不同。请解释：在"连接所有点的最小总费用"中为什么不能直接用 Dijkstra？MST 和最短路径的核心区别是什么？
Why can't you directly use Dijkstra to find the minimum cost to connect all points? What's the fundamental difference between MST and shortest path?
<details><summary>显示答案 / Show Answer</summary>
Dijkstra 找的是：从源点到每个节点的最短路径（路径上的边权之和最小）。它关心的是"我怎么从A走到B最省力"。
MST（最小生成树） 找的是：用最少的总边权连接所有节点，形成一棵树（无环连通图）。它关心的是"用最少的总花费把所有点串联起来"。
如果用 Dijkstra：它可能选一条很长的路连接某个点（因为那是从源点最短的路），但这条路的边对 MST 来说是冗余的。Dijkstra 不会尝试通过其他中间节点来构建生成树。
一句话区别： Dijkstra 优化单源到所有点的距离；Prim's/Kruskal's 优化所有边的总权重，使图联通。
Dijkstra minimizes the path cost from one source to all nodes. MST minimizes the total edge weight to connect ALL nodes as a tree. They optimize different objectives — Dijkstra doesn't guarantee a spanning tree, and Prim's doesn't guarantee shortest paths. Use Dijkstra for "cheapest route," use Prim's/Kruskal's for "cheapest wiring."
</details>
💡 复习巩固记忆，螺旋式上升。图算法三剑客：Union-Find、BFS/双向BFS、Dijkstra/Prim's — 各司其职，掌握边界条件。
📅 明天继续新内容！Day 121 coming up.