sparse graph

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

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

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

度較長的資料上（例如Pac-Bio的測序結果）。 De-Bruijn（英语：De-Bruijn graph）（DBG）法：此方法使用數學圖論中De-Bruijn 圖（英语：De-Bruijn Graph）的概念，先將每個測序片段拆解成k-mer（英语：k-mer）（一個字串中所有長度為k的可能字串

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