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

If the number of the edges is close to the maximum number of edges in a graph, then that graph is a Dense graph. In a dense graph, every pair of vertices is connected by one edge.

The Sparse graph is completely the opposite. If a graph has only a few edges (the number of edges is close to the minimum number of edges), then it is a sparse graph.

There is no strict distinction between the sparse and the dense graphs. Typically, a sparse (connected) graph has about as many edges as vertices, and a dense graph has nearly the maximum number of edges.

Answer 2

Adding to above answers, A Simpler explanation can be,

• Dense Graph If all vertices or nodes in a graph is densely connected (i.e. a node that connects with all neighbour nodes with all possible edges). Here possibly, total number of edges > total number of nodes.

• Sparse Graph Its an vice versa of dense graph, Here we can observe that a node or vertices is not fully connected to its neighbouring nodes (i.e. it has unconnected/remaining edges). Here possibly, total number of edges <= total number of nodes.

Answer 3

Sparse Graphs - Graphs with relatively few edges (generally if it edges < |V| log |V|) are called sparse graphs. Dense Graphs- Graphs with relatively few of the possible edges missing (as compared to complete graph) are called dense graph.

Answer 4

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 5

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|²).

Answer 6

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.

Answer 7

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.

Answer 8

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