邻接表与邻接矩阵:两种表示的代价账本
图的存储表示决定内存账本与查询代价。邻接表为每个顶点存邻居列表,邻接矩阵按 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。对比稀疏图上差一个数量级的空间。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。