引言
- 稀疏图的定义与特征：边数远少于完全图的图结构，常见于社交网络、推荐系统等场景。
- 高效存储与遍历的意义：降低内存占用、提升计算效率，尤其适合大规模数据处理。
稀疏图的存储结构设计
压缩稀疏行（CSR）与压缩稀疏列（CSC）
- CSR的组成：行指针数组、列索引数组、非零值数组，适用于以行为主的遍历。
- CSC的存储方式：列指针数组、行索引数组，适用于列优先操作如矩阵乘法。
邻接表与变体优化
- 传统邻接表的实现：链表或动态数组存储每个顶点的邻居。
- 优化策略：哈希表加速查询、动态数组减少内存碎片。
键值对与哈希存储
- 边列表的哈希表表示：以
(u, v)为键存储边属性，适合动态增删边的场景。 - 多层哈希：针对超大规模图的分块哈希策略。
高效遍历算法设计
广度优先搜索（BFS）优化
- 基于CSR的BFS实现：利用行指针数组快速访问邻接节点。
- 并行化BFS：使用多线程或GPU加速层次遍历。
深度优先搜索（DFS）优化
- 迭代式DFS减少栈开销：显式栈替代递归。
- 缓存友好的访问模式：预取邻接节点数据。
单源最短路径算法适配
- Dijkstra算法的稀疏图优化：优先队列结合CSR存储。
- 动态剪枝策略：利用边权重分布提前终止无效计算。
