Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

The Python Journey - Graphs and Graph Theory


Useful Links

Graph Theory (Wikipedia)Graph Theory 101 (Harvard Uni)NetworkX

Page Contents

Graph Theory Overview

Here we’re talking about very specific definitions of a graph. Not the kind of graph where you plot points on x and y axes, but rather: an abstract model that represents a set of vertices (also called nodes or points), linked together by edges (also called links or lines).

Graph Types

Graphs can be categorised as:

We can summarise like this:

Graph Type Description E.g.
Unweighted Undirected (“graph”) An associated set of unordered nodes. Undirected unweighted
Unweighted Directed (“digraph”) An associated set of ordered nodes. It is the direction of the edges (arrows) that dictates order. Directed unweighted
Weighted Undirected (“weighted graph”) The edges have magnitude, and this magnitude is important. E.g. the weight could represent distance, or cost. Undirected weighted
Weighted Directed (“weighted digraph”) The edges have both magnitude and direction. It is possible for A -> B to have a different magnitude from B -> A. Directed weighted

It’s worth noting that undirected graphs can be either unweighted and weighted; and directed graphs can be either unweighted or weightd.


A tree is an acyclic graph - i.e. one in which no loops are created - where vertices are connected by exactly one path.


However, as the image shows, a given node can appear more than once in a tree.

Adjacency Lists

It’s generally a good idea to store graphs using adjacency lists. I.e. a map that links a given vertex to all the vertices it is directly connected to.

Consider the undirected graph above, where:

Imagine that we’re not given the overall graph, but we’re instead only provided with individual edges. In this case, we can build the graph using an adjacency list as follows:

from collections import defaultdict

edges = set() # store edge edge as a tuple of (node_a, node_b)

# Imagine we're only provided with the edges.
edges.add((1, 2))
edges.add((1, 5))
edges.add((2, 1))
edges.add((2, 3))
edges.add((3, 2))
edges.add((3, 4))
edges.add((4, 3))
edges.add((4, 5))
edges.add((4, 6))
edges.add((5, 1))
edges.add((5, 2))
edges.add((5, 4))
edges.add((6, 4))

# Now we build the adjacency map
node_map = defaultdict(set) # Use a set in order to filter out duplicate connections
for x, y in edges:
    node_map[x].add(y)  # a list of vertices that link to x
    node_map[y].add(x)  # a list of vertices that link to y

for vertex, connections in node_map.items():
    print(f"{vertex}: {connections}")


1: {2, 5}
2: {1, 3, 5}
3: {2, 4}
4: {3, 5, 6}
5: {1, 2, 4}
6: {4}