Graphs and their representations
Graphs model relationships: roads between cities, links between web pages, friendships, dependencies between tasks. Choosing how to store a graph shapes the speed of every algorithm that uses it.
Graph vocabulary
A graph G = (V, E) has a set of vertices (nodes) V and edges E connecting pairs of vertices. In an undirected graph, edges have no direction, like friendships; in a directed graph (digraph), edges point from one vertex to another, like web links. Weighted graphs attach a number, such as distance or cost, to each edge. We write n = |V| and m = |E|.
Degree, paths, and cycles
The degree of a vertex is its number of incident edges; in digraphs we distinguish in-degree and out-degree. A path is a sequence of vertices joined by edges; a cycle is a path returning to its start. A graph is connected if every pair of vertices has a path between them. The sum of all degrees in an undirected graph equals 2m, since each edge contributes to two vertices.
Special graphs
A tree is a connected graph with no cycles and exactly n - 1 edges. A directed acyclic graph (DAG) has directed edges and no directed cycles, modelling prerequisites and build dependencies. A bipartite graph splits vertices into two groups with edges only between groups, such as job applicants and jobs. A complete graph connects every pair, with n(n - 1)/2 edges.
Dense and sparse graphs
A simple undirected graph has at most n(n - 1)/2 edges. Graphs with m close to n^2 are dense; those with m closer to n, such as road networks and most social networks, are sparse. Many real graphs are very sparse: each web page links to a handful of others out of billions. This distinction decides which representation is best.
Adjacency matrix
An adjacency matrix is an n x n table where entry (i, j) is 1, or the weight, if there is an edge from i to j. Checking whether an edge exists is O(1), but the matrix takes O(n^2) space even for sparse graphs, and listing a vertex's neighbours takes O(n). Matrices suit small or dense graphs and algorithms based on matrix arithmetic.
Adjacency list
An adjacency list stores, for each vertex, a list of its neighbours (and weights). It uses O(n + m) space and lists a vertex's neighbours in time proportional to its degree, which makes graph traversals O(n + m). Checking for a specific edge takes O(degree), or O(1) on average if neighbours are kept in hash sets. Adjacency lists are the default for sparse graphs.
Edge lists and implicit graphs
An edge list simply stores all edges as pairs or triples, which suits algorithms that process edges in sorted order, such as Kruskal's minimum spanning tree algorithm. Some graphs are implicit: never stored, but generated on demand, such as the states of a puzzle where each move leads to a neighbouring state, or a grid map where each cell's neighbours are the adjacent cells.
Worked example
A social network with 1,000,000 users, each with about 200 friends: m is about 100,000,000 undirected edges. An adjacency matrix would need 10^12 entries: about 125 gigabytes even at one bit per entry, and far more with integers, almost all of them zeros. Adjacency lists store about 2m = 200,000,000 neighbour entries, roughly 1.6 gigabytes with 8-byte IDs: the only practical choice.
Key takeaways
A graph has vertices and edges, which may be directed and weighted; n = |V|, m = |E|. Degrees sum to 2m in undirected graphs. Trees have n - 1 edges and no cycles; DAGs have no directed cycles; bipartite graphs split into two sides. Dense graphs have m near n^2, sparse ones far fewer. Adjacency matrices give O(1) edge checks but O(n^2) space; adjacency lists use O(n + m) space and enable O(n + m) traversals. Edge lists and implicit graphs suit particular algorithms and huge state spaces.
Flashcard
Vertices connected by edges
Check your understanding
For a sparse graph with a million vertices, why is an adjacency list usually preferred over an adjacency matrix?