定义

        数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），反之边的条数|E|接近|V|²，称为稠密图（dense

graph）。此定义来自百度百科，实际上是一种朴素的理解，简单来说边越多，图就越稠密（其中|V|是结点数的意思，有时也用n来表示）

判断稀疏图与稠密图

首先是一个基本结论：一个有n个点的图最多有 n² （|V|²）条边，有m条边的图最多有(m+1)个结点。

稠密图与稀疏图判断方式没有绝对的标准，可以依据定义来判断，比如边的条数|E|很接近|V|²，那么毫无疑问是个稠密图，但是写算法时经常要根据数据的特点选择使用邻接矩阵还是邻接表，所以我们可以从使用算法的复杂度出发，比如对于Dijkstra算法，朴素Dijkstra时间复杂度是n²，而堆优化Dijkstra时间复杂度mlogn，其中m是边的个数，所以单从算法效率上讲，稀疏图与稠密图的分界点大概就在m=n²/logn处，但是实际上复杂度是有系数的，所以单从式子上计算也是不太科学的，可以作为一个参考。

现在主要的说法是以m=nlogn作为区别稀疏图与稠密图的标准，实际上这个说法也不是很准确，但是考虑到实际场景中的数据，我们构造的图的边大多数时候是很显然远大于nlogn或者远小于nlogn的，所以用这个方式判断也是合理的。

但是对于特定构造的情况，尤其是一些算法题目中，可能要结合实际实现算法的复杂度与系数进行比较，选择邻接矩阵还是邻接表来求解。（其中邻接矩阵适合稠密图，邻接表适合稀疏图）

原文地址：http://www.cnblogs.com/xiaotan-js/p/16792681.html