先还原一次线上的内存告警。产品要做一个「你可能认识的人」的功能,后端把 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,而且读写都要做位运算。问题出在同一个地方:容器大小由顶点数决定,不由边数决定。
如果换成按边存储,同样这份数据只要十 MB 上下,本机实测邻接表约 9.2MB;就算把每个顶点的小数组头都算进去,也在几十 MB 以内。差了约三个数量级,不是代码糙,而是容器和稀疏程度不匹配。下面先把术语对齐。
先把四个词说清楚:顶点、边、方向、权重
图(graph)是由顶点和边组成的一种结构,用来描述「对象之间有没有关系、关系有多重」。社交网络、地图路线、任务依赖、网页链接,都可以抽象成图。
顶点(vertex)是图里的对象,一个用户、一个城市、一个任务就是一个顶点。边(edge)是两个顶点之间的连接,关注、道路、依赖都是边。边可以只从一个顶点指向另一个,也可以双向。
有向图(directed graph)的边带方向:u 关注 v,不代表 v 关注 u,社交关注就是有向图。无向图(undirected graph)的边不带方向:微信好友通过之后双方都是好友,一条边等于双向可达。无向图的一条边在邻接表里要存两份。
带权图(weighted graph)的每条边多一个数字,表示距离、费用或耗时。无权图的边可以看成权重都是 1;把无权图的最短路算法直接搬到带权图上,结果通常是错的。
在挑存法之前,先回答三个问题:顶点大概有多少个、边大概有多少条、主要操作是「查两点之间有没有边」「列出一个点的所有邻居」还是「把所有边扫一遍」。答案不同,最优结构就不同,没有一种表示能三件事都做到最好。
邻接矩阵:用顶点数的平方换常数时间查边
邻接矩阵(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 亿字节,约 10GB | O(1) | O(V),扫 10 万列 | 顶点很少的稠密图 |
| 邻接矩阵,每格 1 位 | 12.5 亿字节,约 1.25GB | O(1),要位运算 | O(V) | 稠密图且内存吃紧 |
| 邻接表,普通数组 | 本机实测约 9.2MB | O(deg),平均 5 次比较 | O(deg) | 通用,增删方便 |
| 边表,两个 32 位整数一条边 | 约 3.8MB | 要扫全表,O(E) | 要扫全表,O(E) | Kruskal 这类边优先算法 |
| CSR | 约 2.3MB | O(deg),可对有序邻居二分 | O(deg),内存连续 | 只读的静态大图 |
最扎眼的是第一行和第三行。同样是 50 万条边,矩阵要 10GB,邻接表只要 9.2MB,差约一千倍。第二行看似把矩阵救回来了,但 1.25GB 是「按位压缩」的理论值,还要加位运算的时间和复杂度;为稀疏图付出 1.25GB 依然不划算。
还有一笔时间账。矩阵上跑 BFS,每个顶点都要扫一整行找邻居,总工作量是 V 乘 V,100 亿次格子检查;邻接表上每个顶点扫自己的列表,总工作量是 V 加 E,约 60 万次。差了四个数量级,不是常数优化能弥补的。
反过来,如果图真的很密,比如 1000 个顶点、接近 50 万条边,矩阵的 100 万个格子只要 1MB,查边一次到位,比邻接表比较几十个邻居更划算。所以「矩阵不好」有前提:稀疏图上不好。判断稀疏看 E 和 V 的平方差多远,不看绝对边数。
现象、原因与第一步排查
图的存储出问题,症状往往不像「图」的问题,而像内存、超时或数据缺失。按「第一步查什么」定位,比直接重写建图代码快得多。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 服务启动后内存暴涨,随后被杀 | 用 V 行 V 列的矩阵存稀疏边,空间按顶点数平方增长 | 先算 V 的平方乘每格字节数,再看实际边数 |
| 查「A 是否关注 B」很快,推荐却极慢 | 矩阵查边是 O(1),但列邻居要扫一整行 O(V) | 算法是否在反复「列出一个点的所有邻居」 |
| 邻接表内存仍然超预期 | 每个顶点一个小数组有对象头,无向图还存了两份边 | 统计实际的列表元素总数和单点度数分布 |
| 无向图只能从一个方向走到另一个方向 | 建边时只加了 u 到 v,忘了加 v 到 u | addEdge 是否对两个方向都写入 |
| 带权图的最短路结果全是 1 | 邻接表只存了邻居编号,权重在建图时被丢掉 | 列表元素里有没有权重字段 |
| 用边表跑 BFS 或 DFS 非常慢 | 边表不能按顶点取邻居,每次都要扫全表 | 算法的主要操作是不是按点扩展 |
| CSR 查邻居时结果错位或多出一个人 | offsets 长度写成了 V,或者没用前缀和 | 检查 offsets 是否为 V+1 项且单调不减 |
| 最短路把重复边当成多条路,统计翻倍 | 同一对顶点之间有重边,建图时没有去重 | 输出每个顶点的度数,看是否有异常大的值 |
最容易误判的是第一行和第三行。第一行看起来像「数据太多」,实际是「容器容量和数据量脱钩」;第三行看起来像「邻接表也费内存」,实际是每个顶点一个数组的对象开销,加上无向边存两份。排查时先把顶点数、边数、平均度数打印出来,三个数字一对,问题基本就定位了。
边界与代价:没有最好的表示,只有匹配的表示
邻接矩阵的边界来自平方。顶点数翻一倍,空间翻四倍;10 万顶点 10GB,100 万顶点就是 1TB。适合的规模通常停在几千个顶点。位矩阵能压到八分之一,但读写要位运算,增删边也不方便,仍然摆脱不了平方增长。
邻接表的边界来自「查边」和「对象开销」。查边要沿列表比较,度数大的点会成为热点;顶点特别多、边特别少时,列表头的开销可能比边本身还大。无向图存两份,估算内存要记得这个系数。它适合动态增删,不适合对缓存极度敏感的批量计算。
边表和 CSR 的边界来自「只读」和「查询能力」。边表只能高效遍历所有边,按顶点展开都会退化成扫全表。CSR 查询快、内存省,但构建要两遍扫描,改一条边可能就要重建。它们适合离线、静态、规模大的场景,比如最小生成树、网页排名、路网预处理。
判断顺序是:先数清 V 和 E,算出稀疏程度;再列出主要操作,是查边、列邻居还是扫全部边;最后看要不要频繁增删。三个问题答完,表示法基本就定了。答不出来就先用邻接表,它足够通用,等性能数据出来再换。
还有两个细节要提前定好。第一,顶点编号尽量从 0 开始连续,矩阵和 CSR 才能直接用下标;业务 id 是字符串或稀疏数字时,先映射成连续编号,映射本身也算内存。第二,自环和重边怎么处理要明确:自环会多算一度,重边会让最短路和计数出现重复,建图时统一过滤更可靠。
当天能做的练习
- 用邻接矩阵和邻接表各建一份同样的 6 顶点图,分别打印两种结构,再手工数一数「查 1 到 6 有没有边」和「列出 1 的所有邻居」各做了多少次比较。
- 生成 1 万个顶点、平均 5 条出边的随机图,用矩阵和邻接表各建一次,记录耗时与
process.memoryUsage()的堆内存差值。 - 把第 2 题的有向图改成无向图,重新建一次,确认列表元素总数正好翻倍,并解释为什么不能只存一个方向。
- 写一份边表并按权重排序,模拟 Kruskal 的第一步;再用同一份边表从 1 号点做 BFS,记录为了找邻居扫了多少条记录,说明边表为什么不适合按点扩展。
- 给 6 顶点图建 CSR,打印
offsets与targets,写一个neighbors(u)函数和邻接表比对;再故意把offsets长度写成 V,观察查最后一个点时错在哪。
小结与下一篇
三句话收一下:图的表示先看稀疏程度,边少就用邻接表,边多到接近平方才考虑矩阵;矩阵把查边压到 O(1),代价是空间按顶点数平方增长;边表和 CSR 各有明确的主场,前者给边优先的算法,后者给只读的大图。
下一篇进入 BFS。存好图只是第一步,真正要回答的是「两个人隔了几层」「到每个点最少走几条边」,这需要按层扩展,而不是一条路走到黑。下一篇就用邻接表把 BFS 的分层、入队标记、0-1 BFS 和网格最短路跑一遍。