先还原一次线上的内存告警。产品要做一个「你可能认识的人」的功能,后端把 10 万个用户的关注关系全部装进内存。第一版用二维数组:matrix[u][v] = 1 表示 u 关注了 v。测试环境只有两千个用户,跑得很顺;换到真实导出,进程内存涨到 10GB,几分钟后被系统杀掉。

复盘时问题很清楚:不在数据量,而在容器。10 万个用户就有 10 万行、10 万列,一共 100 亿个格子;可每人平均只关注 5 个人,全站只有 50 万条边,有值的格子不到万分之五。为了「查得快」买了一张覆盖所有可能性的表,绝大多数格子永远空着。

这篇讲清三种常用存法:邻接矩阵、邻接表、边表,再补一个只读大图常用的 CSR。重点不是背名字,而是算清三笔账:占多少空间、查一条边多久、列一个点的邻居多久。最后用 10 万用户、50 万条边的规模把账算完。

现场:10 万用户把进程撑爆

第一版核心代码只有几行。用户 id 从 0 编到 99999,直接拿 id 当下标:第 u 行第 v 列是 1,就代表 u 关注了 v。

const n = 100000;
const matrix = new Int8Array(n * n);   // 100 亿个格子
function follow(u, v) {
  matrix[u * n + v] = 1;
}

这段代码第一次运行有点迷惑性:new Uint8Array(100000 * 100000) 没抛错,返回了一个对象。原因是操作系统按需分配,没写入的页可以先不落地;只要把 50 万条边写进去再扫一遍,10GB 物理内存立刻压上来。分配成功不等于用得起来。

本机另做了个更接近第一版的实验:建 10 万个长度为 10 万的行数组,光创建空行就花了约 7144 毫秒,地址空间正好 10GB,一条边都没写。对只有 50 万条真实关系的图,这个开销毫无意义。

按字节算,100 亿个格子约 10GB;压成位矩阵也还有 12.5 亿字节,约 1.25GB,而且读写都要做位运算。问题出在同一个地方:容器大小由顶点数决定,不由边数决定。

矩阵方案的容量是怎么被撑大的
10 万个用户,每个用户一行
每行开 10 万列
一共 100 亿个格子
按字节约 10GB
进程被系统杀掉

如果换成按边存储,同样这份数据只要十 MB 上下,本机实测邻接表约 9.2MB;就算把每个顶点的小数组头都算进去,也在几十 MB 以内。差了约三个数量级,不是代码糙,而是容器和稀疏程度不匹配。下面先把术语对齐。

先把四个词说清楚:顶点、边、方向、权重

图(graph)是由顶点和边组成的一种结构,用来描述「对象之间有没有关系、关系有多重」。社交网络、地图路线、任务依赖、网页链接,都可以抽象成图。

顶点(vertex)是图里的对象,一个用户、一个城市、一个任务就是一个顶点。边(edge)是两个顶点之间的连接,关注、道路、依赖都是边。边可以只从一个顶点指向另一个,也可以双向。

有向图(directed graph)的边带方向:u 关注 v,不代表 v 关注 u,社交关注就是有向图。无向图(undirected graph)的边不带方向:微信好友通过之后双方都是好友,一条边等于双向可达。无向图的一条边在邻接表里要存两份。

带权图(weighted graph)的每条边多一个数字,表示距离、费用或耗时。无权图的边可以看成权重都是 1;把无权图的最短路算法直接搬到带权图上,结果通常是错的。

顶点图的节点。存的时候通常要给它一个从 0 开始的连续编号,才能用数组下标。
边顶点之间的连接。边数记作 E,顶点数记作 V,稀疏图的 E 远小于 V 的平方。
方向有向边只算一个方向,无向边要按两个方向存,空间和遍历都会翻倍。
权重边上附带的数字。存结构时不能把它丢掉,否则算出来的最短路只是边数,不是真实代价。

在挑存法之前,先回答三个问题:顶点大概有多少个、边大概有多少条、主要操作是「查两点之间有没有边」「列出一个点的所有邻居」还是「把所有边扫一遍」。答案不同,最优结构就不同,没有一种表示能三件事都做到最好。

邻接矩阵:用顶点数的平方换常数时间查边

邻接矩阵(adjacency matrix)是最直白的一种:开一个 V 行 V 列的二维表,第 u 行第 v 列的值表示 u 到 v 这条边存不存在。无权图用 0 和 1;带权图存权重,用一个特殊值表示「没有边」。

const V = 6;
const m = Array.from({ length: V + 1 }, () => new Int8Array(V + 1));
m[1][2] = m[1][3] = m[2][4] = 1;
m[3][4] = m[3][5] = m[4][6] = m[5][6] = 1;
console.log(m[1][2], m[2][1], m[3][4]);

本机输出是 1 0 1。第一项是 1,因为 1 关注了 2;第二项是 0,因为 2 没有回关 1,这就是有向图的样子。无向图要把对称的两个格子一起写:m[u][v] = m[v][u] = 1,漏写一边,另一个方向就查不到。

邻接矩阵的成本非常固定。空间是顶点数的平方,也就是 O(V²),和实际有多少条边没有关系。查一条边是 O(1),一次下标就出结果。但列出一个顶点的所有邻居,必须把整整一行扫一遍,是 O(V);哪怕这个点只连了 3 条边,也要看 10 万列。遍历全图的所有边同样要扫完整个矩阵,O(V²)。

带权图用矩阵时还要选好「没有边」的标记。常见做法是存 Infinity;存 0 会和权重为 0 的真实边混淆,在 0-1 权重的场景里会直接算错。

邻接矩阵的账

空间 O(V²),查边 O(1),列邻居 O(V),遍历所有边 O(V²)。实现简单、常数小;稀疏图上浪费极其严重,10 万顶点就要 10GB。

邻接表的账

空间 O(V+E),查边 O(度),列邻居 O(度),遍历所有边 O(V+E)。空间和边数成正比,是绝大多数图算法的默认选择。

矩阵真正合适的场景不多但很明确:顶点数很小、边很密、需要频繁判断两点是否相邻,或者算法本身就要反复扫全矩阵。最典型的是 Floyd 求所有点对最短路,它的三重循环天然按矩阵写;还有传递闭包。顶点上万且边稀疏时,矩阵基本可以直接排除。

邻接表:空间跟着边数走

邻接表(adjacency list)换了个思路:不再为「所有可能的边」留位置,而是只给每个顶点挂一张小列表,列表里放它真正的邻居。顶点多没关系,只要边不多,总空间就跟着边数走。

const adj = new Map();
function addEdge(u, v) {
  if (!adj.has(u)) adj.set(u, []);
  if (!adj.has(v)) adj.set(v, []);
  adj.get(u).push(v);
  adj.get(v).push(u);      // 无向图:一条边存两份
}
for (const [u, v] of [[1, 2], [1, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6]]) {
  addEdge(u, v);
}
console.log(adj.get(1), adj.get(3));

本机输出是 [ 2, 3 ] [ 1, 4, 5 ]。1 号的邻居是 2 和 3,3 号的邻居是 1、4、5。无向边在两边各存了一份,这不是重复,而是必要代价;只存一边,反方向就遍历不到。

邻接表的空间是 O(V+E):V 个顶点各有一张列表,每条边进一次,无向图进两次。查一条边要沿 u 的列表找 v,成本是 u 的度数 O(deg(u));列一个点的邻居也是 O(deg(u));把全图的边过一遍是 O(V+E)。平均只关注 5 个人时,查边平均比较 5 次,和矩阵的一次下标差别不大,空间却从 10GB 降到几 MB。

本机实测:10 万顶点、平均 5 条边、共 50 万个列表元素,用普通数组存,堆内存增加约 9.2MB。这比理论值大,因为每个小数组都有对象头,扩容也留余量;算进去也只是十 MB 到几十 MB 的量级。同样这份数据,矩阵是 10GB。

邻接表也有坑。查边不是 O(1),度数大的顶点列表很长,一条一条比会明显变慢。无向图一条边存两份,边数统计要记得除以二。列表里只存邻居编号,带权图就丢了权重;可以存 { to, w } 对象,也可以用两个平行数组。

尽管有缺点,邻接表仍是图算法最通用的表示。BFS、DFS、Dijkstra、拓扑排序的主要操作都是「从一个点出发,看它能到哪些点」,这恰好是邻接表最擅长的。

边表与 CSR:只遍历所有边,或者只读的大图

边表(edge list)更简单:不按顶点组织,直接把每条边当成一条记录,按顺序排在一起。要遍历全图的边,就从头读到尾;要按顶点找邻居,就得把整张表扫一遍。

// 每条边存成 [起点, 终点, 权重]
const edges = [[1, 2, 3], [1, 3, 1], [2, 4, 2], [3, 4, 5]];
edges.sort((a, b) => a[2] - b[2]);   // Kruskal 的第一步:按权重排序

边表的价值只在「边是主角」的算法里。Kruskal 求最小生成树就是典型:先按权重排序,再一条一条判断加不加,根本不需要按顶点取邻居;用邻接表反而要把边再展平一次。边表的代价是查询能力很弱,想知道 3 号点连了谁,必须扫全部记录,O(E)。

CSR(压缩稀疏行,compressed sparse row)是邻接表的一种紧凑写法,专门给只读的大图用。它把邻接表的两层结构压成两个连续数组:offsets 记录每个顶点的邻居在 targets 里的起始位置,targets 按顺序放所有邻居编号。第 u 个点的邻居就是 targets 从 offsets[u] 到 offsets[u+1] 的这一段。

const g = { 1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: [] };
const ids = [1, 2, 3, 4, 5, 6];
const idx = new Map(ids.map((v, i) => [v, i]));
const offsets = new Int32Array(ids.length + 1);
for (let i = 0; i < ids.length; i++) {
  offsets[i + 1] = offsets[i] + g[ids[i]].length;
}
const targets = new Int32Array(offsets[ids.length]);
for (let i = 0; i < ids.length; i++) {
  let p = offsets[i];
  for (const v of g[ids[i]]) targets[p++] = idx.get(v);
}
console.log([...offsets]);
console.log([...targets]);
console.log([...targets.slice(offsets[2], offsets[3])].map(i => ids[i]));

本机输出:offsets 是 [0,2,3,5,6,7,7],targets 是 [1,2,3,3,4,5,5],3 号点的邻居是 [4,5]。注意 targets 存的是从 0 开始的编号,3 号点对应的两个值是 3 和 4,映射回顶点编号才是 4 和 5。写 CSR 最容易错的就是这个映射,先把映射函数单独测一遍。

CSR 内存连续、没有每个顶点一个小数组的对象头,缓存命中率高。换算到 10 万顶点、50 万条边:targets 是 50 万乘 4 字节,约 1.9MB;offsets 是 10 万零 1 个乘 4 字节,约 0.38MB,合计约 2.3MB,比邻接表的 9.2MB 又小一截。很多图计算框架加载大图时,第一步就是把边表转成 CSR。

代价是 CSR 基本只读。加一条边或删一条边,targets 要整体挪动,offsets 后面的值都要改,成本很高。它适合「一次构建、反复查询」的静态图,比如网页链接图、路网;不适合频繁增删的社交关注关系。动态图要么用邻接表,要么定期重建 CSR。

10 万顶点、50 万条边,把账算完

现在把同一份数据放进五种容器,横向比一下。顶点数 V 是 10 万,边数 E 是 50 万,平均每个顶点 5 条边,按十进制 GB 计算。

表示方式空间查一条边列一个点的邻居适合的场景
邻接矩阵,每格 1 字节100 亿字节,约 10GBO(1)O(V),扫 10 万列顶点很少的稠密图
邻接矩阵,每格 1 位12.5 亿字节,约 1.25GBO(1),要位运算O(V)稠密图且内存吃紧
邻接表,普通数组本机实测约 9.2MBO(deg),平均 5 次比较O(deg)通用,增删方便
边表,两个 32 位整数一条边约 3.8MB要扫全表,O(E)要扫全表,O(E)Kruskal 这类边优先算法
CSR约 2.3MBO(deg),可对有序邻居二分O(deg),内存连续只读的静态大图

最扎眼的是第一行和第三行。同样是 50 万条边,矩阵要 10GB,邻接表只要 9.2MB,差约一千倍。第二行看似把矩阵救回来了,但 1.25GB 是「按位压缩」的理论值,还要加位运算的时间和复杂度;为稀疏图付出 1.25GB 依然不划算。

还有一笔时间账。矩阵上跑 BFS,每个顶点都要扫一整行找邻居,总工作量是 V 乘 V,100 亿次格子检查;邻接表上每个顶点扫自己的列表,总工作量是 V 加 E,约 60 万次。差了四个数量级,不是常数优化能弥补的。

反过来,如果图真的很密,比如 1000 个顶点、接近 50 万条边,矩阵的 100 万个格子只要 1MB,查边一次到位,比邻接表比较几十个邻居更划算。所以「矩阵不好」有前提:稀疏图上不好。判断稀疏看 E 和 V 的平方差多远,不看绝对边数。

本文的 GB 按十进制算,1GB 等于 10 的 9 次方字节;按 1024 进位,10GB 约 9.3GiB,1.25GB 约 1.16GiB。对着监控看内存时先确认单位,否则会误以为差了百分之七。

现象、原因与第一步排查

图的存储出问题,症状往往不像「图」的问题,而像内存、超时或数据缺失。按「第一步查什么」定位,比直接重写建图代码快得多。

现象真实原因第一步查什么
服务启动后内存暴涨,随后被杀用 V 行 V 列的矩阵存稀疏边,空间按顶点数平方增长先算 V 的平方乘每格字节数,再看实际边数
查「A 是否关注 B」很快,推荐却极慢矩阵查边是 O(1),但列邻居要扫一整行 O(V)算法是否在反复「列出一个点的所有邻居」
邻接表内存仍然超预期每个顶点一个小数组有对象头,无向图还存了两份边统计实际的列表元素总数和单点度数分布
无向图只能从一个方向走到另一个方向建边时只加了 u 到 v,忘了加 v 到 uaddEdge 是否对两个方向都写入
带权图的最短路结果全是 1邻接表只存了邻居编号,权重在建图时被丢掉列表元素里有没有权重字段
用边表跑 BFS 或 DFS 非常慢边表不能按顶点取邻居,每次都要扫全表算法的主要操作是不是按点扩展
CSR 查邻居时结果错位或多出一个人offsets 长度写成了 V,或者没用前缀和检查 offsets 是否为 V+1 项且单调不减
最短路把重复边当成多条路,统计翻倍同一对顶点之间有重边,建图时没有去重输出每个顶点的度数,看是否有异常大的值

最容易误判的是第一行和第三行。第一行看起来像「数据太多」,实际是「容器容量和数据量脱钩」;第三行看起来像「邻接表也费内存」,实际是每个顶点一个数组的对象开销,加上无向边存两份。排查时先把顶点数、边数、平均度数打印出来,三个数字一对,问题基本就定位了。

边界与代价:没有最好的表示,只有匹配的表示

邻接矩阵的边界来自平方。顶点数翻一倍,空间翻四倍;10 万顶点 10GB,100 万顶点就是 1TB。适合的规模通常停在几千个顶点。位矩阵能压到八分之一,但读写要位运算,增删边也不方便,仍然摆脱不了平方增长。

邻接表的边界来自「查边」和「对象开销」。查边要沿列表比较,度数大的点会成为热点;顶点特别多、边特别少时,列表头的开销可能比边本身还大。无向图存两份,估算内存要记得这个系数。它适合动态增删,不适合对缓存极度敏感的批量计算。

边表和 CSR 的边界来自「只读」和「查询能力」。边表只能高效遍历所有边,按顶点展开都会退化成扫全表。CSR 查询快、内存省,但构建要两遍扫描,改一条边可能就要重建。它们适合离线、静态、规模大的场景,比如最小生成树、网页排名、路网预处理。

判断顺序是:先数清 V 和 E,算出稀疏程度;再列出主要操作,是查边、列邻居还是扫全部边;最后看要不要频繁增删。三个问题答完,表示法基本就定了。答不出来就先用邻接表,它足够通用,等性能数据出来再换。

还有两个细节要提前定好。第一,顶点编号尽量从 0 开始连续,矩阵和 CSR 才能直接用下标;业务 id 是字符串或稀疏数字时,先映射成连续编号,映射本身也算内存。第二,自环和重边怎么处理要明确:自环会多算一度,重边会让最短路和计数出现重复,建图时统一过滤更可靠。

当天能做的练习

  1. 用邻接矩阵和邻接表各建一份同样的 6 顶点图,分别打印两种结构,再手工数一数「查 1 到 6 有没有边」和「列出 1 的所有邻居」各做了多少次比较。
  2. 生成 1 万个顶点、平均 5 条出边的随机图,用矩阵和邻接表各建一次,记录耗时与 process.memoryUsage() 的堆内存差值。
  3. 把第 2 题的有向图改成无向图,重新建一次,确认列表元素总数正好翻倍,并解释为什么不能只存一个方向。
  4. 写一份边表并按权重排序,模拟 Kruskal 的第一步;再用同一份边表从 1 号点做 BFS,记录为了找邻居扫了多少条记录,说明边表为什么不适合按点扩展。
  5. 给 6 顶点图建 CSR,打印 offsets 与 targets,写一个 neighbors(u) 函数和邻接表比对;再故意把 offsets 长度写成 V,观察查最后一个点时错在哪。
环境说明:本文所有输出与内存数字都用 Node.js 24 在本机实际运行,邻接表 9.2MB 是 10 万顶点、50 万条列表元素时的堆内存增量,不同引擎和对象布局会有差异。文中的 GB 按十进制计算,仅用于比较量级,不作为容量规划的精确承诺。

小结与下一篇

三句话收一下:图的表示先看稀疏程度,边少就用邻接表,边多到接近平方才考虑矩阵;矩阵把查边压到 O(1),代价是空间按顶点数平方增长;边表和 CSR 各有明确的主场,前者给边优先的算法,后者给只读的大图。

下一篇进入 BFS。存好图只是第一步,真正要回答的是「两个人隔了几层」「到每个点最少走几条边」,这需要按层扩展,而不是一条路走到黑。下一篇就用邻接表把 BFS 的分层、入队标记、0-1 BFS 和网格最短路跑一遍。