sparse graph

A graph with far fewer edges than the maximum possible, closer to V than to V squared.

In more detail

Road networks and social networks are sparse: each vertex connects to a handful of others. An adjacency list stores them compactly, while a matrix would be almost all zeros.

Related terms

Taught in

References