逻辑与算法

围绕 k-hop 与可达性查询，讲清 BFS+hop 限制、传递闭包取舍、以及位图索引/2-hop labeling 的工程落地路径。

副标题 / 摘要 连通分量是图算法的基础地基：无向图关注“是否连在一起”，有向图关注“是否互相可达”。本文按 ACERS 模板，从朴素做法推导到 Tarjan / Kosaraju，并给出图数据库落地场景与多语言可运行实现。 预计阅读时长：14~18 分钟 标签：图论、连通分量、SCC、Tarjan SEO 关键词：Connected Components, SCC, Tarjan, Kosaraju, 图数据库 元描述：从无向连通分量到有向强连通分量，讲清 Tarjan/Kosaraju 的核心机制、复杂度和工程落地。 目标读者 需要把 BFS/DFS 用到“滚瓜烂熟”的算法学习者 在图数据库场景做子图分析、分片规划的工程师 想建立“无向 CC + 有向 SCC”统一认知框架的中级开发者 背景 / 动机 工程里你会很快遇到这三类问题： 这批节点是否天然分成多个互不相连的群？（无向图连通分量） 哪些节点形成“互相可达”的强闭环？（有向图 SCC） 如何把大图切成更可并行、更易缓存、更易分片的子图？ 如果只会 BFS/DFS 但不会“分量视角”，你会反复做可达性查询，成本高且难维护。 连通分量算法的价值是：一次全图扫描，把局部查询变成 O(1) 的分量 ID 比较。 核心概念 Connected Components（CC）：无向图中，任意两点都可达的最大节点集合 Strongly Connected Components（SCC）：有向图中，任意两点互相可达的最大节点集合 Condensation DAG（缩点图）：把每个 SCC 缩成一个点后得到的有向无环图 Tarjan 核心状态：dfn[u]（时间戳），low[u]（可回溯到的最小时间戳），栈与 in_stack Kosaraju 核心流程：原图按完成时序排序 + 反图二次 DFS A — Algorithm（题目与算法） 题目还原（工程化表述） 给定一个图 G=(V,E)： ...

副标题 / 摘要 最短路径不是一道题，而是一组“按图条件选算法”的工程能力。本文按 ACERS 结构拆解 BFS（无权）/ Dijkstra（非负权）/ A（启发式）*，并给出你在关系图、推荐链路、路径解释里真正会用到的优化模板。 预计阅读时长：14~18 分钟 标签：图论、最短路径、BFS、Dijkstra、A* SEO 关键词：最短路径, BFS, Dijkstra, A*, 双向搜索, 多源 BFS 元描述：最短路径三件套工程指南：算法边界、复杂度、可运行代码、优化策略与实战场景。 目标读者 正在补图算法基础，希望形成可复用工程模板的学习者 做社交关系链路、推荐路径、图查询解释的后端/算法工程师 对 BFS、Dijkstra、A* 都“知道名字”，但选型和优化还不稳定的开发者 背景 / 动机 最短路径问题常见于： 社交网络里的最短关系链路（几跳可达） 推荐系统里的最小代价路径（多目标折中） 可解释系统里的“为什么推荐给你”路径展示 工程里最容易犯的错误是“只会一个算法硬套全部场景”： 用 BFS 跑加权图，结果错但不报错 用 Dijkstra 跑负权边，得到不可靠结果 用 A* 但启发函数不合格，性能退化成 Dijkstra 本质上，最短路径应先做 图条件分类，再做算法选型。 核心概念 算法 适用图 最优性条件 典型复杂度 关键词 BFS 无权图 / 等权图 按层首次到达即最短边数 O(V+E) queue, level Dijkstra 非负权图 堆顶弹出的节点距离已最优 O((V+E)logV) relaxation, min-heap A* 非负权图 + 启发式 h(n) 可采纳（不高估） 最坏同 Dijkstra，平均更快 f=g+h 关键公式： ...

副标题 / 摘要 BFS / DFS 不是“会写就行”，而是要到工程可用、可控成本、可证明正确。本文按 ACERS 模板，把最常用的三类任务（k-hop 查询、子图抽取、路径可达性）拆成可复用模板：迭代实现 + early stop + visited 结构选型。 预计阅读时长：12~16 分钟 标签：图、BFS、DFS、k-hop、子图抽取 SEO 关键词：BFS, DFS, k-hop 查询, 子图抽取, 路径可达性, visited bitmap, bloom filter 元描述：面向工程场景讲解 BFS/DFS：迭代版避免栈溢出、early stop 降低搜索成本、visited bitmap/bloom 优化内存与判重性能。 目标读者 正在做图数据库、风控关系图、调用链分析的工程师 只会“题解式 BFS/DFS”，但还没形成工程模板的同学 希望把图遍历写成“稳定、可观测、可扩展”代码的人 背景 / 动机 在工程里，BFS/DFS 通常不是一次性离线脚本，而是在线请求的一部分： k-hop 邻域查询要控制时延 子图抽取要控制内存与输出规模 路径可达性要快速返回 true/false 如果只停留在教科书递归模板，会很快踩坑： 深图导致递归栈溢出 无剪枝导致无谓扩展 visited 结构选错，内存和吞吐同时恶化 所以这篇文章聚焦一个目标： 把 BFS / DFS 升级到“滚瓜烂熟且能上线”的程度。 核心概念 概念 作用 工程关注点 BFS（队列） 按层扩展、天然支持 hop 层级 适合 k-hop、最短边数、层级子图 DFS（栈） 深入探索、路径存在性高效 适合快速可达性判断与深度剪枝 early stop 提前终止搜索 控制 P99 延迟和资源消耗 visited bitmap 精确判重，内存紧凑 需先做节点 ID 压缩 bloom filter 概率判重/预过滤 有假阳性，不能单独用于“严格正确性”场景 A — Algorithm（题目与算法） 题目还原（LeetCode 风格训练题） 给定一个无权图 G（邻接表），起点 s，最大跳数 K，可选目标点 t： ...

副标题 / 摘要 REPL 是交互式程序的最小形态。本文先构建 echo REPL，再扩展为逆波兰计算器。 目标读者 想练习解析与交互程序的开发者 学习表达式求值的人 初中级算法学习者 背景 / 动机 交互式解释器是语言与工具链的核心。 从简单 REPL 演化到计算器，是理解解析流程的好练习。 核心概念 REPL：读入-求值-输出循环 逆波兰表达式（RPN）：无需括号的表达式形式 栈求值：用栈完成运算 实践指南 / 步骤 先实现 echo REPL（读入并输出） 加入退出指令（如 quit） 解析输入为 token 列表 用栈计算 RPN 表达式 可运行示例 import sys def eval_rpn(tokens): stack = [] for t in tokens: if t in {"+", "-", "*", "/"}: b = stack.pop() a = stack.pop() if t == "+": stack.append(a + b) elif t == "-": stack.append(a - b) elif t == "*": stack.append(a * b) else: stack.append(a / b) else: stack.append(float(t)) return stack[-1] def repl(): while True: line = input("> ").strip() if line == "quit": return if not line: continue try: tokens = line.split() print(eval_rpn(tokens)) except Exception as e: print("error:", e) if __name__ == "__main__": repl() 解释与原理 RPN 的关键是“运算符后置”，因此可以用栈自然求值。 REPL 只需持续读入、求值、输出即可。 ...

副标题 / 摘要 内存泄漏会让程序“越跑越慢”。本文用 C 示例展示泄漏原因，并给出基本规避方法。 目标读者 写过 C/C++ 的开发者 关注资源管理与稳定性的工程师 学习系统编程的读者 背景 / 动机 在手动内存管理语言中，忘记释放会导致内存逐渐耗尽。 长期运行服务最容易遭遇此类问题。 核心概念 内存分配：malloc/new 释放：free/delete 泄漏：分配后没有释放且失去引用 实践指南 / 步骤 所有分配都必须有对应释放 明确资源的所有权 使用工具检测泄漏（valgrind） 用 RAII 或智能指针减少风险 可运行示例 #include <stdlib.h> #include <stdio.h> int main() { for (int i = 0; i < 100000; i++) { char *p = (char *)malloc(1024); if (p == NULL) return 1; // 忘记 free(p); -> 内存泄漏 } printf("done\n"); return 0; } 解释与原理 每次 malloc 都会向堆申请内存，如果不释放，内存不会回收。 循环中持续泄漏最终会导致内存耗尽。 常见问题与注意事项 垃圾回收语言就不会泄漏吗？ 也可能“逻辑泄漏”，比如全局容器无限增长。 为什么泄漏很难发现？ 因为短期运行可能看不出问题。 工具有用吗？ 非常有用，建议上线前检查。 最佳实践与建议 用智能指针或 RAII 自动释放 对长期运行服务做内存监控 建立内存泄漏回归测试 小结 / 结论 内存泄漏是资源管理失控的典型问题。 通过明确所有权与工具检测，可以显著降低风险。 ...

副标题 / 摘要 内存无法容纳 10GB 数据时，外部排序是标准方案。本文介绍分块排序与多路归并。 目标读者 需要处理大文件的工程师 学习外部排序算法的读者 关注磁盘 I/O 优化的人 背景 / 动机 当数据量超过内存容量，传统内存排序会失败。 外部排序通过“分块 + 多路归并”解决问题。 核心概念 分块排序：把大文件拆成可放入内存的小块 多路归并：合并多个有序块 磁盘 I/O：顺序读写优于随机读写 实践指南 / 步骤 按内存容量分块读取 每块内存排序并写回磁盘 多路归并所有有序块 尽量顺序读写减少随机 I/O 可运行示例 # 简化示例：分块排序 + 归并 import heapq def merge_sorted(chunks): heap = [] for i, chunk in enumerate(chunks): if chunk: heapq.heappush(heap, (chunk[0], i, 0)) result = [] while heap: val, i, j = heapq.heappop(heap) result.append(val) if j + 1 < len(chunks[i]): heapq.heappush(heap, (chunks[i][j + 1], i, j + 1)) return result if __name__ == "__main__": chunks = [sorted([3, 1, 2]), sorted([9, 7, 8])] print(merge_sorted(chunks)) 解释与原理 外部排序的核心是把“大问题拆成小问题”，每块可在内存中排序。 最后通过多路归并生成整体有序序列。 ...

副标题 / 摘要 10TB 数据无法在单机完成排序。本文介绍分布式排序的核心流程与工程要点。 目标读者 处理大规模数据的工程师 学习分布式系统的开发者 关注数据处理流程的人 背景 / 动机 数据规模超过单机能力时，必须通过分布式拆分与并行归并完成排序。 这涉及数据切分、网络传输与容错。 核心概念 分片（Shard）：数据切分到多个节点 Shuffle：按 key 重新分配数据 分布式归并：跨节点合并有序块 实践指南 / 步骤 按范围或哈希切分数据 各节点本地排序 Shuffle 让相同范围的数据聚集 全局归并并输出结果 可运行示例 # 简化的“分片排序”示意 def shard_sort(chunks): return [sorted(c) for c in chunks] def merge_two(a, b): i = j = 0 res = [] while i < len(a) and j < len(b): if a[i] < b[j]: res.append(a[i]); i += 1 else: res.append(b[j]); j += 1 res.extend(a[i:]) res.extend(b[j:]) return res if __name__ == "__main__": shards = shard_sort([[3, 1], [4, 2]]) print(merge_two(shards[0], shards[1])) 解释与原理 分布式排序的关键在于“局部排序 + 全局归并”。 Shuffle 会成为主要瓶颈，需要优化网络与分区策略。 ...

副标题 / 摘要 碎片整理的目标是减少随机寻道，提高顺序读写性能。本文给出设计流程与简化实现。 目标读者 学习系统设计的开发者 关注存储性能的工程师 想理解“数据布局优化”的人 背景 / 动机 文件频繁增删会导致数据块分散。 碎片整理通过“重排布局”提升连续读写效率。 核心概念 碎片：文件块分散在多个位置 压缩（Compaction）：把数据块向前聚集 元数据更新：移动块后更新索引 实践指南 / 步骤 扫描磁盘找到空洞与数据块 规划移动顺序，避免覆盖 逐块移动并更新元数据 验证一致性并生成报告 可运行示例 # 简化模型：1 表示数据块，0 表示空洞 def defragment(blocks): write = 0 for read in range(len(blocks)): if blocks[read] == 1: blocks[write], blocks[read] = blocks[read], blocks[write] write += 1 return blocks if __name__ == "__main__": data = [1, 0, 1, 0, 1, 0, 0, 1] print(defragment(data)) 解释与原理 通过双指针把所有数据块向前移动，实现“紧凑布局”。 现实文件系统还需要处理文件连续性与元数据同步。 常见问题与注意事项 整理期间如何保证数据不丢？ 需要日志与校验。 整理会影响系统性能吗？ 会，通常在低峰期进行。 SSD 还需要碎片整理吗？ 需求较低，但仍需维护磨损均衡。 最佳实践与建议 使用快照或日志保护数据 控制整理窗口，避免影响业务 定期评估碎片率 小结 / 结论 碎片整理是“数据布局优化”的工程问题，需要性能与安全的平衡。 核心在于安全移动与元数据一致性。 ...

副标题 / 摘要 随机数生成是很多算法的基础。本文用线性同余法实现一个可复现的 rnd()。 目标读者 学习随机算法的开发者 需要理解 PRNG 的工程师 算法与系统基础学习者 背景 / 动机 大多数语言的随机数来自伪随机算法。 理解基础实现有助于评估随机性与可复现性。 核心概念 伪随机数（PRNG）：由公式生成的序列 种子（Seed）：决定序列起点 可复现性：同样种子产生相同序列 实践指南 / 步骤 选择线性同余参数 用种子初始化状态 每次调用更新状态并输出 将结果归一化到 [0,1) 可运行示例 class LCG: def __init__(self, seed=1): self.mod = 2 ** 31 self.a = 1103515245 self.c = 12345 self.state = seed def rnd(self): self.state = (self.a * self.state + self.c) % self.mod return self.state / self.mod if __name__ == "__main__": rng = LCG(seed=42) for _ in range(3): print(rng.rnd()) 解释与原理 线性同余法是最简单的 PRNG： state = (a * state + c) mod m。 它速度快，但随机性质量有限。 ...