Graphs and trees

Store relationships explicitly

A graph consists of vertices and edges. Vertices represent objects, and edges represent connections. An edge can be directed or undirected. In an undirected graph, a connection from u to v also permits travel from v to u. In a directed graph, the reverse connection must be stated separately.

Choose a representation based on the operations you need. An adjacency matrix answers whether a particular pair is connected directly. An adjacency list efficiently lists the neighbors of one vertex. Both represent the same graph, but their memory and iteration costs differ.

A complete example

Build an undirected graph and visit the vertices reachable from vertex 0.

n = 4
edges = [(0, 1), (1, 2)]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

seen = {0}
stack = [0]
while stack:
    u = stack.pop()
    for v in adj[u]:
        if v not in seen:
            seen.add(v)
            stack.append(v)

print(sorted(seen))

[0, 1, 2]

Vertex 3 is isolated, so it is not reached. The set seen stores visited vertices. Marking a vertex when it is added to the stack prevents the same vertex from being queued repeatedly through different edges.

An adjacency list uses O(n + m) storage for n vertices and m edges. This traversal is O(n + m) because each vertex and edge is inspected a bounded number of times. A matrix uses O(n squared) storage and scanning all neighbors of every vertex takes O(n squared) work.

Build independent rows

Use [[] for _ in range(n)] for an adjacency list. Writing [[]] * n creates several references to the same inner list. Adding a neighbor in one row then changes every row. The same aliasing mistake can break a matrix created from a repeated inner list.

For a matrix, use [[0] * n for _ in range(n)]. When reading an undirected edge, set both matrix[u][v] and matrix[v][u]. For a directed parent-to-child edge, set only the stated direction.

Trees and roots

An undirected tree is connected and has no cycles. With n vertices it has n - 1 edges. Choosing a root gives parent and child relationships. The tree exercises already supply directed parent-to-child pairs and identify the root. Their output must preserve that direction rather than add reverse child-to-parent entries.

Check numbering carefully. Some exercises number vertices from 0, others from 1. Either allocate n + 1 entries for one-based labels or convert every input label consistently. Sort neighbors when the output requires increasing order.

Traversal is not every path problem

The optional museum exercise asks for a path visiting every room exactly once. A normal depth-first traversal does not solve that requirement. Traversal may return along an edge and revisit vertices. A Hamiltonian-path search must try choices, mark a room for the current path, and undo that mark when backtracking.

Its n at most 10 permits an exponential search with pruning. To find the lexicographically first route, consider starting rooms and neighbors in increasing order and stop at the first complete valid path. This is an extension exercise because it requires reasoning beyond graph storage.

Practice

Complete matrix and list representations for graphs, then the two directed tree representations. Test an isolated vertex, a single-vertex tree, and edges whose input order differs from sorted order. For the optional search, test a graph where the first choice leads to a dead end. State whether your visited marks describe the whole traversal or only the current candidate path.