无向图

有向图vs无向图

type: comparison tags: [有向图, 无向图, 图论, 对比] created: 2026-05-04 updated: 2026-05-04有向图 vs 无向图核心区别| 维度 | 有向图 | 无向图 | |------|--------|---------| | 边方向 | 有方向（有序对 (u,v)） | 无方向（无序对 {u,v}） | | 度区分 | 区分入度/出度 | 不区分（度=入度+出度） | | 连通概念 | 强连通图/弱连通图 | 连通图 | | 最短路径 | 需考虑方向（Dijkstra适用） |

图

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,

度

type: concept tags: [图论, 图, 度] created: 2026-05-04 updated: 2026-05-04度定义节点的度（Degree）是指与该节点相连的边的数量。对于有向图，度 = 入度 + 出度（两者等价）。核心特性无向图中：度 = 连接的边数有向图中：入度：指向该节点的边数 → [[入度]]出度：从该节点指出的边数 → [[出度]]度 = 入度 + 出度欧拉路径判断：仅当 0 或 2 个节点度为奇数时存在欧拉路径相关概念[[节点]]：度的主体[[入度]]：有向图入度[[出度]]：有向图出度[[有向图]]：区分入度/出度[[无向图]]：度 = 入度+出度

有向图

type: concept tags: [图论, 图, 有向图] created: 2026-05-04 updated: 2026-05-04有向图定义有向图是由节点（顶点）和有向边组成的图结构，每条边有方向（从起点指向终点），通常用有序对 (u, v) 表示，意为从节点 u 到节点 v 的边。核心特性边有方向：边 (u, v) 与 (v, u) 是不同的两条边节点区分入度（指向该节点的边数）和出度（从该节点指出的边数）常见类型：强连通图、有向无环图（DAG）相关概念[[图]]：有向图是图的一种[[无向图]]：对比类型（边无方向）[[入度]]：有向图节点的入度[[出度]]：有向图节点的出度[[强连通图]]：有向图的特殊类型

边

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

连通图

type: concept tags: [图论, 图, 连通图] created: 2026-05-04 updated: 2026-05-04连通图定义连通图是指任意两个节点之间都存在路径的图（仅适用于无向图）。有向图中对应的概念是强连通图。核心特性无向连通图：任意两节点间有路径连通分量：极大的连通子图 → [[连通分量]]非连通图：包含多个连通分量相关概念[[图]]：连通图是图的一种[[无向图]]：连通图通常用于无向图[[连通分量]]：连通图的极大子图[[强连通图]]：有向图的对应概念

index

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

图论术语-总结

type: summary tags: [图论, 数据结构, 算法基础, 术语] source: "[[raw/articles/2026/05/图论术语-原文]]" created: 2026-05-04 updated: 2026-05-04图论术语一句话简介图论基础术语详解：图的结构组成、度的概念、边节点数量关系、子图类型及连通性等核心概念。关键要点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$

并查集基础-总结

type: summary tags:并查集数据结构图算法算法基础 source: "[[raw/articles/2026/05/并查集基础-原文]]" created: 2026-05-04 updated: 2026-05-04并查集基础一句话总结并查集（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 和 p 也连通传递性：如果