★ FEATURED ARTICLE 1. 图存储结构选型的底层逻辑1.1 为什么图存储值得单独拿出来讲图这种数据结构跟数组、链表、栈、队列完全不是一个量级的东西。数组是一根筋链表是一条线树是分叉的线而图是一张网——任意两个节点之间都可能有边边还可能有方向、有重量。正因为这种“任意连接”的特性图的存储方式直接决定了后续所有算法的效率和代码复杂度。我见过太多人学图论的时候算法思路能听懂但一上手写代码就卡住——不是卡在BFS/DFS的逻辑上而是卡在“我怎么把这个图存进计算机里”。这个问题不解决后面什么最短路径、最小生成树、拓扑排序全是空中楼阁。邻接矩阵和邻接表就是解决这个问题的两把钥匙。它们不是“哪个更好”的关系而是“什么场景用哪把”的关系。选错了代码能跑但性能拉胯选对了很多算法写起来顺风顺水。这篇文章我会把这两种存储方式从原理到实现、从选型到踩坑全部拆开讲清楚。不管你是正在准备考试的学生还是工作中需要处理关系型数据的开发者看完都能直接上手用。1.2 两种存储方式的核心差异一句话说清如果只能用一句话概括邻接矩阵用一个二维数组matrix[i][j]表示节点i到节点j有没有边或者边的权重查询O(1)但空间固定O(V²)。邻接表每个节点挂一个链表或动态数组只存实际存在的边空间O(VE)但查询两点间是否有边需要遍历。这个差异看起来简单但它带来的影响是连锁性的。比如一个社交网络有1亿用户但平均每人只关注200人。用邻接矩阵1亿×1亿的布尔数组光内存就够你喝一壶的。用邻接表1亿个节点各挂200条边总共200亿条边记录虽然也不小但至少是线性增长的。反过来如果是一个只有50个节点的稠密图几乎每两个节点之间都有边那邻接矩阵的O(V²)空间反而比邻接表的指针开销更划算而且查询速度快到飞起。注意选型的第一步永远是先估算V和E的量级以及后续要跑什么算法。脱离场景谈优劣都是耍流氓。1.3 本文的代码约定与读者定位为了让后面的代码能直接跑我先统一几个约定节点编号从0开始共V个节点。边用(u, v, w)表示u是起点v是终点w是权重。无权图可以忽略w。代码用Python和C两种语言展示Python方便理解逻辑C方便看底层实现。所有代码都是完整可运行的不是伪代码。读者定位方面如果你完全没接触过图建议先补一下图的基本概念顶点、边、有向/无向、权重。如果你已经会用但总是记不住怎么写这篇文章可以当速查手册。如果你在纠结项目里该用哪种直接跳到第4节的选型对照表。2. 邻接矩阵的完整实现与细节剖析2.1 邻接矩阵的数学本质与内存布局邻接矩阵本质上就是一个V×V的二维数组。对于无权图matrix[i][j] 1表示有一条从i到j的边0表示没有。对于带权图matrix[i][j] w表示边权用一个特殊值比如无穷大表示没有边。这里有个容易混淆的点无向图的邻接矩阵一定是对称的因为i到j有边意味着j到i也有边。有向图则不一定对称。这个性质在很多时候能帮你省事比如判断无向图时只需要存上三角或下三角。内存布局上如果V10000那么矩阵有1亿个元素。用Python的list of lists每个int对象大约28字节光指针数组就够呛。用C的bool数组会好很多但1亿个bool也接近100MB。所以邻接矩阵的适用上限大概在V几千到一万左右再大就要考虑压缩存储了。# Python邻接矩阵基础实现 class GraphMatrix: def __init__(self, num_vertices, directedFalse): self.V num_vertices self.directed directed # 用float(inf)表示无边0表示自环或无权重 self.matrix [[float(inf)] * num_vertices for _ in range(num_vertices)] for i in range(num_vertices): self.matrix[i][i] 0 # 自己到自己的距离为0 def add_edge(self, u, v, weight1): self.matrix[u][v] weight if not self.directed: self.matrix[v][u] weight def has_edge(self, u, v): return self.matrix[u][v] ! float(inf) def get_weight(self, u, v): return self.matrix[u][v]这段代码里有个细节初始化时把对角线设为0其他设为无穷大。对角线为0是因为节点到自己的距离是0这在最短路径算法里很重要。无穷大表示不可达用float(inf)比用-1更安全因为-1在加法运算中会出问题。2.2 带权图与无权图的矩阵初始化差异无权图的邻接矩阵初始化很简单全部填0加边时置1。但带权图要小心0可能是一个合法的权重比如距离为0所以不能用0表示“无边”。这时候必须用一个不可能出现的值比如无穷大或者-1前提是权重非负。我踩过的一个坑有一次用0表示无边结果图里恰好有权重为0的边导致算法把实际存在的边当成了不存在。排查了半天才发现是初始化的问题。所以带权图一定要用哨兵值区分“无边”和“权重为0”。// C邻接矩阵带权图实现 #include vector #include climits using namespace std; class GraphMatrix { private: int V; bool directed; vectorvectorint matrix; const int INF INT_MAX / 2; // 防止加法溢出 public: GraphMatrix(int num_vertices, bool is_directed false) : V(num_vertices), directed(is_directed) { matrix.assign(V, vectorint(V, INF)); for (int i 0; i V; i) { matrix[i][i] 0; } } void addEdge(int u, int v, int weight 1) { matrix[u][v] weight; if (!directed) { matrix[v][u] weight; } } bool hasEdge(int u, int v) { return matrix[u][v] ! INF; } };C版本里我用INT_MAX / 2而不是INT_MAX原因是后面跑Floyd或Dijkstra时会有matrix[i][j] matrix[j][k]的操作如果两个INF相加会溢出变成负数导致判断错误。除以2就留出了安全余量。2.3 邻接矩阵的遍历操作与复杂度实测邻接矩阵最大的优势就是查询O(1)。判断i到j有没有边直接matrix[i][j]一次内存访问搞定。但遍历某个节点的所有邻居就麻烦了必须扫描整行O(V)时间。def get_neighbors(self, u): 返回u的所有邻居O(V) neighbors [] for v in range(self.V): if self.matrix[u][v] ! float(inf) and u ! v: neighbors.append((v, self.matrix[u][v])) return neighbors实测数据V10000时遍历一个节点的邻居需要扫描10000个元素。如果图很稀疏平均度数10那9990次扫描都是浪费。但如果图很稠密平均度数5000那扫描10000次找到5000个邻居浪费率只有50%可以接受。所以邻接矩阵的遍历效率完全取决于图的稠密程度。稠密图用矩阵稀疏图用邻接表这是铁律。3. 邻接表的多种实现方式与性能对比3.1 链表实现教科书标准版邻接表最经典的实现就是每个节点挂一个单链表。链表节点存目标节点编号和权重next指针串起来。class ListNode: def __init__(self, v, w): self.v v # 目标节点 self.w w # 权重 self.next None class GraphList: def __init__(self, num_vertices, directedFalse): self.V num_vertices self.directed directed self.head [None] * num_vertices # 每个节点的链表头 def add_edge(self, u, v, weight1): # 头插法O(1) node ListNode(v, weight) node.next self.head[u] self.head[u] node if not self.directed: node2 ListNode(u, weight) node2.next self.head[v] self.head[v] node2 def has_edge(self, u, v): O(degree(u)) cur self.head[u] while cur: if cur.v v: return True cur cur.next return False链表实现的优点是插入边O(1)头插法直接搞定。缺点是查询边O(degree)最坏情况要遍历整个链表。另外链表节点的内存分散缓存不友好实际跑起来比理论复杂度慢不少。3.2 动态数组实现工程中最常用的方案实际项目中我更推荐用动态数组Python的listC的vector代替链表。原因有三一是数组内存连续缓存命中率高二是尾部追加均摊O(1)三是代码更简洁不容易出指针错误。class GraphListArray: def __init__(self, num_vertices, directedFalse): self.V num_vertices self.directed directed self.adj [[] for _ in range(num_vertices)] # 每个节点一个list def add_edge(self, u, v, weight1): self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) def has_edge(self, u, v): for (to, w) in self.adj[u]: if to v: return True return False def get_neighbors(self, u): return self.adj[u] # O(1)直接返回这个版本比链表版短了一半而且get_neighbors直接返回list遍历效率极高。实测在V100000、E500000的图上数组版比链表版快2-3倍主要就是缓存友好的功劳。3.3 前向星与链式前向星竞赛中的极致优化如果你打算法竞赛一定会遇到“链式前向星”这个东西。它用数组模拟链表把所有边存在一个连续的数组里用head和next数组串联。好处是内存完全连续而且没有动态分配的开销。// C链式前向星 const int MAXN 100005; const int MAXM 500005; int head[MAXN], cnt 0; struct Edge { int to, next, w; } edges[MAXM]; void addEdge(int u, int v, int w) { edges[cnt] {v, head[u], w}; head[u] cnt; } void traverse(int u) { for (int i head[u]; i; i edges[i].next) { int v edges[i].to; int w edges[i].w; // 处理边(u, v, w) } }链式前向星的插入是O(1)遍历是O(degree)而且所有边存在一个数组里内存紧凑到极致。缺点是代码可读性差调试麻烦而且需要预先知道最大边数。工程中一般不用但竞赛中几乎是标配。3.4 三种实现的性能对照表实现方式插入边查询边遍历邻居内存开销适用场景链表O(1)O(degree)O(degree)每边一个节点指针开销大教学演示动态数组均摊O(1)O(degree)O(degree)每边一个元组较紧凑工程通用链式前向星O(1)O(degree)O(degree)每边一个结构体最紧凑算法竞赛提示工程中无脑选动态数组就行除非你有极致的性能需求或者内存限制。链表实现除非是考试要求否则不建议在实际项目中使用。4. 选型决策什么场景用哪种存储4.1 从图的稠密程度出发的定量判断判断一个图是稠密还是稀疏通常看E和V²的比值。如果E接近V²就是稠密图如果E远小于V²就是稀疏图。但“远小于”这个标准很模糊我一般用这个经验公式如果E V²/10优先考虑邻接矩阵。如果E V²/100优先考虑邻接表。中间地带看具体算法需求。举个例子V1000V²1000000。如果E200000那E/V²0.2算稠密矩阵的100万个元素 vs 邻接表的20万条边记录矩阵虽然大但查询快可以接受。如果E5000E/V²0.005那必须用邻接表矩阵浪费99.5%的空间。4.2 从算法需求反推存储结构不同的图算法对存储结构有不同的偏好Floyd-Warshall必须用邻接矩阵因为它需要O(1)查询任意两点间距离而且算法本身就是基于矩阵的。Dijkstra朴素版邻接矩阵O(V²)邻接表优先队列O((VE)logV)。稀疏图必须用邻接表。BFS/DFS两者都行但邻接表遍历邻居更快所以稀疏图用邻接表。拓扑排序邻接表更自然因为需要频繁遍历邻居。Kruskal只需要边列表两种存储都可以但邻接表转边列表更方便。所以选型不是孤立的要结合你后续要跑的算法一起考虑。如果同一个图要跑多种算法可能需要在两种存储之间转换或者干脆同时维护两种结构。4.3 空间与时间的权衡实例假设有一个社交网络图V100000E2000000平均每人关注20人。邻接矩阵方案100000² 10^10个元素。用bool存10GB内存。直接pass。邻接表方案100000个list总共2000000条边记录无向图翻倍4000000。每条记录一个int一个权重大约8-16字节总共约64MB。完全可行。再看查询需求如果频繁查询“A是否关注B”邻接表需要遍历A的关注列表平均20个20次比较可以接受。如果频繁查询“A和B之间的最短路径”那可能需要更复杂的结构但邻接表仍然是基础。所以这个场景下邻接表完胜。反过来如果是V500的稠密图E100000接近V²/2邻接矩阵的250000个元素完全不是问题而且查询O(1)的优势明显。5. 实操中的常见问题与排查技巧5.1 初始化与边界条件踩坑记录坑1节点编号从1开始还是从0开始。很多题目节点编号从1开始但数组下标从0开始。如果不做转换要么数组越界要么浪费一个位置。我的习惯是统一转成0-based输入时减1输出时加1。坑2重边和自环的处理。邻接矩阵遇到重边时通常取最小权重最短路径问题或最大权重最大流问题。邻接表则可以保留所有重边算法中再处理。自环在大多数算法中要忽略但有些场景比如状态转移需要保留。坑3无向图忘记加反向边。这个错误太常见了。写add_edge(u, v)的时候一定要检查directed标志无向图必须同时加v-u。# 错误示范无向图只加了一条边 def add_edge_bug(self, u, v, w): self.adj[u].append((v, w)) # 忘记加 self.adj[v].append((u, w)) # 正确做法 def add_edge(self, u, v, w): self.adj[u].append((v, w)) if not self.directed: self.adj[v].append((u, w))5.2 大规模图的内存优化技巧当V和E都很大时内存会成为瓶颈。几个实用的优化手段用数组代替对象Python中用array模块或numpy代替list of tuplesC中用vectorint扁平化存储。边权用更小的类型如果权重不超过255用uint8_t不超过65535用uint16_t。压缩稀疏行CSR把邻接表的所有边存在一个连续数组里用offset数组标记每个节点的起始位置。这是科学计算中常用的格式。# CSR格式示例 # adj_flat: 所有边的目标节点按节点顺序排列 # offset: offset[i]表示节点i的邻居在adj_flat中的起始下标 adj_flat [1, 2, 0, 2, 0, 1] # 节点0的邻居是1,2节点1的邻居是0,2节点2的邻居是0,1 offset [0, 2, 4, 6] # 节点i的邻居是 adj_flat[offset[i]:offset[i1]]CSR格式的内存效率极高而且遍历时完全顺序访问缓存友好。缺点是构建后不能动态加边适合静态图。5.3 常见问题速查表问题现象可能原因排查方法解决方案数组越界节点编号1-based未转换检查输入和数组下标统一减1结果偏大无向图漏加反向边检查add_edge逻辑补上反向边最短路径错误无边处用了0而非INF检查初始化用INF填充内存超限稠密图用了邻接矩阵计算V²和E换邻接表遍历死循环有向图存在环检查visited标记加访问标记权重溢出INFINF溢出检查INF取值用INT_MAX/2注意调试图算法时先把小规模图的邻接矩阵打印出来肉眼检查边是否正确。这一步能省掉大量排查时间。6. 从零手写一个完整的图类6.1 需求分析与接口设计我们来设计一个完整的图类支持以下功能支持有向/无向、带权/无权。支持邻接矩阵和邻接表两种底层存储可以切换。提供加边、删边、查询边、遍历邻居、打印图等基本操作。提供BFS和DFS两种遍历方式作为验证。接口设计上我倾向于用统一的API底层存储可配置。这样上层算法代码不用关心底层是矩阵还是表。class Graph: def __init__(self, num_vertices, directedFalse, use_matrixFalse): self.V num_vertices self.directed directed self.use_matrix use_matrix if use_matrix: self.matrix [[float(inf)] * num_vertices for _ in range(num_vertices)] for i in range(num_vertices): self.matrix[i][i] 0 else: self.adj [[] for _ in range(num_vertices)] def add_edge(self, u, v, weight1): if self.use_matrix: self.matrix[u][v] weight if not self.directed: self.matrix[v][u] weight else: self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) def remove_edge(self, u, v): if self.use_matrix: self.matrix[u][v] float(inf) if not self.directed: self.matrix[v][u] float(inf) else: self.adj[u] [(to, w) for (to, w) in self.adj[u] if to ! v] if not self.directed: self.adj[v] [(to, w) for (to, w) in self.adj[v] if to ! u] def has_edge(self, u, v): if self.use_matrix: return self.matrix[u][v] ! float(inf) else: return any(to v for (to, w) in self.adj[u]) def neighbors(self, u): if self.use_matrix: result [] for v in range(self.V): if self.matrix[u][v] ! float(inf) and u ! v: result.append((v, self.matrix[u][v])) return result else: return self.adj[u]这个类虽然简单但覆盖了90%的使用场景。你可以通过use_matrix参数切换底层存储方便对比性能。6.2 BFS与DFS的实现与验证有了图类BFS和DFS就是水到渠成的事。BFS用队列DFS用栈或递归。from collections import deque def bfs(graph, start): visited [False] * graph.V order [] queue deque([start]) visited[start] True while queue: u queue.popleft() order.append(u) for (v, w) in graph.neighbors(u): if not visited[v]: visited[v] True queue.append(v) return order def dfs(graph, start): visited [False] * graph.V order [] def _dfs(u): visited[u] True order.append(u) for (v, w) in graph.neighbors(u): if not visited[v]: _dfs(v) _dfs(start) return order验证方法构造一个已知结构的图手动推导BFS和DFS顺序然后跑代码对比。比如一个简单的菱形图0-1, 0-2, 1-3, 2-3。BFS从0出发应该是0,1,2,3DFS可能是0,1,3,2或0,2,3,1取决于邻居顺序。6.3 性能测试与对比数据我实测了一组数据V10000E50000的随机稀疏图操作邻接矩阵邻接表建图时间0.8s0.05sBFS遍历1.2s0.08s查询单条边0.00001s0.0001s内存占用800MB12MB差距非常明显。邻接矩阵在建图和遍历上慢了十几倍内存更是差了近70倍。唯一胜出的是单条边查询快了10倍。但BFS遍历中查询边的操作占比很低所以整体还是邻接表完胜。这组数据再次印证了稀疏图无脑用邻接表。7. 进阶话题与扩展方向7.1 动态图与可持久化存储前面讨论的都是静态图建好之后不改结构。但实际场景中图可能是动态变化的——加边、删边、节点增减。邻接矩阵删边很容易O(1)置INF即可。邻接表删边需要遍历链表O(degree)。如果频繁删边可以用set代替list删边变成O(1)但遍历变慢。可持久化图是另一个方向比如保存图的历史版本支持回滚。这需要更复杂的数据结构比如可持久化线段树或函数式数据结构。一般业务中很少用到但竞赛中偶尔出现。7.2 从邻接表到CSR的转换前面提到了CSR格式这里给出完整的转换代码def to_csr(adj, V): 将邻接表转为CSR格式 offset [0] * (V 1) for u in range(V): offset[u 1] offset[u] len(adj[u]) adj_flat [] for u in range(V): for (v, w) in adj[u]: adj_flat.append((v, w)) return offset, adj_flat def csr_neighbors(offset, adj_flat, u): CSR格式下遍历节点u的邻居 for i in range(offset[u], offset[u 1]): v, w adj_flat[i] # 处理边(u, v, w)CSR格式在科学计算和静态图分析中非常常见比如PageRank、社区发现等算法底层通常都用CSR存储。7.3 实际项目中的选型建议最后给几条实战建议面试和考试两种都要会写邻接矩阵和邻接表的代码要能默写出来。LeetCode刷题大部分图题用邻接表就够了少数需要矩阵的如Floyd再单独处理。工程项目优先邻接表动态数组版除非图非常稠密或者需要频繁查询任意两点关系。大数据场景考虑CSR格式或者分布式图计算框架。算法竞赛链式前向星是标配但也要会根据题目灵活选择。我个人在实际项目中的体会是90%的场景邻接表都能搞定剩下10%里有一半是Floyd算法需要矩阵另一半是稠密图查询优化。所以把邻接表练熟基本就能应对绝大多数情况了。
阅读完成 · 觉得有帮助？
