What is the distinction between sparse and dense graphs?

Question

I read it is ideal to represent sparse graphs by adjacency lists and dense graphs by an adjacency matrix. But I would like to understand the main difference between sparse and dense graphs.

Solution 1

Dense graph is a graph in which the number of edges is close to the maximal number of edges. Sparse graph is a graph in which the number of edges is close to the minimal number of edges. Sparse graph can be a disconnected graph.

Solution 2

As the names indicate sparse graphs are sparsely connected (eg: Trees). Usually the number of edges is in O(n) where n is the number of vertices. Therefore adjacency lists are preferred since they require constant space for every edge.

Dense graphs are densely connected. Here number of edges is usually O(n^2). Therefore adjacency matrix is preferred.

To give a comparison, let us assume graph has 1000 vertices.

Irrespective of whether the graph is dense or sparse, adjacency matrix requires 1000^2 = 1,000,000 values to be stored.

If the graph is minimally connected (i.e. it is a tree), the adjacency list requires storing 2,997 values. If the graph is fully connected it requires storing 3,000,000 values.

Solution 3

From Data Structures and Algorithms with Object-Oriented Design Patterns in C++ , p. 534, by Bruno P. Reiss:

Informally, a graph with relatively few edges is sparse, and a graph with many edges is dense.

Definition (Sparse Graph): A sparse graph is a graph G = (V, E) in which |E| = O(|V|).

Definition (Dense Graph) A dense graph is a graph G = (V, E) in which |E| = Θ(|V|²).

Solution 4

Main graph integral characteristics are number of vertices V and number of edges E. The relation of these two determines whether graph is sparse or dense (wiki page here).

The whole theory behind choosing graph in-memory representation is about determining the optimal access time vs memory footprint tradeoff, considering subject domain and usage specifics.

Generally you want to have O(1) access time (and thus store the graph as a dense adjacency matrix) unless you can't tolerate memory footprint, in which case you choose the most appropriate sparse matrix representation (wiki page here).

Solution 5

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and depends on the context.

View more solutions

Comments

[Gabor Csardi]

I think a graph with n vertices is considered to be sparse if it has O(n) or less edges.

[JayJay]

Conversely, a graph with n vertices is dense if the number of edges is O(n^2)

[Akash Kandpal]

Several examples of sparse graphs are: Transportation and road networks where the intersections are vertices and roads are edges. For such networks, the number of roads is not significantly larger than the number of intersections (in other words E~=c * V, where c is in the range of 2-3). While in many cases real-world graphs are sparse, it is possible to create weighted graphs that are highly dense with the edge weight representing some sort of relationship - such as a large edge weight if two people visited the same store at the same time or had coffee at the same coffee-shop.

[Akash Kandpal]

Another example might be to take a "sub-graph" of a sparse graph that represents a community of people that are highly connected.

[Surya Teja Vemparala]

How adjacency list for 1000 vertices requires 2997 values? Can you elaborate more pls?

[lucifer]

@SuryaTejaVemparala sparse graph is considered a tree here. consider the tree as 1-2-3-4- .... - 1000, for every vertice from 2 - 999, there would be 2 entries, one for previous vertex and other for next one. First and last will have one entry each, and then extra space for all the keys in the adjacency list if constructed through Hashmap. I believe this can be reduced down to 1998 if used list of lists.