Graph: Sparse vs Dense
- Distinguish between sparse vs. dense graphs.
A sparse graph has relatively few edges, i.e., $M$ is closer to the lower bound $\Omega(N)$.
A dense graph has many edges, i.e., $M$ is closer to the upper bound $\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).