多叉树 (N-ary Tree)

BFS

type: concept tags: [图遍历, 广度优先搜索, 算法] created: 2026-05-04 updated: 2026-05-04BFS（广度优先搜索）Breadth-First Search，广度优先搜索，是图遍历的两种基本方式之一。核心思想从起点开始，先访问所有距离为 1 的节点，再访问距离为 2 的节点，以此类推。就像水波一样一层层扩散。类比：湖面投石，涟漪一圈圈向外扩散。代码框架// 图的 BFS 遍历框架 void traverse(Graph graph, int s, boolean[] visited) { Queue<Integer> q = new LinkedList<>(); q.offer(s); visited[s] = true;

DFS

type: concept tags: [图遍历, 深度优先搜索, 算法] created: 2026-05-04 updated: 2026-05-04DFS（深度优先搜索）Depth-First Search，深度优先搜索，是图遍历的两种基本方式之一。核心思想沿着一条路径尽可能深地探索，直到无法继续（到达叶子节点或遇到已访问节点），然后回溯到上一个分叉点，继续探索其他路径。类比：走迷宫时，沿着一条路走到头，碰壁后返回最近的岔路口换条路。代码框架// 图的 DFS 遍历框架 void traverse(Graph graph, int s, boolean[] visited) { // base case if (s < 0 || s >= graph.size()) {

图

type: concept tags:图数据结构图论 created: 2026-05-04 updated: 2026-05-04图 (Graph)定义图是由若干**节点（Vertex）和边（Edge）**构成的数据结构，是对复杂网络关系的抽象。图可以看作是多叉树结构的延伸——多叉树只允许父节点指向子节点，而图中节点之间可以相互指向，形成更复杂的网络结构。基本组成| 组成 | 说明 | |------|------| | 节点 (Vertex) | 图的基本组成单元，每个节点有唯一标识 | | 边 (Edge) | 连接两个节点的线，可以是有向或无向 |常见类型按方向分类有向图 (Directed Graph)：边有方向，只能沿箭头方向到达无向图 (Undirected Graph)：边无方向，可双向到达按权重分类加权图 (Weighted Graph)：边带权重，可表示距离、成本等无权图 (Unweighted Graph)：边无权重按密度分类稠密图 (Dense Graph)：$E$ 接近 $V^2$，几乎每两个节点间都有边稀疏图 (Sparse Graph)：$E$ 远小于 $V^2$，边很少存储方式1. 邻接表 (Adjacency List)每个节点存储一个列表，记录与其相连的所有节点适合稀疏图，空间复杂度 $O(V+E)$2. 邻接矩阵

并查集

type: concept tags:数据结构算法图算法并查集 created: 2026-05-04 updated: 2026-05-04并查集（Union Find）定义并查集（Union Find）是二叉树结构的衍生，用于高效解决无向图的连通性问题。它可以在 O(1) 时间内完成合并、查询和统计操作，且只需一个数组实现，无需构建完整的图结构（邻接表/邻接矩阵）。核心操作（API）class UF { // 初始化并查集，包含 n 个节点，时间复杂度 O(n) public UF(int n); // 连接节点 p 和节点 q，时间复杂度 O(1) public void union(int p,

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

log

Harness Engineering - 操作日志本页面记录所有 Claude 的操作记录，仅追加，不修改历史记录[2026-05-02] init | 初始化仓库结构创建 raw/ 目录结构（articles, papers, images）创建 wiki/ 目录结构（entities, concepts, summaries, comparison）创建 wiki/index.md 索引页创建 wiki/log.md 操作日志仓库初始化完成[2026-05-02] ingest | 时间空间复杂度入门保存原始内容到 raw/articles/复杂度分析基础.md创建摘要页 wiki/summaries/2026-05-02 时间空间复杂度入门.md侧重：复杂度分析的实用方法（Big O 简化估算技巧）更新 wiki/index.md：摘要页数量 0→1注意：labuladong 实体和复杂度概念首次出现，暂不创建独立页（需 ≥2 篇来源）[2026-05-02] ingest | 数组基础（labuladong）提取网页内容（defuddle）并创建摘要页 wiki/summaries/2026-05-02 数组基础.md创建实体页

前缀树(Trie)基础

type: summary tags: [前缀树, Trie, 字典树, 字符串, 数据结构, labuladong] created: 2026-05-04 updated: 2026-05-04[[raw/articles/2026/05/前缀树(Trie)基础]]前缀树（Trie）基础⚠️ 内容不完整：原始文件仅包含核心原理与前缀操作部分，后续内容（如通配符匹配等）缺失。核心原理（多叉树本质、空间优势、前缀操作复杂度）Trie 树（又称字典树、前缀树）是 多叉树结构的延伸，专门针对字符串做优化：每个节点代表一个字符串字符，从根节点到某一节点的路径表示一个完整字符串空间优势：不重复存储公共前缀，例如存储 "apple"、"app"、"appl" 仅需 5 个字符（HashMap 需存储 12 个字符，重复存储3次 "app"、2次 "l"）前缀操作复杂度：所有前缀相关操作（如 shortestPrefixOf、longestPrefixOf、hasKeyWithPrefix）的时间复杂度为 O(L)，L 为前缀长度，远优于 HashMap/TreeMap 的 O(N*L)（需遍历所有键逐一比对）与多叉树的关系：Trie 是特殊的多叉树，子节点对应下一个可能的字符，子节点数量取决于字符集大小（如小写字母为26个）与现有数据结构对比（核心原理+定位对比）本站已实现的数据结构定位对比：| 数据结构 | 底层实现 | 键类型 | 核心操作复杂度 | 特点 | |---------|---------|--------|--------------|------| | HashMap/HashSet

图遍历基础

type: summary tags: [图遍历, DFS, BFS, visited数组, onPath数组, 图论] created: 2026-05-04 updated: 2026-05-04图遍历基础[[raw/articles/2026/05/图遍历基础]]一句话总结图的遍历就是 多叉树遍历 的延伸，主要遍历方式还是深度优先搜索（[[DFS]]）和广度优先搜索（[[BFS]]）。唯一的区别是，树结构中不存在环，而图结构中可能存在环，所以我们需要标记遍历过的节点，避免遍历函数在环中死循环。核心内容三种遍历场景由于图结构的复杂性，可以细分为遍历图的三种场景，每种场景的代码实现略有不同：| 场景 | 标记数组 | 标记位置 | 说明 | |------|---------|---------|------| | 遍历节点 | visited 一维数组 | 前序位置 | 确保每个节点只被遍历一次 | | 遍历边 | visited 二维数组 | for循环内部 | 确保每条边只被遍历一次 | | 遍历路径 |

并查集基础

type: summary tags: [并查集, 数据结构, 图算法, 算法基础] created: 2026-05-04 updated: 2026-05-04并查集基础[[raw/articles/2026/05/并查集基础]]一句话总结并查集（Union Find）是二叉树结构的衍生，用于高效解决无向图的动态连通性问题，所有操作时间复杂度 O(1)。核心要点1. 并查集的核心价值并查集提供以下 API：union(p, q)：连接节点 p 和 q，O(1)connected(p, q)：查询 p 和 q 是否连通，O(1)count()：查询当前连通分量数量，O(1)为什么需要并查集：使用邻接表/邻接矩阵 + DFS/BFS 判断连通性需要 O(V+E)并查集只需一个数组，所有操作 O(1)特别适合处理动态连通性问题（边逐步增加）2. 动态连通性问题图结构中的连通操作与查询：连接操作：将节点 p 和 q 连通连通查询：判断两个节点是否连通（考虑传递性）统计连通分量：查询当前图中有多少连通分量连通关系的性质：自反性：节点 p 和 p 自身是连通的对称性：如果 p 和 q 连通，则 q