Graph Data Structure Representation from Scratch (2026)
A graph is a collection of vertices (nodes) connected by edges. Choosing the right graph representation is critical for algorithm performance. The three most common representations are adjacency matrix, adjacency list, and edge list — each with distinct trade-offs in memory usage, edge lookup speed, and iteration efficiency.
Graphs can be directed or undirected, weighted or unweighted. The representation choice depends on the density of the graph and the operations required. For sparse graphs, adjacency lists are generally preferred, while dense graphs may benefit from adjacency matrices.
Adjacency Matrix
An adjacency matrix is an n×n 2D array where matrix[i][j] = 1 (or weight) if there is an edge from i to j. It offers O(1) edge lookup but uses O(n²) memory, making it suitable for dense graphs (n ≤ 1000 typically). It is simple to implement but wastes space for sparse graphs.
// C++: Adjacency Matrix (directed weighted)
int graph[100][100] = {0};
void addEdge(int u, int v, int w) { graph[u][v] = w; }
bool hasEdge(int u, int v) { return graph[u][v] != 0; }Adjacency List and Edge List
An adjacency list stores an array of vectors: for each vertex, a list of neighbors (and optionally weights). It uses O(n + m) memory, ideal for sparse graphs. An edge list stores all edges as tuples (u, v, w), used in algorithms like Kruskal's MST where sorting edges is required.
# Python: Adjacency List
from collections import defaultdict
graph = defaultdict(list)
def add_edge(u, v, w=1):
graph[u].append((v, w))
graph[v].append((u, w)) # undirected
# Edge list
edges = [(0, 1, 4), (1, 2, 3), (2, 0, 5)]
# Kruskal's: edges.sort(key=lambda x: x[2])Frequently Asked Questions
When should I use an adjacency matrix?
Use an adjacency matrix for dense graphs (n² ≈ m) or when you need O(1) edge existence checks. Memory constraints typically limit this to n ≤ 10^4 for unweighted (bitset) or n ≤ 10^3 for weighted.
What is the space complexity of an adjacency list?
O(n + m) where n is the number of vertices and m is the number of edges. For directed graphs, each edge appears once; for undirected, twice. This is the most memory-efficient representation for sparse graphs.
Originally published on Ayodhyyya. Last updated June 1, 2026.