What is the distinction between sparse and dense graphs?

Geek picture Geek · Sep 26, 2012 · Viewed 55.7k times · Source

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

CAMOBAP picture CAMOBAP · Sep 26, 2012

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.