What is the distinction between sparse and dense g

问题:

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.

回答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.

回答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.

回答3:

From here:

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

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

回答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.