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

Choosing Representation by Graph Density

Select optimal representation based on whether graph is sparse (E << V²) or dense (E ≈ V²).

Choosing Representation by Graph Density

What you'll learn: How to pick the best graph representation (adjacency matrix vs adjacency list) based on whether your graph is sparse or dense.


Understanding Graph Density

Graph density describes how many edges exist compared to the maximum possible. A graph with V vertices can have at most V² edges (in a directed graph). When we talk about density, we're asking: "How close are we to that maximum?"

  • Sparse Graph: E << V² (far fewer edges than possible)
    • Example: Social networks — most people know only a tiny fraction of all users
  • Dense Graph: E ≈ V² (edges approach the theoretical maximum)
    • Example: Complete graphs or nearly-complete graphs where most vertices connect to most others

Matching Representation to Density

For Sparse Graphs (E << V²): Use an adjacency list. You only store actual edges, so memory usage is O(V + E). Since E is small relative to V², this is highly efficient. Iterating over neighbors is fast because you skip non-existent edges.

For Dense Graphs (E ≈ V²): Use an adjacency matrix. You're already using O(V²) space, but since most cells represent real edges, little space is wasted. Edge lookups are O(1), which becomes valuable when you frequently check "Does edge (u, v) exist?"

The Decision Rule

Think of it like packing a suitcase:

  • Sparse graph = packing only what you need (adjacency list)
  • Dense graph = using a structured organizer with slots (adjacency matrix)

Key Takeaway: Choose adjacency lists for sparse graphs (most real-world networks) to save memory; choose adjacency matrices for dense graphs when fast edge lookups matter and memory for O(V²) is acceptable.