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
- dense graph — A graph in which most pairs of vertices are connected, so the edge count is close to V squared.
- adjacency list — A graph representation that stores, for each vertex, a list of its neighbours, typically as a dict of lists in Python.
Taught in
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers