Skip to main content

1 / 4概念

Graph Structures

图结构的核心不是“把边存下来”,而是决定哪种查询便宜:查一条边、遍历邻居、扫全部边、合并连通块,四种需求对应四种表示。判断标准是 V/E 比例、更新频率和缓存局部性,不是“邻接表更常用”。

1 概念​

1.1 一句话定义​

图是顶点集合 V 与边集合 E 的结构;存储表示决定空间和操作代价。邻接矩阵用 V×V 表存边,邻接表为每个点挂邻居列表,边列表只存边,CSR 用偏移数组压缩邻接表;并查集(DSU)维护不相交集合,支持近似 O(1) 的合并与查询。

1.2 它解决什么问题​

  • 稀疏图存储:E 远小于 V² 时,矩阵会浪费大量空间,邻接表/CSR 只存实际边。
  • 快速邻居遍历:BFS/DFS/最短路都要反复遍历邻居,表示必须让这一步便宜。
  • 全边扫描:Kruskal、Bellman-Ford 需要按边遍历/排序,边列表更直接。
  • 动态连通性:并查集把“合并两个集合、判断是否同集合”做到近似常数。
  • 依赖排序:拓扑排序把 DAG 变成线性执行顺序,发现循环依赖。

1.3 不属于本页的内容​

主题去哪
BFS/DFS、Dijkstra、MST、A*Graph Algorithms
数组、链表、哈希表Linear Structures
树、堆、B+ 树Trees & Heaps
复杂度分析与摊还Complexity Analysis
强连通分量、2-SAT 等进阶图论进阶图论页面(待补)

1.4 关键术语​

术语含义容易混淆的点
稀疏 / 稠密E 接近 V / E 接近 V²稠密不绝对等于矩阵
度 / 入度 / 出度相邻边数 / 指向该点 / 从该点出发无向图只有度
邻接矩阵V×V 的边权表无向图对称,有向图不一定
邻接表每个点一个邻居容器无向边通常存两份
边列表只存 (u, v, w)不适合查邻居
CSR偏移数组 + 邻居数组行压缩,不是列压缩
DSU并查集,维护不相交集合不是图的完整表示
路径压缩查找时把节点直接挂到根不改变集合划分
按秩/按大小合并矮树挂到高树下与路径压缩配合近似 O(α)
拓扑序所有边从前往后的线性序只对 DAG 存在