Graphs

Data Structures in Practice

Chapter 8 · Graphs

A graph is a set of nodes (also called vertices) joined by edges. Unlike a tree (Data Structures in Practice 7) there is no root, nodes may have any number of neighbours, and loops are allowed. Road maps, friend networks, web links, flight routes and the dependencies between tasks are all graphs. Edges can be undirected (a two-way road) or directed (a one-way street), and they can carry a weight such as a distance or a cost.

What was run, and what was not

Every snippet below was run and the output shown is what it printed. No timings are quoted, because they differ between machines. Orders, paths and costs are exact, because they depend only on the data.

Storing a Graph

There are two classic layouts. An adjacency matrix is a grid with one row and one column per node; cell (a, b) says whether an edge joins them. An adjacency list keeps, for each node, only the list of its neighbours. In Python the natural adjacency list is a dict of lists.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
    "G": [],                  # a node with no edges
}
print(graph["C"])
print(len(graph), sum(len(v) for v in graph.values()) // 2)

def add_edge(g, a, b):
    g.setdefault(a, []).append(b)
    g.setdefault(b, []).append(a)

g = {}
for a, b in [("A", "B"), ("A", "C"), ("B", "D")]:
    add_edge(g, a, b)
print(g)
    

['A', 'D', 'E']
7 7
{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}
    

Seven nodes and seven edges. Because the graph is undirected, each edge is stored twice (once under each end), which is why the total length is halved to count edges. The picture the first dict describes:

    A --- B
    |     |
    C --- D        G (alone)
    |     |
    E --- F
    

	Adjacency list (dict of lists)	Adjacency matrix
Memory	One entry per node plus one per edge	One cell per pair of nodes
List a node's neighbours	Read its list directly	Scan a whole row
Is there an edge a-b?	Scan a's list (use sets of neighbours for constant time)	One lookup
Best for	Sparse graphs (few edges per node), which is most real graphs	Dense graphs, or small graphs where edge tests dominate

The memory row matters quickly. A chain of 1,000 nodes needs 1,000,000 matrix cells to hold only 1,998 stored list entries (each of its 999 edges stored twice). Unless the graph is nearly complete, use a dict.

Breadth-First Search

Breadth-first search (BFS) explores a graph in rings: the start, then everything one edge away, then everything two edges away. It is the queue-based walk from Data Structures in Practice 4 and the level-order walk from Data Structures in Practice 7, with one change: a graph can loop back, so you must remember which nodes have already been seen, in a set (Data Structures in Practice 3).

from collections import deque

def bfs_order(g, start):
    seen = {start}
    q = deque([start])
    order = []
    while q:
        cur = q.popleft()
        order.append(cur)
        for nb in g[cur]:
            if nb not in seen:
                seen.add(nb)          # mark when queued, not when visited
                q.append(nb)
    return order

print(bfs_order(graph, "A"))
    

['A', 'B', 'C', 'D', 'E', 'F']

G never appears, because no path leads to it from A. Marking a node as seen at the moment it is queued (rather than when it is taken off) stops it being queued twice. Each node and each edge is handled a fixed number of times, so the cost is proportional to nodes plus edges.

Why BFS finds shortest routes

Since BFS reaches nodes in order of distance, the first time it reaches a node is by a route with the fewest edges. To recover that route, store for each node where you came from (its parent) and walk backwards from the goal.

def shortest_path(g, start, goal):
    parent = {start: None}           # doubles as the "seen" set
    q = deque([start])
    while q:
        cur = q.popleft()
        if cur == goal:
            path = []
            while cur is not None:
                path.append(cur)
                cur = parent[cur]
            return path[::-1]
        for nb in g[cur]:
            if nb not in parent:
                parent[nb] = cur
                q.append(nb)
    return None                              # unreachable

print(shortest_path(graph, "A", "F"))
print(shortest_path(graph, "A", "G"))
    

['A', 'B', 'D', 'F']
None
    

Depth-First Search

Depth-first search (DFS) goes as far as it can along one route before backing up and trying another. It is the same loop as BFS with the queue swapped for a stack (Data Structures in Practice 4), so the most recently discovered node is explored next.

def dfs_order(g, start):
    seen, order, stack = set(), [], [start]
    while stack:
        cur = stack.pop()
        if cur in seen:
            continue
        seen.add(cur)
        order.append(cur)
        for nb in reversed(g[cur]):   # reversed so the first neighbour is tried first
            if nb not in seen:
                stack.append(nb)
    return order

print(dfs_order(graph, "A"))
    

['A', 'B', 'D', 'C', 'E', 'F']

From A it dived to B, then D, and only later came back to C. Both searches visit exactly the same set of nodes; only the order differs. This version uses an explicit stack, so it has no recursion limit (Data Structures in Practice 7 showed why that matters).

Question	Use	Why
Fewest edges from A to B?	BFS	Reaches nodes in order of distance
Can A reach B at all? What is connected to A?	Either	Both visit everything reachable
Find every separate cluster; detect loops	Usually DFS	Simple to write with a stack; see Exercise 1
Put tasks in a valid order, explore every option (puzzles, mazes)	DFS	Follows one possibility to its end before trying others
Memory on a wide graph	DFS	BFS holds a whole ring in its queue at once

Weighted Edges: Cheapest, Not Fewest

BFS counts edges, which is the right measure only when every edge costs the same. With weights, the route with the fewest edges is not always the cheapest. Dijkstra's algorithm fixes this with the heap from Data Structures in Practice 6: always expand the unfinished node with the smallest total cost so far. For weighted graphs, store (neighbour, weight) pairs.

import heapq

wgraph = {
    "A": [("B", 7), ("C", 2)],
    "B": [("D", 1)],
    "C": [("B", 3), ("D", 8), ("E", 5)],
    "D": [("F", 4)],
    "E": [("D", 2), ("F", 9)],
    "F": [],
}

def dijkstra(g, start):
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, cur = heapq.heappop(heap)
        if d > dist.get(cur, float("inf")):
            continue                 # a stale entry: a cheaper route was found since
        for nb, w in g[cur]:
            nd = d + w
            if nd < dist.get(nb, float("inf")):
                dist[nb] = nd
                heapq.heappush(heap, (nd, nb))
    return dist

print(dijkstra(wgraph, "A"))

# the same graph with weights ignored: BFS by edge count
plain = {k: [n for n, _ in v] for k, v in wgraph.items()}
print(shortest_path(plain, "A", "F"))
    

{'A': 0, 'B': 5, 'C': 2, 'D': 6, 'E': 7, 'F': 10}
['A', 'B', 'D', 'F']
    

The fewest-edges route A, B, D, F has three edges but costs 7 + 1 + 4 = 12. The cheapest route is A, C, B, D, F: four edges, but 2 + 3 + 1 + 4 = 10, as the costs printed above show. Notice B costs 5 via C, not 7 directly.

Dijkstra needs non-negative weights

The method assumes that once a node is the cheapest unfinished one, nothing can make it cheaper. A negative edge breaks that assumption and the answers can be wrong. If your costs can be negative, a different algorithm is needed. Exercise 3 makes the function reject them.

Picking a Representation in Python

Situation	Reach for
Most graphs, sparse, unweighted	`dict` of lists; BFS with `deque`
Need to test "is there an edge?" often	`dict` of `set`s
Weighted edges	`dict` of lists of `(neighbour, weight)`, or a dict of dicts
A grid (maze, map, board)	No graph at all: compute neighbours from coordinates (Exercise 2)
Very large or specialised graphs	A graph library; the standard library has none

Challenges

Exercise 1

Write components(g) for an undirected graph, returning a list of the separate connected groups (each a sorted list), and has_cycle(g), which says whether any group contains a loop. Remember that each undirected edge is stored twice, so walking back along the edge you came from must not count as a loop. Test with a graph that has three groups and no loop, then add one edge to create a loop, and check an empty graph.

📄 View solution

Exercise 2

A maze is a list of strings where # is a wall, S the start and G the goal. Write solve(grid) using BFS, moving up, down, left and right, that returns the shortest path as a list of (row, column) positions, or None if the goal cannot be reached. Do not build a dict of neighbours: compute them from the coordinates. Print the path length and draw the route on the maze with *. Test a blocked maze and a maze where the start is next to the goal.

📄 View solution

Exercise 3

Extend Dijkstra's algorithm into cheapest(g, start, goal), returning (cost, path) or None if the goal is unreachable. Track a parent for each node to rebuild the path, stop as soon as the goal is taken from the heap, and raise ValueError if any edge weight is negative. Test it on the chapter's weighted graph, with start equal to goal, with an unreachable goal, and with a negative weight.

📄 View solution

Quick Reference

Graph: nodes joined by edges; edges may be directed and may carry weights
Storage: a dict of lists (adjacency list) for sparse graphs; a matrix only for dense ones
Undirected: store each edge under both ends
BFS: queue (deque) plus a seen set; fewest edges first
DFS: the same loop with a stack; follows one route to its end
Cost: BFS and DFS are proportional to nodes plus edges
Paths: keep a parent for each node and walk back from the goal
Weights: Dijkstra with heapq; skip stale heap entries; no negative weights
Grids: compute neighbours from coordinates instead of building a graph

Coming next

Data Structures in Practice 9 builds a hash table by hand: collisions, load factor and a small working dictionary, so you can see why the dict you have used all course is so fast.