DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Representation of Graph
Two very different tradeoffs for storing the exact same information.
📊 Adjacency Matrix vs Adjacency List
Adjacency MatrixAn n×n grid where cell [i][j]=1 if an edge exists between i and j. Simple, O(1) to check if an edge exists, but wastes O(n²) space even for sparse graphs (few actual edges).
Adjacency ListEach vertex keeps a list of only its actual neighbours. Space-efficient for sparse graphs (real-world graphs usually ARE sparse), but checking a specific edge takes longer than the matrix's instant lookup.
💡 One-liner: "Why is adjacency list generally preferred for large, sparse real-world graphs?" → An adjacency matrix wastes O(n²) space regardless of actual edge count; most real graphs (social networks, road maps) have far fewer edges than the n² maximum, so a list uses dramatically less memory.
How big the difference actually is
"Wastes O(n²) space" understates it. Put realistic numbers in and the gap is enormous.
A social network: n = 1,000,000 users, average 100 friends each
Adjacency matrix: 1,000,000² = 10¹² cells
Adjacency list: 1,000,000 × 100 × 2 ≈ 2 × 10⁸ entries
The matrix needs roughly 5,000 times more storage —
and 99.99% of its cells are zeros.
A graph is called sparse when the edge count is far below the n² maximum, and essentially every real graph is: people have hundreds of friends rather than millions, cities have a handful of roads rather than a road to every other city. Sparseness is the normal case, which is why adjacency lists are the default in practice.
The choice changes the algorithm's complexity
This is the part that matters for exam answers. The same algorithm has different complexity depending on the representation, because the cost of "visit every neighbour" differs.
⚖️ Same operation, different cost
Is there an edge i–j?Matrix: O(1), one lookup. List: O(degree), scan the vertex's list.
Visit all neighbours of iMatrix: O(n), scan the whole row including non-edges. List: O(degree), only real neighbours.
DFS or BFS over the graphMatrix: O(n²). List: O(V + E), which is far smaller when sparse.
Add an edgeBoth O(1). Removing one is O(1) for the matrix, O(degree) for the list.
💡 So "DFS is O(V + E)" silently assumes an adjacency list. On a matrix it is O(V²), because finding each vertex's neighbours means scanning a full row of n cells whether or not edges exist there. State the representation when you quote the complexity.
Syllabus points
Adjacency matrix
Adjacency list
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.