Course contentsShow
← Computer Science
Lesson 693 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Graph Density and Sparsity

Measuring how many edges exist relative to possible edges and implications for algorithm choice.

Graph Density and Sparsity

What you'll learn: How to measure the "fullness" of a graph and why it matters for choosing the right algorithms and data structures.

The Core Idea

Graph density measures how many edges actually exist in your graph compared to the maximum possible number of edges. Think of it like a social network: a "dense" graph is where almost everyone knows almost everyone else, while a "sparse" graph has relatively few connections between people.

For an undirected simple graph with V vertices, the maximum possible edges is V(V-1)/2. For a directed graph, it's V(V-1).

Density formula:

Density = (Actual edges E) / (Maximum possible edges)

A graph with density close to 1 is dense; close to 0 is sparse.

Why This Matters

The density directly impacts which representation and algorithms work best:

  • Sparse graphs (e.g., road networks, social networks): Use adjacency lists. They save memory since you only store edges that exist. Most real-world graphs are sparse!

  • Dense graphs (e.g., complete graphs, small fully-connected systems): Adjacency matrices may work fine here, as the O(V²) space matches the number of edges anyway.

Many graph algorithms perform differently based on density. For example, checking if an edge exists is O(1) with a matrix but O(degree) with a list—crucial when edges are numerous.

Practical Rule of Thumb

If E is close to V (linear), the graph is sparse. If E is close to V² (quadratic), it's dense. Most graphs fall in the sparse category with E = O(V) or E = O(V log V).

Key Takeaway: Graph density determines the ratio of actual to possible edges, guiding your choice of representation (list vs. matrix) and influencing algorithm performance.