加权图

图

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最短路径算法定义最短路径算法用于寻找图中两个节点之间的权重和最小的路径，根据图的类型（有无负权重、单源/多源）选择不同算法。常见算法| 算法 | 适用场景 | 时间复杂度 | 支持负权重 | |------|---------|------------|------------| | Dijkstra | 单源、非负权重 | O((V+E)logV) | ❌ | | Bellman-Ford | 单源、可含负权重 | O(VE) | ✅ | | A* | 单源、有启发函数 | 取决于启发函数 | ❌ | |

边

type: concept tags: [图论, 图, 边] created: 2026-05-04 updated: 2026-05-04边定义边是连接两个节点的结构，表示节点之间的关系。通常用 E 表示边集合（Edge 的复数）。核心特性无向图的边：无序对 {u, v}，无方向有向图的边：有序对 (u, v)，从 u 指向 v加权图的边：附带权重（距离、成本等）相关概念[[图]]：边是图的基本组成[[节点]]：边连接的两个节点[[有向图]]：有向边[[无向图]]：无向边[[加权图]]：加权边

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创建实体页

图论术语

type: summary tags: [图论, 数据结构, 算法基础, 术语] created: 2026-05-04 updated: 2026-05-04图论术语[[raw/articles/2026/05/图论术语]]一句话简介图论基础术语详解：图的结构组成、度的概念、边节点数量关系、子图类型及连通性等核心概念。关键要点1. 图的基本结构节点 (Vertex)：图的基本组成单元，每个节点有唯一 ID边 (Edge)：连接节点的线，可以是有向或无向有向图 (Directed Graph)：边有方向，只能沿箭头方向到达无向图 (Undirected Graph)：边无方向，可双向到达（可理解为双向图）加权图 (Weighted Graph)：边带权重，可用于表示距离、成本等无权图 (Unweighted Graph)：边无权重2. 度的概念度 (Degree)：无向图中与节点相连的边的条数入度 (Indegree)：有向图中指向该节点的边数出度 (Outdegree)：有向图中从该节点指向其他节点的边数3. 边和节点的数量关系简单图 (Simple Graph)：无自环边和多重边的图边数的取值范围：$0 \leq E \leq V(V-1)/2 \approx V^2$稠密图 (Dense Graph)：$E$ 接近 $V^2$，几乎每两个节点间都有边稀疏图 (Sparse Graph)：$E$ 远小于