Python Arena
Start learning
Step 1 of 6

Graphs and adjacency lists

Which of your friends' friends haven't you met yet? Can you fly from Lisbon to Osaka with one change of plane? Which of a program's files must Python load before main.py can run? Each question is about some things and the links between pairs of them. Put that way, it is a graph: a set of vertices (the things, also called nodes) and a set of edges, each joining two vertices. You have met one kind of graph already, the tree, where every node but the root hangs from exactly one parent. A graph in general has no such rules: it can have loops, several routes between the same two vertices, and pieces with no link between them at all. Interview questions about mazes, flights, schedules and groups of people are very often graph questions in disguise.

Links come in kinds. A flight has a price and a road a driving time: a number on an edge is its weight. The fifth step of this module uses weights; until then, every edge counts as one step. And a link may or may not work both ways. If Ana is Ben's cousin, Ben is Ana's cousin too, so the edge is undirected. But Ana can follow Ben online without Ben following back, and a file can import another without being imported by it: those edges are directed, from a to b.

From a list of edges to an adjacency list

A graph often arrives as a list of edges, each a pair of vertices. But the question that graph algorithms ask over and over is "where can I go from v in one step?": the neighbors of v. Scanning the whole list of edges for every such question costs O(E) each time, for E edges. An adjacency list answers at once. It is a dict that maps each vertex to the list of its neighbors:

roads = [("Rome", "Naples"), ("Florence", "Rome"), ("Naples", "Bari"), ("Bologna", "Florence"), ("Rome", "Bari"), ("Cagliari", "Sassari")]

graph = {}
for a, b in roads:
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)

for city in graph:
    print(city, len(graph[city]), graph[city])
Output
Rome 3 ['Naples', 'Florence', 'Bari']
Naples 2 ['Rome', 'Bari']
Florence 2 ['Rome', 'Bologna']
Bari 2 ['Naples', 'Rome']
Bologna 1 ['Florence']
Cagliari 1 ['Sassari']
Sassari 1 ['Cagliari']

A road is an undirected edge, so it goes into two lists: Naples is in Rome's list, and Rome is in Naples's. The number of neighbors of a vertex is its degree: Rome's is 3. Each edge adds 1 to the degree of both its ends, so the degrees add up to 2E, here 12 for 6 roads. Cagliari and Sassari are on the island of Sardinia, with a road only to each other: a graph can come in separate pieces, and no road leads from Rome to Cagliari.

The two if lines give every vertex a list of its own the first time it shows up, as a or as b. Without them, the first road to a new city stops with a KeyError. (collections.defaultdict(list) does the same for you: a missing key gets an empty list the first time it's used.) When the vertices are numbered 0 to n - 1, a list of lists works just as well: graph[v] is the list of v's neighbors.

Directed graphs: out and in

A directed edge goes into one list only, the list of the vertex it leaves from. That list's length is the vertex's out-degree. The in-degree, the number of edges coming in, needs a count of its own, made in the same single pass over the edges:

follows = [(0, 1), (0, 2), (1, 2), (2, 0), (3, 2)]
n = 4

following = [[] for _ in range(n)]
followers = [0] * n
for a, b in follows:
    following[a].append(b)
    followers[b] += 1

print(following)
print([len(people) for people in following])
print(followers)
Output
[[1, 2], [2], [0], [2]]
[2, 1, 1, 1]
[1, 1, 3, 0]

Person 2 has three followers and follows one person, and nobody follows 3. Counting each person's followers with a scan of all the edges per person gives the same numbers, but costs O(V·E) instead of O(V + E).

A Python trap: [[]] * n

To make n empty lists, [[]] * n looks right. But * repeats a reference to one list n times, so every vertex shares the same list:

In the Python interpreter
>>> graph = [[]] * 3
>>> graph[0].append(1)
>>> graph
[[1], [1], [1]]

Make each list separately: [[] for _ in range(n)].

What it costs

An adjacency list takes O(V + E) memory: a list for each vertex, plus an entry for each directed edge (two for an undirected one). Going through the neighbors of v takes O(deg v), and through the neighbors of every vertex O(V + E). That's what the searches of the next steps do.

"Is there an edge from a to b?" is b in graph[a]: O(deg a) with a list. With a set of neighbors instead, it's O(1) on average, the trade of memory for speed from the step on sets and dicts in the module on complexity. (Sets of strings have no fixed order, so sort them before you print them.) The other classic layout, an adjacency matrix, is a V by V table of True and False, a list of V lists in Python. It answers in O(1) too, but takes O(V²) memory, whatever the number of edges. Take a city's street map: 50,000 crossings, each joined to about 4 others. Its adjacency lists hold about 200,000 entries. Its matrix has 2.5 billion cells, and since every item of a Python list is an 8-byte reference, that's 20 GB, almost all of it False. Graphs like this one, with far fewer than V² edges, are called sparse, and most real graphs are, so adjacency lists are the usual choice.

Your task

Challenge 1 of 3

build makes the adjacency list of an undirected graph whose vertices are numbered 0 to n - 1. Fill in the blanks: the edge's way back, and each vertex's degree. The program should print:

[[1, 2], [0, 2], [0, 1, 3], [2], []]
[2, 2, 3, 1, 0]

Challenge 2

At a party of n people, numbered 0 to n - 1, knows lists pairs (a, b): person a knows person b. A celebrity is known by everyone else and knows nobody. Write find_celebrity(n, knows) that returns the celebrity's number, or None when there is none. No pair appears twice, and nobody is paired with themselves.

In graph words, knows is a directed graph, and the celebrity has an in-degree of n - 1 and an out-degree of 0. Count both in one pass over the pairs: the hidden tests have 100,000 people and over 130,000 pairs, and counting each person's pairs with a scan of the whole list is O(n·E), billions of steps.

For example, this program:

print(find_celebrity(4, [(0, 2), (1, 2), (3, 2), (0, 1), (3, 0)]))
print(find_celebrity(3, [(0, 1), (1, 0), (2, 1)]))

prints:

2
None

Challenge 3

On a social network, follows lists pairs (a, b): person a follows person b. Write mutual_pairs(follows) that returns how many pairs of people follow each other. Each such pair counts once. The people are numbers, no pair appears twice in the list, and nobody follows themselves.

(b, a) in follows would answer "does b follow a back?", but on a list it's a scan, O(E) for each of the E follows: the hidden test has 80,000 follows. Put each person's follows in a set first, so the check is O(1) on average.

For example, here 1 and 2 follow each other, and so do 3 and 4. So this call:

print(mutual_pairs([(1, 2), (2, 1), (1, 3), (3, 4), (4, 3), (2, 3)]))

prints:

2
Next: Breadth-first search