sparse graph

于大型无向图（平均度数为16的克罗内克图（英语：Kronecker graph）模型）中的广度优先搜索（BFS）。测试基准中有三个计算内核：第一个内核用来生成图，并将其压缩为稀疏结构CSR或CSC（Compressed Sparse Row/Column，压缩稀疏行/列）；第二个内核对一些随机顶点进

下表给出了在图上进行各种操作的复杂度。其中，用|V|表示节点数量，|E|表示边的数量。同时假设存储的信息是边上对应的值，如果没有对应值则存储∞。 邻接表在稀疏图（英语：sparse graph）上比较有效率。邻接矩阵则常在图比较稠密的时候使用，判断标准一般为边的数量|E |接近于节点的数量的平方|V |2；邻接矩阵也在查找两节点邻接情况较为频繁时使用。

MATLAB：Matlab_bgl（页面存档备份，存于互联网档案馆）包中 Perl：Graph（页面存档备份，存于互联网档案馆）组件下 Python：SciPy库下（scipy.sparse.csgraph（页面存档备份，存于互联网档案馆）），NetworkX（英语：NetworkX）库中也有

propagation） 值域傳播 （页面存档备份，存于互联网档案馆）（value range propagation） 稀疏有條件的常數傳播 （sparse conditional constant propagation） 消除無用的程式碼 （dead code elimination） 全域數值編號

Peter, Algorithms based on the treewidth of sparse graphs, Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005)