图

副标题 / 摘要 Clone Graph 不是单纯的图遍历题，而是“带环对象图的深拷贝”题。真正的关键不是能不能走完图，而是如何保证每个原节点只克隆一次，并且所有边都指向克隆图中的新节点。 预计阅读时长：12~15 分钟 标签：图、DFS、BFS、哈希表、深拷贝 SEO 关键词：克隆图, Clone Graph, 图深拷贝, LeetCode 133, DFS, BFS 元描述：通过“原节点 -> 新节点”映射表实现无向图深拷贝，讲清 DFS/BFS、环处理、复杂度与多语言代码。 目标读者 刷 LeetCode 图论题、希望掌握“深拷贝 + visited/map”模板的学习者 需要复制对象图、工作流图、拓扑结构的工程师 经常在“图遍历”和“对象复制”之间混淆的开发者 背景 / 动机 很多同学第一次做这题，会把它当成普通遍历题： DFS 一遍 BFS 一遍 把值抄过去 但真正难点在于： 图里可能有环 同一个节点可能从多条路径访问到 复制出来的新图，所有邻居必须指向“新节点”，不能混入旧节点引用 所以这题本质上是： 带环对象图的深拷贝问题 这类模式在工程里也很常见： 复制流程编排图 克隆编辑器里的节点网络 复制依赖关系图做快照 核心概念 深拷贝：返回的新图里每个节点都必须是新建对象 节点身份：判断“是不是同一个节点”看的是对象身份 / 引用，不只是 val 邻接关系保持：新图的边结构必须与原图完全一致 映射表：原节点 -> 克隆节点，既防止死循环，也防止重复创建 A — Algorithm（题目与算法） 题目重述 给定一个无向连通图中某个节点 node 的引用，请返回这个图的深拷贝。 每个节点结构如下： class Node { public int val; public List<Node> neighbors; } 题目测试用例使用邻接表表示图。 如果图不为空，给定节点总是值为 1 的节点。 ...

副标题 / 摘要 社区发现不是“把图分几堆”这么简单，而是要在准确性、可解释性、速度和可维护性之间做平衡。本文按 ACERS 结构拆解两种工程最常见算法：Louvain（模块度优化） 与 Label Propagation（标签传播）。 预计阅读时长：12~16 分钟 标签：社区发现、Louvain、Label Propagation、图分区 SEO 关键词：community detection, Louvain, Label Propagation, modularity, graph partition 元描述：社区发现工程入门：Louvain 与 LPA 的原理、复杂度、选型与落地模板，覆盖群体识别、图分区、冷启动分析。 目标读者 做社交图、风控图、推荐系统图分析的工程师 想把“社区发现”从论文概念落到生产实践的开发者 需要在“图分区/冷启动”场景做群体结构建模的人 背景 / 动机 社区发现在工程里很常见： 群体识别：识别强关联账号簇、异常团伙、兴趣圈层 图分区：把高连通子图放在同一分片，减少跨分片通信 冷启动分析：新用户/新实体通过邻域社区快速归类 痛点在于： 全局最优通常不可得（NP-hard 相关目标） 数据规模大、更新快，离线算法难以频繁重跑 不同业务对“稳定性/速度/解释性”优先级不同 所以工程上最常见的两类方法是： Louvain：追求较高质量社区（模块度） Label Propagation (LPA)：追求速度与简单实现 核心概念 概念 含义 工程影响 Community 内部边密、外部边疏的节点集合 影响分区与推荐质量 Modularity(Q) 度量社区划分质量的指标 Louvain 优化目标 Label Propagation 节点迭代采用邻居主流标签 速度快、结果有随机性 Graph Partition 按社区切分存储/计算 降低跨机通信成本 Cold Start 用邻域结构给新节点快速归群 提升启动期召回 A — Algorithm（题目与算法） 题目还原（工程抽象版） 给定无向图 G=(V,E)，输出每个节点所属社区 ID，并支持以下用途： ...

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

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

副标题 / 摘要 随机迷宫生成常用深度优先回溯法。本文解释思路并提供可运行实现。 目标读者 学习图算法的开发者 想做程序化生成的工程师 算法入门学习者 背景 / 动机 迷宫生成是图遍历与随机化的经典结合。 它能帮助理解 DFS、回溯与边界处理。 核心概念 网格图：迷宫格点和通道 DFS 回溯：随机探索与回退 墙与通路：用字符表示结构 实践指南 / 步骤 初始化全墙网格 从起点开始 DFS 随机选择未访问邻居并打通墙 回溯直到全部访问完成 可运行示例 import random def maze(w, h): grid = [["#"] * (2 * w + 1) for _ in range(2 * h + 1)] visited = [[False] * w for _ in range(h)] def carve(x, y): visited[y][x] = True dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] random.shuffle(dirs) for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx < w and 0 <= ny < h and not visited[ny][nx]: grid[y * 2 + 1 + dy][x * 2 + 1 + dx] = " " grid[y * 2 + 1][x * 2 + 1] = " " grid[ny * 2 + 1][nx * 2 + 1] = " " carve(nx, ny) carve(0, 0) return "\n".join("".join(row) for row in grid) if __name__ == "__main__": print(maze(6, 4)) 解释与原理 DFS 回溯保证每个格子被访问一次，随机方向带来多样性。 打通墙壁即可形成迷宫通路。 ...