Graph: Sparse vs Dense

  • Distinguish between sparse vs. dense graphs.

A sparse graph has relatively few edges, i.e., MM is closer to the lower bound Ω(N)\Omega(N).

A dense graph has many edges, i.e., MM is closer to the upper bound O(N2)\Omicron(N^2).

Graph representation (implementation) choice will depend on whether the problem at hand is more likely to be a sparse or dense graph!

If your graph is sparse, adjacency list representation will be more efficient (in terms of space complexity).