Skip to content
LumenaryAcademy
Core 70 min

Graphs: representation and traversal

Roads, dependencies and friendships — how to store a network, and the two basic ways to explore one.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Networks everywhere

Many problems are secretly about things and the connections between them.

  • A city's streets: intersections joined by road segments. Can an ambulance get from the station to this address? What is the route with the fewest turns?
  • A software project: packages that depend on other packages. In what order must they be built? Is there a circular dependency?
  • A social network: people and friendships. Who is a friend of a friend? How many separate communities are there?
  • This very course: lessons and the prerequisites between them. Is there an order in which every lesson comes after all the lessons it builds on?
  • A school timetable: exams that share students cannot be at the same time. Can all the exams fit into two sessions?

Each is a graph: a set of vertices (also called nodes) and a set of edges joining pairs of them. Once a problem is drawn as a graph, a small toolbox of algorithms answers a remarkable range of questions. This lesson builds the toolbox: how to store a graph, and the two fundamental ways to explore one, breadth-first and depth-first. Later lessons add weights (Shortest paths, Minimum spanning trees). The mathematics of graphs has its own home in Lumenary Math.

DefinitionsH

Definitions

Definition— graph

A graph G=(V,E)G = (V, E) is a set VV of vertices and a set EE of edges. In an undirected graph an edge {u,v}\{u, v\} joins uu and vv symmetrically (friendship); in a directed graph an edge (u,v)(u, v) goes from uu to vv (a one-way street, "depends on"). A weighted graph attaches a number to each edge (a length, a cost, a travel time). We write n=∣V∣n = |V| and m=∣E∣m = |E|.

Definition— degree

The neighbours of vv are the vertices joined to it by an edge, and its degree is the number of edges at vv. In a directed graph, the in-degree and out-degree count incoming and outgoing edges. In an undirected graph the degrees add up to 2m2m, since each edge has two ends.

Definition— paths, cycles and connectivity

A path is a sequence of vertices in which each consecutive pair is joined by an edge (following edge directions, if any); its length is its number of edges. A cycle is a path of length at least 1 that returns to its start without repeating an edge (in an undirected graph, of length at least 3). An undirected graph is connected if every pair of vertices is joined by a path; its maximal connected pieces are its connected components. A directed graph with no cycles is a DAG (directed acyclic graph).

Definition— sparse and dense

A graph can have up to about n2n^2 edges. It is called sparse when mm is closer to nn than to n2n^2 (road networks, most real networks) and dense when mm is a sizeable fraction of n2n^2.

ExplanationH

Storing a graph

There are two classic representations.

An adjacency matrix is an n×nn \times n table with a 1 (or the edge's weight) in row uu, column vv when there is an edge from uu to vv. Checking for a particular edge is one array access, but the matrix takes n2n^2 cells however few edges there are, and listing the neighbours of a vertex means scanning a whole row.

An adjacency list stores, for each vertex, a list of its neighbours. In Python the natural form is a dict mapping each vertex to a list (or set) of neighbours. It takes space proportional to n+mn + m, and listing the neighbours of vv costs O(deg⁡v)O(\deg v), which is exactly what traversals need.

OperationAdjacency matrixAdjacency list (dict of lists)
SpaceΘ(n2)\Theta(n^2)Θ(n+m)\Theta(n + m)
Is there an edge u→vu \to v?O(1)O(1)O(deg⁡u)O(\deg u), or O(1)O(1) expected with sets
List the neighbours of uuΘ(n)\Theta(n)Θ(deg⁡u)\Theta(\deg u)
Visit every edgeΘ(n2)\Theta(n^2)Θ(n+m)\Theta(n + m)

The deciding fact is that real graphs are sparse. The road network of a large country has tens of millions of intersections, each with only two to four roads. An adjacency matrix would need around 101410^{14} cells, almost all zero; adjacency lists need a few hundred megabytes. Matrices make sense for small or dense graphs, and when you want to treat the graph with linear algebra or fill in a table for every pair of vertices, as the all-pairs algorithm in Shortest paths does. High-performance libraries such as scipy.sparse.csgraph store adjacency lists in compressed sparse row form: one array holding all neighbour lists back to back, and a second array saying where each vertex's list starts. It is an adjacency list with the locality of an array.

ABCDEFGH
The example graph used in this lesson: eight vertices and seven undirected edges, forming two connected components. The square A, B, D, C is a cycle of length 4.
ExplanationH

Breadth-first search

Breadth-first search (BFS) explores a graph in rings around a starting vertex ss: first ss, then all its neighbours, then all their undiscovered neighbours, and so on. The tool that produces this order is a queue (from the lesson on queues). Each vertex records dist, the number of edges on the path by which it was discovered, and parent, the vertex it was discovered from.

text
BFS(G, s):
    dist[s] = 0; parent[s] = None; queue = [s]
    while queue is not empty:
        u = dequeue()
        for each neighbour v of u:
            if v has not been discovered:
                dist[v] = dist[u] + 1; parent[v] = u; enqueue(v)

Theorem— BFS finds shortest paths

In an unweighted graph (directed or undirected), BFS from ss discovers exactly the vertices reachable from ss, and for each of them sets dist[v] to δ(s,v)\delta(s, v), the least number of edges on any path from ss to vv. Following parent pointers from vv back to ss traces a shortest path. BFS runs in O(n+m)O(n + m) time.

Proof

First, dist[v] is always the length of an actual path (the one traced by the parent pointers), so dist[v] ≥δ(s,v)\ge \delta(s, v).

Next, the queue always holds vertices in non-decreasing order of dist, with the last at most 1 more than the first. This holds initially, and each step removes the front uu and appends vertices with dist[u] + 1, which keeps it true. So vertices leave the queue in non-decreasing order of dist.

Now prove dist[v] =δ(s,v)= \delta(s, v) by induction on k=δ(s,v)k = \delta(s, v). For k=0k = 0, v=sv = s. For k>0k > 0, a shortest path to vv ends with an edge (u,v)(u, v) where δ(s,u)=k−1\delta(s, u) = k - 1; by induction uu is discovered with dist[u] =k−1= k - 1, so it is eventually dequeued. When that happens, either vv is undiscovered, and it gets dist[v] =k= k, or vv was discovered earlier from some vertex ww dequeued before uu, so dist[w] ≤\le dist[u] =k−1= k-1 and dist[v] ≤k\le k. Combined with dist[v] ≥k\ge k, we get equality. Unreachable vertices are never discovered, since every discovered vertex has a path from ss.

Each vertex is enqueued at most once (we mark it when it is discovered, not when it is processed), and each vertex's neighbour list is scanned once, when it is dequeued. That is O(n)O(n) queue operations plus O(m)O(m) neighbour checks.

∎

Running BFS from every vertex not yet discovered splits an undirected graph into its connected components, again in O(n+m)O(n + m) total. ("Is in the same component as" is an equivalence relation, and the components are its classes; see equivalence relations.)

python
from collections import deque

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E"), ("E", "F"), ("G", "H")]
graph = {v: [] for v in "ABCDEFGH"}             # adjacency list: vertex -> neighbours
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)                           # undirected: store both directions

def bfs(graph, s):
    dist, parent = {s: 0}, {s: None}
    queue = deque([s])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in dist:                    # mark when discovered, so each vertex is queued once
                dist[v], parent[v] = dist[u] + 1, u
                queue.append(v)
    return dist, parent

def path_to(parent, v):
    path = []
    while v is not None:
        path.append(v)
        v = parent[v]
    return path[::-1]

dist, parent = bfs(graph, "A")
print("distances from A:", dist)
print("a shortest path A to F:", " -> ".join(path_to(parent, "F")))
print("H reachable from A?", "H" in dist)

def components(graph):
    seen, comps = set(), []
    for s in graph:
        if s not in seen:
            dist, _ = bfs(graph, s)
            seen.update(dist)
            comps.append(sorted(dist))
    return comps
print("components:", components(graph))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

BFS is the right tool whenever every step costs the same: the fewest transfers on a metro map, the fewest moves to solve a puzzle, the degrees of separation between two people, a web crawler that visits pages nearest the start first. When steps have different costs, BFS's guarantee no longer holds, and Dijkstra's algorithm, a BFS with a priority queue instead of a plain queue, takes over.

ExplanationH

Depth-first search

Depth-first search (DFS) explores like a person in a maze with a ball of thread: keep going forward to an unvisited place while you can; when you are stuck, back up to the last place with an unexplored turning. Recursion expresses this perfectly, since the call stack remembers the way back:

python
def dfs(graph, u, visited):
    visited.add(u)
    for v in graph[u]:
        if v not in visited:
            dfs(graph, v, visited)

DFS also visits every reachable vertex in O(n+m)O(n + m) time, and repeated DFS finds connected components just as BFS does. What DFS adds is structure in time. It is useful to colour each vertex: white before it is discovered, grey while its call is still running (it is on the stack), and black once its call has finished. At any moment the grey vertices form a path from the start to the current vertex.

Theorem— Cycle detection in directed graphs

A directed graph has a cycle if and only if some depth-first search over it (restarted from every white vertex) finds an edge (u,v)(u, v) to a vertex vv that is grey, called a back edge.

Proof

If (u,v)(u, v) is found while vv is grey, then vv is on the current path from the start to uu, so there is a path v⇝uv \leadsto u; together with the edge u→vu \to v it forms a cycle.

Conversely, suppose there is a cycle, and let vv be the first vertex of the cycle that DFS discovers. At that moment every other vertex of the cycle is white, and each can be reached from vv along the cycle through white vertices. DFS from vv cannot finish until it has explored everything reachable from vv through white vertices, so it reaches uu, the vertex just before vv on the cycle, while vv is still grey. Examining the edge u→vu \to v then finds vv grey.

∎

For undirected graphs the test is simpler: there is a cycle exactly when DFS (or BFS) meets an already-visited neighbour other than the vertex it came from.

In Python, recursion has a practical limit: the default recursion limit is about 1000, and a DFS down a path of 100,000 vertices would crash with RecursionError. Production code uses an explicit stack. A careful iterative version keeps, for each grey vertex, an iterator over its remaining neighbours, which reproduces the recursive order exactly and makes it possible to know when a vertex finishes.

python
def find_cycle(graph):
    """Return a list of vertices forming a directed cycle, or None. Iterative DFS with colours."""
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {v: WHITE for v in graph}
    parent = {}
    for start in graph:
        if colour[start] != WHITE:
            continue
        colour[start] = GREY
        stack = [(start, iter(graph[start]))]       # each grey vertex with its unexplored neighbours
        while stack:
            u, neighbours = stack[-1]
            v = next(neighbours, None)
            if v is None:                           # u has no more neighbours: it finishes
                colour[u] = BLACK
                stack.pop()
            elif colour[v] == WHITE:
                colour[v], parent[v] = GREY, u
                stack.append((v, iter(graph[v])))
            elif colour[v] == GREY:                 # back edge u -> v: walk parents from u to v
                cycle = [u]
                while cycle[-1] != v:
                    cycle.append(parent[cycle[-1]])
                return cycle[::-1]
    return None

# "x depends on y" is drawn as an edge x -> y.
deps = {
    "app":     ["web", "auth"],
    "web":     ["http", "templates"],
    "auth":    ["crypto", "db"],
    "db":      ["config"],
    "http":    ["config"],
    "templates": [],
    "crypto":  [],
    "config":  [],
}
print("cycle:", find_cycle(deps))
deps["config"] = ["auth"]                           # someone makes config import auth...
cycle = find_cycle(deps)
print("cycle:", " -> ".join(cycle + cycle[:1]))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

DFS is the engine inside many deeper algorithms: finding the bridges and articulation points whose removal disconnects a network, splitting a directed graph into strongly connected components (Tarjan's algorithm), generating mazes, and solving puzzles by backtracking (Recursion). Hopcroft and Tarjan's work in the early 1970s showed how much a single linear-time DFS can reveal.

ExplanationH

Topological sort

A topological order of a directed graph lists its vertices so that every edge goes from an earlier vertex to a later one. If edges mean "must happen before", a topological order is a valid schedule: a build order for a project, an installation order for packages, a sequence for a syllabus, an order in which a spreadsheet can recalculate its cells.

Theorem— Topological orders exist exactly for DAGs

A directed graph has a topological order if and only if it has no cycle.

Proof

If there is a cycle v1→v2→⋯→vk→v1v_1 \to v_2 \to \cdots \to v_k \to v_1, each viv_i would have to come before vi+1v_{i+1} and vkv_k before v1v_1, which is impossible. Conversely, every finite DAG has a vertex with in-degree 0: otherwise, start anywhere and keep walking backwards along incoming edges; after nn steps some vertex repeats, which gives a cycle. Put such a vertex first, delete it, and repeat on the remaining graph, which is still a DAG. This produces a topological order.

∎

The proof is an algorithm, published by A. B. Kahn in 1962. Kahn's algorithm keeps each vertex's in-degree and a queue of vertices whose in-degree is 0. It repeatedly removes a vertex from the queue, appends it to the output, and decrements the in-degrees of its out-neighbours, adding any that drop to 0. If the output ends up shorter than nn, the vertices left over are on or behind a cycle: Kahn's algorithm detects cycles for free. It runs in O(n+m)O(n + m). An alternative uses DFS: the order in which vertices finish, reversed, is a topological order, because when uu finishes, everything reachable from uu has already finished.

Python's standard library has this built in as graphlib.TopologicalSorter, which raises CycleError on a cycle and can also hand out tasks in parallel batches as their prerequisites complete, the way a build system such as Make or Bazel runs independent steps at once.

python
from collections import deque
from graphlib import TopologicalSorter, CycleError

# Each step of making jollof rice, with the steps that must come before it.
before = {
    "wash rice": [],
    "chop onions": [],
    "blend peppers and tomatoes": [],
    "fry onions": ["chop onions"],
    "cook down the sauce": ["fry onions", "blend peppers and tomatoes"],
    "add stock and rice": ["cook down the sauce", "wash rice"],
    "steam until done": ["add stock and rice"],
}

def kahn(before):
    after = {v: [] for v in before}                 # edge u -> v when u must come before v
    indegree = {v: len(prereqs) for v, prereqs in before.items()}
    for v, prereqs in before.items():
        for u in prereqs:
            after[u].append(v)
    ready = deque(v for v in before if indegree[v] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in after[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                ready.append(v)
    if len(order) < len(before):
        raise ValueError(f"cycle among: {sorted(set(before) - set(order))}")
    return order

order = kahn(before)
print(*order, sep="\n")
position = {v: i for i, v in enumerate(order)}
assert all(position[u] < position[v] for v, ps in before.items() for u in ps)

print("graphlib:", list(TopologicalSorter(before).static_order())[:3], "...")
before["wash rice"] = ["steam until done"]          # a nonsensical requirement creates a cycle
try:
    kahn(before)
except ValueError as e:
    print("kahn:", e)
try:
    list(TopologicalSorter(before).static_order())
except CycleError as e:
    print("graphlib found a cycle:", e.args[1])
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

Bipartite graphs

A graph is bipartite if its vertices can be coloured with two colours so that every edge joins vertices of different colours. Exam timetabling with two sessions, assigning two shifts so that people who clash are never together, checking that a "who reviews whom" graph splits into authors and reviewers: all ask whether a graph is bipartite.

BFS answers it. Colour the start vertex red; BFS colours each newly discovered vertex the opposite colour of its parent, so vertices at even distance are red and those at odd distance are blue. Then check every edge. If no edge joins two vertices of the same colour, the colouring proves the graph bipartite. If one does, the graph is not, and there is a witness:

Theorem— König's characterisation

A graph is bipartite if and only if it has no cycle of odd length.

Proof

A cycle in a 2-coloured graph alternates colours, so it must have even length; hence a bipartite graph has no odd cycle. Conversely, suppose BFS finds an edge {u,v}\{u, v\} with both ends the same colour, so dist[u] and dist[v] have the same parity. Follow parent pointers from uu and from vv back to their nearest common ancestor ww. The two tree paths and the edge {u,v}\{u, v\} form a cycle of length (dist[u]−dist[w])+(dist[v]−dist[w])+1(\text{dist}[u] - \text{dist}[w]) + (\text{dist}[v] - \text{dist}[w]) + 1, which is odd because dist[u] + dist[v] is even. So if there is no odd cycle, BFS never finds such an edge, and its colouring is valid (in each component).

∎

You will implement this in the exercises. Bipartite graphs matter far beyond colouring: matching students to projects, job seekers to openings, or kidneys to compatible donors are all matching problems on bipartite graphs, solved with algorithms that build directly on BFS and DFS.

ExplanationH

Real graphs, and the libraries that handle them

Real graphs come in recognisable families, and their shapes decide which tools work.

  • Road networks are sparse (average degree below 3), almost planar, and huge: a continent's road graph built from OpenStreetMap data has tens to hundreds of millions of vertices. Their edges carry lengths and travel times, so routing needs weighted shortest paths with heavy preprocessing (Shortest paths).
  • Dependency graphs (packages, build targets, spreadsheet cells, data pipelines) should be DAGs, and topological sorting is their daily bread. A cycle is a bug, and good tools report it with the cycle itself, as find_cycle does above.
  • Social and web graphs have billions of vertices, a few with enormous degree (celebrities, popular sites), and surprisingly short paths between most pairs. They do not fit on one machine; systems in the style of Google's Pregel (2010) run graph algorithms as rounds of messages between vertices spread across a cluster, and BFS-like "frontier" computations are their staple.

For everyday Python work, NetworkX offers hundreds of graph algorithms on dict-of-dicts graphs and is ideal for exploration; scipy.sparse.csgraph runs BFS, DFS, components and shortest paths in compiled code on compressed sparse matrices; and graphlib covers topological sorting without any dependency at all.

Common misconceptionsH

Common misconceptions

Misconception

"DFS also finds shortest paths." DFS finds a path, often a long and winding one. Only BFS (for unweighted graphs) guarantees the fewest edges, because it finishes each distance ring before starting the next.

Misconception

"Mark a vertex visited when you take it out of the queue." Then a vertex can be added to the queue many times, once from each neighbour that sees it before it is processed. The distances still come out right, but the queue can grow to O(m)O(m) entries and the work multiplies. Mark vertices when they are discovered.

Misconception

"Seeing a visited vertex means there is a cycle." In a directed graph, reaching a black (finished) vertex is harmless: two different routes can lead to the same dependency, as config is reached from both db and http above. Only an edge to a grey vertex, one still on the current path, closes a cycle.

Misconception

"An adjacency matrix is simpler, so use it." For n=106n = 10^6 vertices a matrix has 101210^{12} cells, more memory than most machines have, and a BFS over it costs Θ(n2)\Theta(n^2) even if each vertex has only three neighbours. Use adjacency lists unless the graph is small or dense.

Exercises

Exercises

1. Graphs: representation and traversal

Warm-upHuman

A routing service stores the road network of a country with 20 million intersections; each intersection has between 1 and 5 roads. Which representation should it use for running BFS and similar traversals?

Choose one

2. Graphs: representation and traversal

Warm-upHuman

An undirected graph (no loops, no repeated edges) has six vertices with degrees 3,3,2,2,2,43, 3, 2, 2, 2, 4. How many edges does it have?

3. Graphs: representation and traversal

CoreHuman

An undirected graph has vertices 1 to 7 and edges

{1,2},{1,3},{2,4},{3,4},{4,5},{5,6},{3,7},{7,6}\{1,2\}, \{1,3\}, \{2,4\}, \{3,4\}, \{4,5\}, \{5,6\}, \{3,7\}, \{7,6\}.

BFS starts at vertex 1. What value of dist does it assign to vertex 6?

4. Graphs: representation and traversal

CoreHuman

A directed graph has five vertices and the edges a→ca \to c, b→cb \to c, c→dc \to d, c→ec \to e. How many different topological orders does it have?

5. Graphs: representation and traversal

CoreHuman

You run Kahn's algorithm on a directed graph with 10 vertices, and it outputs only 7 of them before the queue becomes empty. What can you conclude?

Choose one

6. Graphs: representation and traversal

CoreComputational

Write two_colouring(graph) for an undirected graph given as a dict that maps each vertex to a list of its neighbours (each edge appears in both lists). Return a dict mapping every vertex to 0 or 1 so that every edge joins vertices of different colours, or return None if no such colouring exists. The graph may have several connected components and isolated vertices. Use BFS, so that the whole run takes O(n+m)O(n + m).

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Graphs: representation and traversal

CoreComputational

A warehouse floor is a grid of strings: # is a shelf, . is free floor, S is the robot's start and G its goal. The robot moves one square up, down, left or right per step and cannot enter shelves or leave the grid.

Write fewest_steps(grid) that returns the minimum number of steps from S to G, or -1 if G cannot be reached. The graph is implicit: do not build an adjacency list, generate each square's neighbours when you need them.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources