《大规模分布式计算深入解析》2.1 邻接表与邻接矩阵:两种表示的代价账本

以 V=1000、E=10000 为样本核算邻接表 80KB 与邻接矩阵 1MB 的空间账本,给出稀疏与稠密表示的适用边界。

邻接表与邻接矩阵:两种表示的代价账本

图的存储表示决定内存账本与查询代价。邻接表为每个顶点存邻居列表,邻接矩阵按 V×V 布尔位记「有无边」。稀疏图用邻接表、稠密图用矩阵,中间的阈值是这道账本的核心。

空间账本

表示空间公式V=1000、E=10000
邻接表(有向)E × 8 字节10000×8 = 80KB
邻接表(无向)2E × 8 字节160KB
邻接矩阵V² 位1000² = 1M 位 ≈ 1MB

lab 用例 4 验证有向邻接表 8 字节/槽位、V=1000/E=10000 时 E×8 = 80KB;用例 5 验证邻接矩阵 V² 布尔 = 1000² = 1M 槽位 ≈ 1MB。稀疏图上矩阵比表大一个数量级,且多数槽位是「无」,浪费。

查询代价与适用边界

邻接表查度数 O(度数)、遍历沿链表走;矩阵查任意两点是否相连 O(1),遍历却要扫整行。NetworkX 与 GraphX 都按稀疏/稠密切换:稀疏用 CSR 压缩,稠密用矩阵运算。这与卷五存储格式账本同构——先量访问模式,再选布局。

验证

从卷十一实验包 解包,运行 graph 模块:用例 4 验证 V=1000、E=10000 有向邻接表 8 字节/槽位 = 80KB;用例 5 验证邻接矩阵 V² 布尔 = 1000² = 1M 槽位 ≈ 1MB。对比稀疏图上差一个数量级的空间。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图