Representing a graph

Adjacency list vs matrix vs edge list, and the directed/undirected/weighted choices. · 10 min read

What a graph is

A graph is a set of vertices connected by edges. Edges can be directed (one-way) or undirected, and weighted or unweighted. Trees, grids, road networks, dependency graphs, and social networks are all graphs — most non-trivial algorithms problems are graph problems in disguise.

Three representations

• Adjacency list — adj[u] is the list of u's neighbours. Space O(V + E); iterating a vertex's neighbours is fast. The default for sparse graphs.
• Adjacency matrix — m[u][v] = 1 (or the weight) if an edge exists. Space O(V²); edge lookup is O(1) but iterating neighbours is O(V). Good for dense graphs or when you need instant edge tests.
• Edge list — just a list of (u, v, w). Compact; ideal for algorithms that sort edges (like Kruskal).

int V, E;
vector<vector<int>> adj(V);          // adjacency list
for (auto [u, v] : edges) {
    adj[u].push_back(v);
    adj[v].push_back(u);             // omit for a directed graph
}