What Are the Main Graph Representation Techniques?
Compare adjacency list, adjacency matrix, and edge list graph representations and when to use each for this interview question.
Expected Interview Answer
The two main graph representation techniques are the adjacency list, which stores each vertex with a list of its neighbors and is space-efficient at O(V + E), and the adjacency matrix, which stores a V-by-V grid of edge presence and gives O(1) edge lookup at the cost of O(V²) space.
An adjacency list keeps, for each vertex, a collection of the vertices it connects to (plus a weight if the edge is weighted), which is ideal for sparse graphs where E is much smaller than V². An adjacency matrix instead allocates a full grid where cell (i, j) records whether an edge exists between vertex i and j, giving instant O(1) edge-existence checks but wasting memory on graphs with few edges. A third, less common option is an edge list, a flat array of (u, v, weight) tuples, which is compact and simple to sort but slow for neighbor lookups. The right choice depends on graph density and the dominant operation: iterate neighbors (adjacency list) versus check a specific edge (adjacency matrix).
- Adjacency list: O(V + E) space, ideal for sparse graphs
- Adjacency matrix: O(1) edge lookup, simple to implement
- Edge list: compact, good for algorithms that sort edges (Kruskal)
- Choice directly impacts traversal and query performance
AI Mentor Explanation
An adjacency list is like a coach keeping a separate notecard per team listing only the teams they have actually played, which stays short and useful even in a huge tournament with hundreds of teams. An adjacency matrix is like printing one giant grid with every team down the side and across the top, marking a tick wherever two teams have met, which wastes a lot of blank cells if most teams never faced each other. Checking whether Team A played Team B is instant in the grid — just look up one cell — but scanning the grid to list all of Team A opponents means reading an entire row. The notecard approach wins when most pairs never play; the grid wins when you need instant yes/no answers about any specific pair.
Step-by-Step Explanation
Step 1
Choose adjacency list for sparse graphs
Store each vertex with a list of (neighbor, weight) pairs; O(V + E) space, fast neighbor iteration.
Step 2
Choose adjacency matrix for dense graphs or O(1) lookup
A V x V grid where cell (i, j) marks edge presence or weight; O(V²) space.
Step 3
Consider an edge list for edge-centric algorithms
A flat array of (u, v, weight) tuples, easy to sort — used by Kruskal minimum spanning tree.
Step 4
Match representation to dominant operation
Neighbor iteration favors adjacency list; specific edge existence checks favor adjacency matrix.
What Interviewer Expects
- Name adjacency list and adjacency matrix as the two primary representations
- State space complexity for each: O(V + E) vs O(V²)
- Explain the tradeoff between edge lookup speed and memory
- Mention edge list as a third option and where it is used
Common Mistakes
- Claiming one representation is always better regardless of graph density
- Forgetting adjacency matrix uses O(V²) space even for sparse graphs
- Not knowing adjacency list gives O(degree) neighbor iteration vs O(V) for a matrix row
- Confusing an edge list with an adjacency list
Best Answer (HR Friendly)
“I usually store a graph either as an adjacency list, where each node keeps a short list of its neighbors, or as an adjacency matrix, which is a full grid marking which nodes connect. I pick the list for most real-world graphs because they are sparse, and the matrix only when I need instant lookups on a small, dense graph.”
Code Example
# Adjacency list: space-efficient for sparse graphs
adjacency_list = {
"A": [("B", 4), ("C", 1)],
"B": [("C", 2)],
"C": [],
}
def neighbors(graph, u):
return graph.get(u, []) # O(degree(u))
# Adjacency matrix: O(1) edge lookup, O(V^2) space
vertices = ["A", "B", "C"]
index = {v: i for i, v in enumerate(vertices)}
matrix = [[0] * len(vertices) for _ in vertices]
def add_edge(u, v, weight):
matrix[index[u]][index[v]] = weight
add_edge("A", "B", 4)
has_edge = matrix[index["A"]][index["B"]] != 0 # O(1)Follow-up Questions
- When would you prefer an adjacency matrix over an adjacency list?
- How does the choice of representation affect BFS or DFS runtime?
- How would you represent a weighted graph in each format?
- How does an edge list help algorithms like Kruskal minimum spanning tree?
MCQ Practice
1. What is the space complexity of an adjacency list for a graph with V vertices and E edges?
An adjacency list stores each vertex plus one entry per edge, giving O(V + E) space.
2. Which representation gives O(1) time to check if an edge exists between two specific vertices?
An adjacency matrix stores a direct grid cell per vertex pair, so checking a specific edge is O(1).
3. Which representation is most space-wasteful for a sparse graph?
An adjacency matrix always allocates O(V^2) space regardless of how few edges exist, wasting memory on sparse graphs.
Flash Cards
What space complexity does an adjacency list use? — O(V + E), efficient for sparse graphs.
What space complexity does an adjacency matrix use? — O(V^2), regardless of edge count.
Which representation gives O(1) edge existence checks? — The adjacency matrix.
What is an edge list good for? — Edge-centric algorithms like Kruskal minimum spanning tree, since it is easy to sort by weight.