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.

Answer 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.

Answer 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.