Graphs and their representations

Use a graph when items have relationships: roads join cities, links join pages, and prerequisites join courses.

One graph, three representations

A --- B
|     |
C --- D

Edge list:       [(A, B), (A, C), (B, D), (C, D)]
Adjacency lists: A: B, C     B: A, D     C: A, D     D: B, C

Adjacency matrix:    A B C D
                  A  0 1 1 0
                  B  1 0 0 1
                  C  1 0 0 1
                  D  0 1 1 0

A graph is a collection of vertices and edges. Its representation decides how those edges are stored. Adjacency lists and matrices are not different kinds of connectivity.

An undirected edge connects both ways. A directed edge goes from one vertex to another. Weighted edges also store a cost. Decide whether self-loops and parallel edges are allowed; that choice affects storage and deletion.

The diagram is an undirected simple graph: no self-loops or parallel edges. Its adjacency invariant requires B in A's neighbors exactly when A is in B's neighbors. Its matrix is symmetric.

Trace a change

Insert edge B–C: add C to B's neighbors and B to C's neighbors. To test whether A–D exists, inspect A's neighbors; D is absent. Delete A–B by removing B from A and A from B.

For a directed graph, each operation changes only the outgoing edge. Keeping incoming adjacency as well can make predecessor queries faster, but every update must maintain both views.

Choose by the questions you ask

Let V be the number of vertices, E the number of edges, and degree(u) the number of neighbors of u.

Representation	Space	Test edge u–v	Enumerate u's neighbors
Edge list	O(V + E), including vertices	O(E)	O(E)
Array/list of neighbors per vertex	O(V + E)	O(degree(u))	O(degree(u))
Hash set of neighbors per vertex	O(V + E)	Expected O(1)	O(degree(u))
Adjacency matrix	O(V²)	O(1)	O(V)

An edge list is convenient when processing every edge, such as sorting edges by weight. Adjacency lists suit sparse graphs and traversal. A matrix suits dense graphs or frequent edge tests when quadratic memory is acceptable.

Appending an edge to a neighbor array is amortized O(1) if duplicates need not be checked. Deleting a specified neighbor requires finding it and may shift entries. Neighbor hash sets make insertion and deletion expected O(1), but cannot represent parallel edges without extra counts or IDs.

A weighted matrix needs a distinct marker for no edge. Zero can be a real edge weight.

Predict and modify

What breaks if undirected deletion updates only one endpoint?
Does an isolated vertex appear in an edge list automatically?
Modify BFS to store a parent for each discovered vertex and reconstruct a path.

Implementation and exercise answers

Implement adjacency sets and BFS

BFS uses a queue to visit vertices by increasing number of edges from the start. Mark vertices when adding them to the queue so cycles do not cause repeated work.

from collections import deque


def add_edge(graph, left, right):
    graph.setdefault(left, set()).add(right)
    graph.setdefault(right, set()).add(left)


def remove_edge(graph, left, right):
    graph[left].discard(right)
    graph[right].discard(left)


def distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance


graph = {vertex: set() for vertex in "ABCDZ"}
for left, right in [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]:
    add_edge(graph, left, right)
assert distances(graph, "A") == {"A": 0, "B": 1, "C": 1, "D": 2}
add_edge(graph, "B", "C")
remove_edge(graph, "A", "B")
assert "B" not in graph["A"] and "A" not in graph["B"]
assert distances(graph, "A")["B"] == 2
assert distances(graph, "Z") == {"Z": 0}

With adjacency lists or sets, BFS takes O(V + E) time over the reachable graph under constant-time vertex bookkeeping. Its queue and visited map use O(V) extra memory. BFS gives shortest paths by edge count; it does not solve arbitrary weighted shortest paths.

Exercise answers

Different traversal directions would disagree about whether the edge exists. An edge list needs a separate vertex collection to preserve isolated vertices. Store the current vertex as a new neighbor's parent; follow parents backward from the target, then reverse the path.

A grid can represent neighbors implicitly; see Number of Islands.

Next: Tries.