Representing graphs

A railway map, a road network, friends on a website, web pages and their links, tasks that must wait for other tasks: all of these are things joined to other things. A graph is the general picture of that. This station shows how to store a graph, and then how to search one. Leg D builds everything else on it.

Vertices and edges

A graph is a set of vertices (also called nodes: the stations) and a set of edges (the lines). Each edge joins two vertices. Two vertices joined by an edge are neighbours.

• In an undirected graph an edge goes both ways: a line between A and B can be used from A to B and from B to A. We write it A–B.
• In a directed graph each edge goes one way, from its start to its end, written A → B. One-way streets, links between web pages and “task A must come before task B” are directed.
• The degree of a vertex is the number of edges at it. In a directed graph, the out-degree counts edges going out and the in-degree counts edges coming in.
• A path is a sequence of vertices where each one is joined to the next. A cycle is a path that comes back to where it started. A graph is connected if there is a path between every two vertices.

We write V for the number of vertices and E for the number of edges. Cost is usually given in both, as in O(V + E): “time that grows with the number of vertices plus the number of edges”. A graph with no repeated edges and no edge from a vertex to itself has at most V(V − 1)/2 undirected edges, so E can be anything from 0 to about V²/2 (half of V times V). A graph with few edges (a road map, where E is a small multiple of V) is called sparse; one with close to V² edges is dense.

The reason: every edge has two ends, and each end adds 1 to the degree of one vertex. So the total is exactly twice the number of edges. One consequence is that the number of vertices with an odd degree is always even.

The adjacency matrix

Number the vertices 0 to V − 1. The adjacency matrix is a V × V table where row u, column v holds 1 if there is an edge from u to v, and 0 if not. For an undirected graph the table is symmetric: it reads the same when flipped across its diagonal, because every edge is entered twice, at (u, v) and at (v, u).

• “Is u joined to v?” is one look-up: O(1).
• Listing the neighbours of u means reading the whole row: O(V), even if u has only two neighbours.
• The memory is V² entries, whatever the number of edges. 100,000 vertices need 10¹⁰ entries (ten thousand million), which no laptop holds.

So the matrix suits small or dense graphs. It also allows arithmetic on the whole graph: entry (u, v) of the matrix to the power k (k copies of the matrix multiplied together) counts the walks of exactly k edges from u to v (a walk is a path that may repeat vertices). MATH-3 computes such powers quickly. Floyd–Warshall (PATH-5) also works on a matrix.

Adjacency lists

Adjacency lists keep, for each vertex, a list of its neighbours. An undirected edge u–v appears twice, once in u’s list and once in v’s; a directed edge u → v appears once, in u’s list. Step through the figure to see the same graph built each way.

Building adjacency lists from a list of edges takes one pass:

def build(n, edges, directed=False):
    adj = [[] for _ in range(n)]       # not [[]] * n: that is one list, n times
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

• The memory is O(V + E): one list per vertex, and one or two entries per edge.
• Listing the neighbours of u takes time in proportion to its degree, which is what a search needs.
• “Is u joined to v?” means scanning u’s list: O(degree of u). If that question is common, keep each vertex’s neighbours in a set instead of a list. A set answers it in O(1) on average (HASH), at the cost of more memory and of losing the order of the neighbours.

Nearly every algorithm in Leg D uses adjacency lists, because a search touches each edge only a few times and the lists give exactly those edges.

The edge list

The simplest form is just the list of edges, [(u, v), …]: the way graphs usually arrive in a file or a problem. It uses the least memory, but answering anything about one vertex means reading the whole list. Algorithms that look at every edge in some order use it directly: Kruskal’s method sorts the edges by weight (SPAN-2), and Bellman–Ford goes over all edges again and again (PATH-4).

Graphs in Python

When the vertices are numbered 0 to n − 1, a list of lists is the fastest choice. When they have names (station codes, words), use a dict whose values are lists or sets:

from collections import defaultdict

lines = [("NDLS", "AGC"), ("AGC", "GWL"), ("NDLS", "JP")]
adj = defaultdict(set)            # a missing key starts as an empty set
for a, b in lines:
    adj[a].add(b)
    adj[b].add(a)
print(sorted(adj["NDLS"]))        # ['AGC', 'JP']

Another way is to give each name a number once, and then use lists:

names = ["NDLS", "AGC", "GWL", "JP"]
index = {name: i for i, name in enumerate(names)}
adj = [[] for _ in names]
for a, b in lines:
    adj[index[a]].append(index[b])
    adj[index[b]].append(index[a])

That is faster for big graphs, and the numbers let you keep facts about each vertex (a distance, a parent) in plain lists.

Now try GRPH-P1, Is there a direct line?