DFS

副标题 / 摘要 连通分量是图算法的基础地基：无向图关注“是否连在一起”，有向图关注“是否互相可达”。本文按 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)： ...

副标题 / 摘要 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： ...

副标题 / 摘要 “路径不必从根开始、但必须向下”使得这题无法用简单的根到叶 DP 解决。本文用 ACERS 结构讲透 树上前缀和：把任意向下路径转化为“两个前缀和的差”，用哈希表在线计数，做到 O(n) 一次 DFS 统计所有答案。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、前缀和、DFS、哈希表 SEO 关键词：Path Sum III, 路径和 III, 树上前缀和, 前缀和哈希, LeetCode 437, Hot100 元描述：前缀和 + 哈希表在线统计二叉树向下路径和等于 targetSum 的条数，包含推导、复杂度对比与多语言实现。 目标读者 刷 LeetCode、希望把“树 + 哈希”题型沉淀成模板的学习者 对“路径不从根开始”的树题容易写成 O(n^2) 的同学 做日志调用链 / 层级数据分析，需要在树结构上做区间统计的工程师 背景 / 动机 很多“树上的路径问题”都有一个坑： 你以为要从根出发、或要到叶子结束，但题目允许 从任意节点开始、到任意节点结束（但方向必须向下）。 这意味着： 你不能只维护“从根到当前”的一种状态就完事； 也不能枚举所有起点（那会退化成 O(n^2)）； 更不能用滑动窗口（节点值可正可负，窗口单调性不存在）。 这题最值得掌握的点是：把“树上任意向下路径”化为“同一路径上的两个前缀和之差”。 一旦你掌握了这个模型，很多树上统计题都会变成“前缀和 + 哈希表”的熟悉配方。 核心概念 向下路径：只能从父到子（不能回头、不能跨分支） 前缀和（prefix sum）：从根到当前节点路径上所有节点值的累加 差分计数：若 curSum - prevSum = target，则 prevSum = curSum - target 路径内哈希表：只统计“当前 DFS 路径上的前缀和”，回溯时必须撤销（否则会把不同分支混在一起） A — Algorithm（题目与算法） 题目还原 给定一个二叉树的根节点 root 和整数 targetSum，求二叉树里 节点值之和等于 targetSum 的向下路径 的数目。 路径不需要从根节点开始，也不需要在叶子节点结束，但路径方向必须向下（只能从父节点到子节点）。 ...