AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 19

Part 5 · Graphs · Chapter 19

Graphs and How to Represent Them

Friends, roads, web links, dependencies, chess positions. The most general structure in the course, and the one where choosing the representation is half the battle.

Reading

CLRS Ch. 22.1

Focus

Modelling

Cost

list O(V+E) · matrix O(V²)

Unlocks

Ch. 20–23

By the end of this chapter you can

Define a graph precisely and distinguish directed, weighted and cyclic variants
Convert between an adjacency list and an adjacency matrix, and state each one's costs
Choose a representation from the density of the graph and the operations needed
Model a real problem as a graph — naming the vertices and edges explicitly
Recognise when a problem is a graph problem even though nobody mentioned graphs

1Things, and connections between them

Drop every restriction a tree imposes and you get a graph. That generality is why almost everything can be modelled as one.

The friendship network

A tree had a root and a strict hierarchy. Friendship has neither. There is no “first person”, friendship can be mutual or one-sided (following, on social media), you can reach someone through several different chains, and A can know B who knows C who knows A.

None of that fits a tree. All of it fits a graph.

A graph is a set of vertices and a set of edges connecting pairs of them. That is the entire definition. Everything else is an option:

Option	Meaning	Example
Directed	Edges have a direction: A→B does not imply B→A	Twitter follows, web links, task dependencies
Undirected	Edges go both ways	Facebook friends, roads without one-way streets
Weighted	Each edge carries a number	Distance, cost, capacity, travel time
Cyclic	You can return to where you started	Most real networks
Acyclic	No cycles — a DAG if also directed	Dependencies, build order, git history
Connected	Every vertex is reachable from every other	One social network with no isolated groups
Dense / sparse	E close to V² / E close to V	Decides the representation, section 3

Some vocabulary that will be used without further comment from here on:

Degree of a vertex — how many edges touch it. Directed graphs have an in-degree and an out-degree.
Path — a sequence of vertices joined by edges.
Cycle — a path that returns to its starting vertex.
Connected component — a maximal group of mutually reachable vertices.

A tree is a graph with two extra promises

A tree is exactly a connected, acyclic, undirected graph. Every tree is a graph; almost no graph is a tree.

The two promises a tree makes — no cycles, exactly one path between any two vertices — are precisely what made Chapter 14's recursion so simple. Graph algorithms have to work without them, and nearly all of the extra machinery in the next four chapters exists to handle the cycles.

2Two representations

A graph is an abstract idea. To compute with it you have to write it down, and there are two standard ways.

The adjacency list

For each vertex, store the list of its neighbours. In Python, a dict of lists.

adjacency_list.py

graph = {
    "A": ["B", "D"],
    "B": ["A", "C", "E"],
    "C": ["B", "F"],
    "D": ["A", "E", "G"],
    "E": ["B", "D", "F", "G"],
    "F": ["C", "E", "H"],
    "G": ["D", "E", "H"],
    "H": ["F", "G"],
}

# Undirected, so every edge appears TWICE — once in each direction.
# Forgetting the second entry is the most common graph-construction bug.

# Weighted version: store pairs.
weighted = {
    "A": [("B", 4), ("D", 2)],
    "B": [("A", 4), ("C", 3), ("E", 5)],
}

The adjacency matrix

A V×V grid where cell [i][j] records whether an edge exists (or its weight).

adjacency_matrix.py

#      A  B  C  D
#  A [ 0  1  0  1 ]
#  B [ 1  0  1  0 ]
#  C [ 0  1  0  0 ]
#  D [ 1  0  0  0 ]

matrix = [[0,1,0,1],
          [1,0,1,0],
          [0,1,0,0],
          [1,0,0,0]]

# A  →  matrix[0][3]  →  O(1)
# An undirected matrix is symmetric across the diagonal.

Operation	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
Add an edge	O(1)	O(1)
Remove an edge	O(degree)	O(1)
Is there an edge u–v?	O(degree)	O(1)
Iterate u's neighbours	O(degree)	O(V) — scan the whole row
Iterate all edges	O(V + E)	O(V²)

The decision rule

Use an adjacency list unless you have a specific reason not to.

Real graphs are almost always sparse: a social network with a billion users does not have a billion friends each. Traversal algorithms iterate neighbours constantly, and that is the list's strongest operation and the matrix's weakest.

Use a matrix when the graph is genuinely dense (E approaching V²), when V is small and fixed, when you need O(1) edge lookups, or when you want to do linear algebra on it — matrix multiplication counts paths, which is occasionally exactly what you want.

The numbers make the argument concrete. For a graph with a million vertices and five million edges:

Representation	Storage
Adjacency list	~6 million entries
Adjacency matrix	1,000,000,000,000 cells — a terabyte to store five million facts

3Building graphs in Python

No standard-library graph type. Three practical patterns cover essentially everything.

Pattern 1 — dict of lists, built from an edge list

build.py

from collections import defaultdict

def build(edges, directed=False):
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        if not directed:
            g[v].append(u)        # ← forget this and half your edges vanish
    return g

g = build([("A","B"), ("A","D"), ("B","C")])

Pattern 2 — a grid is a graph

This is the one people miss most often. A 2-D grid is a graph whose vertices are cells and whose edges are the moves between them — you just never build the adjacency list explicitly.

grid.py

def neighbours(grid, r, c):
    """The implicit adjacency list of a grid cell."""
    rows, cols = len(grid), len(grid[0])
    for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):      # add diagonals if allowed
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
            yield (nr, nc)

# Every maze, flood fill, island-counting and shortest-path-on-a-map
# problem is a graph problem with this function as its edge set.

Pattern 3 — an implicit graph

Sometimes the graph is far too large to build, or infinite. Define the neighbour function and let the traversal generate vertices as it needs them.

implicit.py

def neighbours(word, dictionary):
    """Words one letter away. The graph of all English words, never built."""
    for i in range(len(word)):
        for ch in "abcdefghijklmnopqrstuvwxyz":
            candidate = word[:i] + ch + word[i+1:]
            if candidate != word and candidate in dictionary:
                yield candidate

# C is a shortest-path problem
# on a graph nobody ever constructed.

The three graph-building bugs

Forgetting the reverse edge in an undirected graph. Symptom: the traversal reaches half the vertices.
Isolated vertices vanishing. A vertex with no edges never appears in an edge list, so it is missing from a defaultdict built purely from edges. Add every vertex explicitly.
Duplicate edges from repeated input, quietly doubling degrees. Use a set of neighbours if the input might repeat.

4Modelling: seeing the graph

The hard part is not the algorithm. It is realising that the problem in front of you is a graph, and naming the vertices and edges.

Most graph problems in the wild do not mention graphs. The skill is translating. Two questions do almost all the work:

The two modelling questions

What is a vertex? A vertex is a state or a thing.
What is an edge? An edge is a relationship or a legal move between two states.

Once you can answer those two in one sentence each, the algorithm is usually the easy part.

Problem	A vertex is…	An edge is…	Then run
Shortest driving route	An intersection	A road, weighted by time	Dijkstra (Ch. 22)
Six degrees of separation	A person	A friendship	BFS (Ch. 20)
Build order for a project	A task	“must come before”	Topological sort (Ch. 21)
Solving a maze	A cell	A legal step	BFS (Ch. 20)
Word ladder: COLD → WARM	A word	One letter changed	BFS (Ch. 20)
Cheapest network cabling	A building	A possible cable, weighted by cost	MST (Ch. 23)
Detecting circular imports	A module	“imports”	Cycle detection (Ch. 21)
Fewest moves in a puzzle	A board position	One legal move	BFS on an implicit graph
Currency arbitrage	A currency	An exchange rate	Bellman-Ford (Ch. 22)

Look at the last column. Nine wildly different problems, five algorithms — and once the modelling is done, the code is nearly identical each time. The modelling is the work.

A worked example

“Given a list of course prerequisites, can a student finish all the courses?”

modelling.py

# 1. What is a vertex?  A course.
# 2. What is an edge?    A, so a DIRECTED edge A → B.
# 3. What is the question, in graph terms?
#       B
#     = C
#     = D
#
# Because if course A requires B and B requires A, no order exists.

prereqs = [("intro", "data-structures"),
           ("data-structures", "algorithms"),
           ("intro", "discrete-math"),
           ("discrete-math", "algorithms")]

# Now it is a cycle-detection problem, and Chapter 21 solves it in ten lines.
# The translation was the hard part, and it took three sentences.

5Traversal, previewed

One more thing before Chapter 20: why graph traversal needs something tree traversal did not.

Chapter 14 walked trees with four lines of recursion. Graphs need one extra thing, and it is not optional.

why_visited.py

# Tree traversal — no bookkeeping needed
def visit(node):
    if node is None: return
    process(node)
    visit(node.left)
    visit(node.right)

# The SAME code on a graph runs forever, because a cycle brings you back
# to a node you have already processed.

# Graph traversal — the visited set is what makes it terminate
def visit(vertex, graph, seen):
    if vertex in seen:
        return                    # ← this line is the entire difference
    seen.add(vertex)
    process(vertex)
    for neighbour in graph[vertex]:
        visit(neighbour, graph, seen)

Two things a tree gave you for free

No cycles, so you could never revisit a node.
One path to every node, so you could never reach the same node twice by different routes.

Graphs guarantee neither. The visited set replaces both, and forgetting it is the single most common graph bug — it produces an infinite loop rather than a wrong answer, which is at least easy to notice.

With the visited set in place, everything else is a choice about order:

Those two animations run the same algorithm. The only difference is whether the frontier is a queue or a stack. Chapter 20 is about what that one substitution buys you.

Store (list)

O(V + E)

Store (matrix)

O(V²)

Edge lookup (list)

O(deg)

Edge lookup (matrix)

O(1)

Full traversal

O(V + E)

Neighbours (list)

O(deg)

What to carry forward

A graph is vertices and edges. Directed, weighted, cyclic and connected are all independent options.
A tree is a connected acyclic undirected graph. The extra machinery in graph algorithms exists to cope with the cycles trees forbid.
Adjacency list by default: O(V+E) space and fast neighbour iteration. Matrix only for dense graphs or O(1) edge lookups.
In an undirected graph, every edge must be added twice. Forgetting the reverse edge is the classic construction bug.
Grids and puzzles are graphs with an implicit edge function. You rarely build the adjacency list.
Modelling is the real work: what is a vertex, what is an edge. Answer those and the algorithm is usually already written.
Graph traversal needs a visited set. Without one a cycle makes it run forever.

>_Playground

Build a graph three ways, convert between representations, and compare the memory. Then watch what happens without a visited set.

scratch.pypython not loaded

from collections import defaultdict
import sys

EDGES = [("A","B"), ("A","D"), ("B","C"), ("B","E"), ("C","F"),
         ("D","E"), ("D","G"), ("E","F"), ("E","G"), ("F","H"), ("G","H")]
VERTICES = ["A","B","C","D","E","F","G","H"]

# ---- adjacency list ----
def build_list(vertices, edges, directed=False):
    g = {v: [] for v in vertices}        # every vertex, even isolated ones
    for u, v in edges:
        g[u].append(v)
        if not directed:
            g[v].append(u)
    for v in g:
        g[v].sort()
    return g

adj = build_list(VERTICES, EDGES)
print("adjacency list:")
for v, ns in adj.items():
    print(f"  {v}: {ns}")
print()

# ---- adjacency matrix ----
def build_matrix(vertices, edges, directed=False):
    idx = {v: i for i, v in enumerate(vertices)}
    n = len(vertices)
    m = [[0]*n for _ in range(n)]
    for u, v in edges:
        m[idx[u]][idx[v]] = 1
        if not directed:
            m[idx[v]][idx[u]] = 1
    return m, idx

mat, idx = build_matrix(VERTICES, EDGES)
print("adjacency matrix:")
print("    " + "  ".join(VERTICES))
for v, row in zip(VERTICES, mat):
    print(f"  {v} " + "  ".join(str(x) for x in row))
print()

print(f"edges stored: {len(EDGES)}")
print(f"list entries : {sum(len(n) for n in adj.values())}")
print(f"matrix cells : {len(VERTICES)**2}   <- most of them zero")
print()

# ---- degree ----
print("degrees:", {v: len(n) for v, n in adj.items()})
print()

# ---- the visited set, and what happens without it ----
def traverse(g, start, seen=None, depth=0, budget=[40]):
    if seen is None:
        seen = set()
    if budget[0] <= 0:
        return
    budget[0] -= 1
    if start in seen:
        return
    seen.add(start)
    print("  " * min(depth, 8) + start)
    for n in g[start]:
        traverse(g, n, seen, depth + 1, budget)

print("WITH a visited set:")
traverse(adj, "A")
print()

def traverse_broken(g, start, depth=0, budget=[25]):
    if budget[0] <= 0:
        print("  " * min(depth, 8) + "... (stopped after 25 visits - this never terminates)")
        return
    budget[0] -= 1
    print("  " * min(depth, 8) + start)
    for n in g[start]:
        traverse_broken(g, n, depth + 1, budget)

print("WITHOUT a visited set:")
traverse_broken(adj, "A")

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 20 — Breadth-First and Depth-First Search

Two ways to explore a maze: flood it evenly, or follow one corridor to the end. Same code, different container.

Continue →