Python图数据结构重构：从邻接表到CSR稀疏矩阵的性能跃升

先从一次线上事故说起。上个月跑一批千万级节点的关系链路分析，脚本在凌晨4点准时被Linux的OOM Killer干掉，日志里只有一行Killed process。换机器重跑，两天后内存又爆了一轮。后来把图的数据结构整体翻新一遍，同样的任务内存占用从11GB降到1.8GB，单次全图遍历从22秒压进1.1秒。这次实战让我确信一件事：大部分图相关的性能问题，不怪算法，怪的是图的表示方式。

很多团队把图问题等同于算法问题，一上来就调BFS、调Dijkstra，忽略了底层数据结构。我这次要聊的就是基于Python的图结构重构与性能调优，从邻接表到CSR稀疏矩阵的迁移、算法适配、缓存策略，以及重构前后的真实数据。适合正在处理十万级节点以上图数据、又被内存和耗时卡住的朋友参考。

1.1 三个影响图性能的结构指标

拿到一张图，先别急着写代码。我建议先用15分钟做一次结构体检，重点看三个指标：

图密度。就是实际边数占完全图边数的比例。公式是density = E / (V*(V-1)/2)（无向图），有向图是E / (V*(V-1))。密度小于0.05的算稀疏图，大于0.5就是稠密图。这个值直接决定你用邻接矩阵还是邻接表。80万节点的社交网络一般密度都在万分之几，但一个班级协作网可以到0.6以上。

平均度与度分布。平均度等于2E/V（无向图），但平均度会骗人。有的图平均度看着只有8，实际尾部节点度上千，这种极度右偏的分布对邻接表查询很不利。用np.bincount扫一遍所有节点的度数，看P99和P50的差距，差距超过50倍就有问题。

连通分量与环结构。一张看似庞大的图往往分为上千个互不相连的小块。可以先跑一遍连通分量分析，如果最大连通分量只有全图的30%，说明这张图在结构上是破碎的，很多算法根本不需要在全图范围跑，按分量分而治之反而快得多。

这三个指标决定重构方向，也决定后面所有优化的预期上限。

1.2 两个可以直接用的诊断脚本

诊断代码不用写得很复杂，重点是快速出结果。我常用的就是下面两段。

第一段读边列表，输出基本信息：

import numpy as np import pandas as pd df = pd.read_csv("edges.csv", header=None, names=["src", "dst", "weight"]) nodes = pd.unique(pd.concat([df["src"], df["dst"]])) n = len(nodes) - 1 # 假设节点编号从0开始连续，不连续要先重映射 m = len(df) # 有向图密度 density_directed = m / (n * (n - 1)) # 无向图密度（如果边是双向的） density_undirected = 2 * m / (n * (n - 1)) print(f"节点数: {n}, 边数: {m}") print(f"有向密度: {density_directed:.6f}, 无向密度: {density_undirected:.6f}") # 度数分布 degrees = np.bincount(df["src"].to_numpy(), minlength=n) + np.bincount(df["dst"].to_numpy(), minlength=n) p50 = np.percentile(degrees, 50) p99 = np.percentile(degrees, 99) print(f"度数P50: {p50}, P99: {p99}, 最大: {degrees.max()}")

第二段统计连通分量，顺带压测一下内存基线：

from collections import deque import sys def component_sizes(adj): visited = set() sizes = [] for start in range(len(adj)): if start in visited: continue q = deque([start]) visited.add(start) cnt = 0 while q: u = q.popleft() cnt += 1 for v in adj[u]: if v not in visited: visited.add(v) q.append(v) sizes.append(cnt) return sorted(sizes, reverse=True) # 粗略估计当前表示法的内存占用 def estimate_memory(adj): total = 0 for k, vs in adj.items(): total += sys.getsizeof(k) + sys.getsizeof(vs) return total / 1024 / 1024 sizes = component_sizes(adj) print(f"连通分量个数: {len(sizes)}") print(f"最大分量占比: {sizes[0] / n:.2%}") print(f"邻接表预估内存: {estimate_memory(adj):.1f} MB")

跑一遍之后，你会对图是什么脾气有一个直观判断。接下来选型才有依据。

2. 四种表示法各有脾气：不弄清适用边界别急着动手

图结构在Python里的主流表示法就那么几套：邻接矩阵、邻接表、CSR/CSC稀疏矩阵、边列表。它们不是随便选的，每种表示背后对应一种计算模式。

2.1 邻接矩阵的“暴力美学”与容量上限

邻接矩阵是二维数组A[u][v]，有边为1（或权重），无边为0。查询任意两点之间是否有边是O(1)，这是它最大的优势。

但代价太沉重了。100万节点的稠密布尔矩阵需要1000000 × 1000000 / 8字节，约125GB。如果用int32存，直接上4000GB。哪怕只有10万节点，int32矩阵也要40GB。所以邻接矩阵只适合节点数不超过一两万、且密度较高的场景。

那什么时候用它？我见过一个案例：一个2万节点、4000万边的概率转移图，密度0.2，查询极频繁，用邻接表查一条边要遍历邻居列表，用矩阵就是一两次内存索引的事。那个场景矩阵反而赢了，因为它把查询量压到了极致。

2.2 邻接表：好用但吃内存

邻接表用dict[节点] -> list/set[邻居]表示。查询出边快、插入删除方便、写起来顺手，NetworkX的默认Graph底层就大量用了dict。

但Python dict的overhead非常大。一个int键要28字节，一个int值也要28字节，一个dict条目还要额外的哈希表空间，算下来一张100万节点、1.2亿条边的图，用dict[set]结构存储，内存可以突破8GB，甚至10GB。我在实战里碰到过最夸张的一次，1200万条边吃掉了6GB，还没开始跑算法。这就是典型的“表示法吃掉了预算”。

邻接表不是不能用，它适合节点数在几十万以内、边数几百万的场景，而且适合频繁增删边的动态图。但如果你要跑的是一次性批量分析，该换就换。

2.3 CSR/CSC：大规模图的工业标准

CSR（Compressed Sparse Row）是工业界大规模图标准存储。它用三个一维数组搞定一切：

• indptr：长度V+1，记录每个节点的出边在indices/data中的起始偏移。
• indices：长度E，按节点顺序排列的邻居编号。
• data：长度E，与indices对应的边权。

100万节点、1.2亿条边的图，用CSR存，indptr大约4MB（100万×4字节int32），indices约480MB（1.2亿×4字节），data若用float32约480MB，总内存不到1GB。对比邻接表的8GB，差距非常明显。

更关键的是，CSR在遍历出边时是连续内存访问，CPU缓存友好。我实测下来，同样是全图BFS，CSR比邻接表快一个数量级。它是稀疏矩阵运算库scipy.sparse和大部分图计算引擎（igraph、graph-tool）的底层存储，也是我们这次重构的核心目标。

CSC是CSR的列优先版本，适合按入边查询的场景。如果你的算法大量查“谁指向我”，CSC更合适，不过实际项目中通常是CSR+CSC各维护一份。

2.4 边列表：只适合当源头数据

边列表就是三列src, dst, weight，通常来自CSV或数据库导出的原始数据。它唯一的优势是导入导出方便，任何图都可以先落到边列表再转成其他格式。

但拿着边列表直接跑算法就是灾难，查一个节点的邻居需要扫描全表，O(E)复杂度。我做数据清洗时只会拿边列表做统计，比如总边数、权重分布、重复边检查，等清洗干净再转CSR或邻接表进入正题。

为了帮助理解这四种表示法的差异，我把结论整理成一张速查表：

3. 重构实操：把1.2亿条边的“dict大礼包”换成CSR

选型定了，下面就是动手环节。我用一个1.2亿条边的有向带权图作为案例，把从边列表到CSR的四个步骤完整走一遍。

3.1 第一步：边列表预处理与重复边的合并

CSR构建之前最烦的是重复边。原始数据里同样的(src, dst)可能出现多次，有的是业务上确实有多次交互，需要累加权重；有的是采集错误，需要去重。

我习惯用pandas先做一次聚合并重映射节点编号：

import pandas as pd import numpy as np df = pd.read_csv("edges.csv", header=None, names=["src", "dst", "weight"]) # 重复边合并，权重求和 df = df.groupby(["src", "dst"], sort=False)["weight"].sum().reset_index() # 节点重映射到连续编号，避免稀疏编号导致数组巨大 all_nodes = np.unique(np.concatenate([df["src"].to_numpy(), df["dst"].to_numpy()])) node_map = {node: i for i, node in enumerate(all_nodes)} df["src_id"] = df["src"].map(node_map) df["dst_id"] = df["dst"].map(node_map) n = len(all_nodes) m = len(df) print(f"节点数: {n}, 去重后边数: {m}") # 丢弃原节点列，省内存 df = df[["src_id", "dst_id", "weight"]]

这里有个经验：节点重映射非常关键。如果原始节点是字符串，不映射成int32连续编号，后面所有数组都建不起来。UUID当节点ID的图数据，映射后内存能再缩一半以上。

3.2 第二步：构建CSR三件套

接下来用scipy.sparse的csr_matrix一步到位。它内部就是标准CSR三件套，而且自带大量批量运算方法。

from scipy.sparse import csr_matrix def build_csr_from_df(df, n): rows = df["src_id"].to_numpy(dtype=np.int32) cols = df["dst_id"].to_numpy(dtype=np.int32) data = df["weight"].to_numpy(dtype=np.float32) return csr_matrix((data, (rows, cols)), shape=(n, n)) A = build_csr_from_df(df, n) print(f"CSR矩阵形状: {A.shape}") print(f"非零元素数: {A.nnz}")

如果有人只想用纯numpy不依赖scipy，手动构造也很简单：

import numpy as np src = df["src_id"].to_numpy(dtype=np.int32) dst = df["dst_id"].to_numpy(dtype=np.int32) vals = df["weight"].to_numpy(dtype=np.float32) # 按src排序，让同一节点的出边连续存放 order = np.argsort(src, kind="stable") src = src[order] dst = dst[order] vals = vals[order] indptr = np.zeros(n + 1, dtype=np.int64) np.cumsum(np.bincount(src, minlength=n), out=indptr[1:]) indices = dst data = vals

两种方式都行，建议优先用scipy，稳定性更好。构建完可以检查一下A.indptr, A.indices, A.data，确保和预期一致。

3.3 第三步：查询、出边遍历算法的改造

重构之后，原来的邻接表操作要对应改掉。下面是三组最常见操作的新写法。

查某个节点的出边：

def get_out_edges(A, u): start, end = A.indptr[u], A.indptr[u + 1] return A.indices[start:end], A.data[start:end]

这个操作几乎零成本，indices[start:end]本身是连续切片，直接拿到numpy数组。

查两点之间是否有边：

def has_edge(A, u, v): start, end = A.indptr[u], A.indptr[u + 1] # 邻居有序的话可以用 searchsorted，无序就 while idx = np.searchsorted(A.indices[start:end], v) return idx < end - start and A.indices[start + idx] == v

全图BFS的适配版本：

from collections import deque import numpy as np def bfs_csr(A, s): n = A.shape[0] dist = np.full(n, -1, dtype=np.int32) dist[s] = 0 q = deque([s]) while q: u = q.popleft() start, end = A.indptr[u], A.indptr[u + 1] for i in range(start, end): v = A.indices[i] if dist[v] == -1: dist[v] = dist[u] + 1 q.append(v) return dist

看起来和邻接表版本差别不大，但内部从dict查key变成了连续数组索引，同样的图，这个BFS能跑到接近C代码的速度。

下面举一个完整的实际对比，让大家直观感受代码改动量其实很小：

# 重构前：邻接表 for u in range(n): for v in adj[u]: process(v) # 重构后：CSR for u in range(n): start, end = A.indptr[u], A.indptr[u + 1] for i in range(start, end): v = A.indices[i] process(v)

逻辑层几乎不需要动，只要把“遍历邻居”这件事抽象成一个函数或迭代器，后续算法代码都能直接被新结构复用。

3.4 第四步：与NetworkX混用的桥接方案

有些图算法生态只有NetworkX有现成实现，比如某些社区发现、中心度指标。全量迁过去的代价太大，我通常的做法是用CSR做粗算，把结果转回NetworkX只跑关键子图。

import networkx as nx def csr_to_networkx(A): G = nx.DiGraph() rows, cols = A.nonzero() for u, v in zip(rows, cols): G.add_edge(int(u), int(v), weight=A[u, v]) return G

注意，这个转换只适合小图。超过百万边就别转NetworkX了，老老实实找替代算法实现。我一般建议：NetworkX只用于建模验证和画图，生产链路的核心计算全部落到CSR上。

4. 性能调优不是玄学：四个动手就能见效的层

结构重构是第一步，后面还有一系列调优手段。我按“收益从大到小、成本从小到大”排个序，大家按这个顺序动手。

4.1 数据结构层：少用Python对象，多用连续内存

Python里每创建一个int对象、一个tuple、一个dict条目，都有大量内存开销。图数据一旦到千万级，这些开销会直接压垮性能。

我总结的替换原则：能用numpy数组绝不用Python list，能用list绝不用dict，能用元组当tuple绝不用class。

具体到图领域，几个高频替换：

• 节点集合：set换成numpy.bool_数组或bitarray。
• 邻居判断：list换成numpy.ndarray，配合二分查找。
• 边权存储：dict[(u, v)] = w换成两个numpy数组，或者直接放CSR。
• 节点ID：字符串一律映射成int32。

有人会质疑，这些改动会不会把代码搞晦涩。我的观点是，底层表示和业务逻辑分离，暴露给算法层的API保持稳定，就不会牺牲可读性。

4.2 算法层：迭代BFS代替递归DFS，能用numpy别用for

递归DFS在Python里非常危险，一是Python默认递归深度约1000，图稍大直接RecursionError；二是每次递归调用都有帧开销，大图慢到怀疑人生。

优先写成迭代BFS。如果必须DFS，也用手动栈：

def dfs_csr(A, s): n = A.shape[0] vis = np.zeros(n, dtype=bool) stack = [s] vis[s] = True while stack: u = stack.pop() start, end = A.indptr[u], A.indptr[u + 1] for i in range(start, end): v = A.indices[i] if not vis[v]: vis[v] = True stack.append(v)

另一个常见优化是向量化。比如要统计每个节点的出边权重之和，用笨办法是遍历所有A.indptr区间逐个相加，改用scipy的A.sum(axis=1)直接拿到每行和，一行代码：

out_degree_sum = np.asarray(A.sum(axis=1)).ravel()

之前一个12万行的循环要跑0.8秒，向量化后0.01秒。能向量化的计算绝不要手动写循环。

4.3 计算层：scipy.sparse里那些被低估的批量操作

scipy.sparse自带很多矩阵运算，很多图算法可以借用线性代数思路实现。

• 计算一跳邻居数量：A @ np.ones(n)。
• 两跳邻居粗估：A @ (A @ ones)。
• 三角形计数：对无向图可以用trace(A @ A @ A) / 6的近似思路（只适合小规模验证）。
• 页面排名：直接用幂迭代r = alpha * A @ r + beta。

这些表达式在底层是编译过的C代码，比Python手写的循环快太多。举个例子，某次我需要计算每个节点的二阶影响力，手写循环跑了半小时，改成A @ A的稀疏乘法，三分钟出结果，内存也没爆。

不过要提醒一句：稀疏矩阵乘法在某些结构下会急剧膨胀，如果两个高密度子图乘起来，中间产物可能比原图大几十倍。操作前先预估一下nnz增长曲线，膨胀严重就分块做。

4.4 缓存层：重复计算是性能黑洞

图算法的另一个通病是反复算同一个结果。最典型的是中心度、最短路径、连通分量这些指标，在参数调优阶段会被反复调用。

我常用的缓存策略：

• 用functools.lru_cache装饰纯函数，比如根据参数返回某个子图结构。
• 把昂贵的计算结果序列化到磁盘，用pickle或numpy.savez，进程重启后直接load。
• 对增量更新的图，维护一个脏标记，节点或边有变动才重算缓存指标。

举个例子，计算每个节点的PageRank需要迭代一百多轮，如果每次调参都从头跑一遍就太亏了。我会把上一轮的r向量存成npy，下一轮用它作为初始值，迭代次数经常从150次降到20次内收敛，时间省78%。

5. 重构前后的实测数据：800万节点社交关系图

理论说了不少，来看一组我实测的真实数据。测试对象是一张整理过的社交关系有向图，800万节点、1.2亿条带权边，无重复边，节点编号本身不连续。机器是16核32GB的普通云主机，Python 3.11。

5.1 测试场景与基线

原始方案用的是NetworkX.DiGraph，从CSV读进内存，用了约2小时导入，内存峰值11.4GB。当时以为还能扛住，直到跑一次全图Dijkstra链路分析，半小时没出结果，最后OOM。

重构方案分两步走，先用CSR代替NetworkX，再把热点算法向量化加缓存。参与对比的测试项：

• J：全图从任意节点出发的BFS遍历平均耗时（抽100个起点取均值）。
• K：从指定节点查询一跳出边并聚合权重。
• L：全图PageRank 100轮迭代耗时。
• 内存峰值：整张图读入内存后的常驻内存。

5.2 结果分析：内存降了多少、时间快了多少

结果如下：

补充说明一下内存的变化：NetworkX存800万节点的DiGraph本身就有很大的节点对象和哈希表开销，再加上维护入边出边两套索引，内存很容易膨胀到边的数量乘以70~80字节。CSR用边数乘以大概12字节就解决问题，因为int32的indices和float32的data都是紧凑数组。

PageRank从132秒压到29秒的贡献主要来自两点：一个是用A @ r替代手动循环，另一个是缓存上一轮结果当初值。这两步都在本章第4节讲过，效果非常直接。

事实证明：换数据结构，比花时间优化Python循环语句高效得多。数据结构决定性能量级，循环微调只决定常量因子。

提示：以上数据是在这台云主机上测的，不同机器、不同Python版本、不同图密度可能差异较大。但方向上一般不会变：大规模稀疏图用CSR在内存和时间上都有数量级优势。

6. 这一路踩过的坑：关于图优化的六条经验

最后分享几条我从实际项目里踩出来的教训，每一条背后都有一段不得不说的故事。

6.1 稀疏图的“伪优化”

第一个坑是盲目把邻接表换成CSR，结果更慢了。原因是那张图节点30万、边只有28万，很多节点出度为0甚至个位数。这种超稀疏图中，CSR的indptr和indices虽然紧凑，但每次遍历还是要走两层数组索引，反而比dict的直接哈希多了一些间接跳转。

我的经验：平均度数低于3的图，优先保留邻接表；平均度数在10以上或者需要频繁跑矩阵运算的，才适合CSR。这个判断依赖我第一部分的图密度体检，所以我说刚开始的体检很重要。

6.2 整数类型与内存边界

第二个坑是整数类型选择。CSR里indices用int32，如果节点数超过21亿会溢出，这种情况不罕见，大图里节点ID可能全局起编号到几十亿。用int64更安全但内存翻倍。我的建议：先看节点总数，少于10亿用int32，超出就int64，别贪内存。

还有一个隐藏问题：indptr的长度是V+1，用int32的话，当边数超过21亿时也会有溢出。我用np.int64给indptr保底，特别是长尾图，边数很容易冲爆int32。

6.3 不要迷信库的默认实现

第三个坑是对成熟库的盲信。NetworkX的shortest_path在1.2亿边大图上几乎不可用，igraph在同样场景下快得多，但igraph的某些社区检测算法又不如networkX丰富。我的建议是：大图计算，底层数据结构走CSR和igraph/graph-tool，上层图算法能借用scipy矩阵表达式就不手写循环，只有小图和可视化才交给NetworkX。

6.4 边方向、权重、多图拆分的业务重构

第四个坑是过度关注技术重构，忘了业务层面的图结构重构。我处理过一个多关系混合图，一张图里同时有“关注、点赞、收藏、屏蔽”四种关系，结果很多分析结果都是噪音。后来我按关系类型拆成四张单关系子图，各自建CSR，不仅内存小了，分析的精确度也上来了。

另一个业务重构技巧是方向压缩。有些无向分析场景，比如判断两个用户是否有过直接交互，你根本不需要区分方向。我把有向图转成无向图后，数据量直接减半，很多算法的输入规模也跟着缩小。类似的还有：边权归一化，把权重落在0到1区间，有利于后续的矩阵运算收敛。

6.5 延迟加载与磁盘回退

第五个坑是妄想把全图塞进内存。一张包含几十亿边的图，即使CSR存储也需要几十GB，内存不够就必须用图分区或磁盘回退方案。我常用的做法是划分连通分量，把最大分量之外的小分量上抛到独立文件，逐个处理。配合第1节的连通分量分析，这个策略非常稳。

还有一种更简单的思路：用numpy.memmap将indices和data直接映射到磁盘文件，内存只保留indptr。虽然访问速度比纯内存慢，但胜在可以处理远超物理内存的图。我处理100亿条边的数据时就用过这个方案。

6.6 先分析再优化，是最大的经验

最后一句话总结这一路折腾：先分析图的结构特征，再选数据结构，最后才谈算法优化。顺序反了，后面所有努力都是在错误的地基上盖楼。

如果现在有人再拿一张图找我，我不会急着写BFS、Dijkstra，我会先问三个问题：这张图多大、多稀疏、要跑什么业务。然后根据一、二、三、四的顺序做一次体检，再决定用邻接表还是CSR，要不要拆分多图，要不要缓存中间结果。

这也是我最想在这篇文章里说清楚的一件事：图优化的第一课是认识你的图，第二课才是动手改代码。认识了图，上面所有重构和调优才会落到正确的位置上。

最后再分享一个小技巧：如果你经常处理图数据，把第一部分和第三部分的代码存成工具脚本，把CSR构建、基础统计、BFS/DFS封装成通用接口，后续所有图项目都从这套接口开始。一次投入，长期收益，非常划算。