Exercises: Graph Representations, Traversal, and Search

DataField.Dev

Exercises: Graph Representations, Traversal, and Search

These build from mechanical warm-ups on representations and hand-traces up to full correctness proofs, code, modeling, and a conjecture-and-test investigation. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md — hand-trace each one yourself before you peek.

Unless a problem says otherwise, "the example graph" means the chapter's running graph: vertices $0,1,2,3,4,5$ with edges $\{0,1\}, \{0,2\}, \{1,3\}, \{2,3\}, \{3,4\}$ and vertex $5$ isolated, stored as the adjacency list

adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3], 5: []}

with every neighbor list in increasing order.

Part A — Warm-ups: representations and hand-traces (⭐)

28.1 † Write the $6\times 6$ adjacency matrix $A$ of the example graph. Then, without re-reading the picture, use the matrix to answer: (a) is $\{1,4\}$ an edge? (b) what is $\deg(3)$? (c) which row is all zeros, and what does that tell you?

28.2 Convert this adjacency matrix back into an adjacency-list dictionary (vertices $0,1,2,3$): $$A = \begin{pmatrix} 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 \end{pmatrix}.$$ Is the underlying graph connected? How many edges does it have?

28.3 † Hand-trace bfs_order(adj, 0) on the example graph using the queue-trace table format from §28.2 (columns: Dequeue, Append to order, Newly discovered, Queue after). Confirm you get [0, 1, 2, 3, 4].

28.4 Hand-trace dfs_order(adj, 2) — note the source is vertex $2$, not $0$. Give the call-stack trace and the final pre-order. Does vertex $5$ appear?

28.5 † For a graph with $n = 5000$ vertices and $m = 9000$ edges, compute (a) the number of cells in the adjacency matrix, and (b) the total number of entries in the adjacency list (count each undirected edge twice, then add the $n$ keys). State the approximate ratio.

28.6 In one sentence each, give the $\Theta$-cost on an adjacency list for: (a) testing whether $\{i,j\}$ is an edge, (b) listing the neighbors of $v$, (c) iterating over all edges. (You may consult the §28.1 decision table, then close it and reproduce the row from memory.)

Part B — Prove it (⭐⭐)

28.7 † (Scaffolded — fill in the missing step.) Prove that the adjacency matrix $A$ of an undirected simple graph is symmetric ($A[i][j] = A[j][i]$ for all $i,j$) with zero diagonal ($A[i][i] = 0$). Fill the blanks:

Symmetry. By definition $A[i][j] = 1$ exactly when $\underline{\hphantom{xxxxxxxx}}$ is an edge. Since the graph is undirected, the edge $\{i,j\}$ and the edge $\{j,i\}$ are $\underline{\hphantom{xxxxxxxx}}$, so $A[i][j] = 1 \iff A[j][i] = 1$. Hence $A[i][j] = \underline{\hphantom{xxxx}}$ for all $i,j$.
Zero diagonal. $A[i][i] = 1$ would mean $\{i,i\}$ is an edge — i.e. a $\underline{\hphantom{xxxxxxxx}}$ — which a simple graph forbids. So $A[i][i] = \underline{\hphantom{xxxx}}$. $\blacksquare$

28.8 Prove that the BFS tree of a connected graph on $n$ vertices has exactly $n - 1$ edges. (Use the fact established in §28.4 that BFS records exactly one tree edge — the parent pointer — each time it discovers a new vertex.)

28.9 † (Prove it.) Let $u$ and $v$ be two vertices both at BFS distance $d$ from a source $s$ (that is, $\mathrm{dist}[u] = \mathrm{dist}[v] = d$). Prove that the edge $\{u,v\}$, if it exists in the graph, is not a BFS tree edge. (Hint: a tree edge connects a vertex at distance $d$ to one at distance $d+1$; use the §28.2 distance invariant.)

28.10 Prove that if a connected undirected graph has $n$ vertices and exactly $n - 1$ edges, then it contains no cycle. (Suggested route: suppose it had a cycle, delete one edge of the cycle, argue the graph stays connected, and count edges against §28.4's "$n-1$ edges suffice for connectivity" fact to reach a contradiction. You may cite Chapter 27 for the definition of connected.)

28.11 † Prove the finishing-time property used in §28.5: in a DFS of a DAG, if $a \to b$ is an edge, then $b$ finishes before $a$. Write out the three cases for the state of $b$ when DFS examines the edge $a \to b$ (unvisited / finished / started-but-not-finished), and explain why the third case is impossible in a DAG.

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention.

28.12 † Write neighbors_via_matrix(A, v) that returns the sorted list of neighbors of vertex v given an adjacency matrix A (a list of lists). What is the running time in terms of $n$, and why is it $\Theta(n)$ even when v has only one neighbor?

28.13 Write to_adjacency_list(A) that converts an adjacency matrix A into the dictionary representation {v: [neighbors...]}. Run it (by hand) on the matrix from Exercise 28.2 and show the # Expected output:.

28.14 † Implement degrees_of_separation(adj, s, t) that returns the BFS distance between vertices s and t, or -1 if t is unreachable from s. Reuse the chapter's bfs_distances. Trace it on the example graph for s = 0, t = 4 and for s = 0, t = 5, and show both expected outputs.

28.15 Implement count_components(adj) returning the number of connected components (an integer), built on top of a traversal. Trace it on the example graph and give the # Expected output:.

28.16 † (Implement it — iterative DFS.) Write dfs_iterative_matching(adj, s) that uses an explicit stack but produces the same pre-order as the recursive dfs_order. (Recall the §28.3 pitfall: you must push neighbors in reverse so the smallest is popped first.) Trace it on the example graph from s = 0 and confirm it returns [0, 1, 3, 2, 4], matching the recursive version.

Part D — Find the error (⭐⭐)

Each item below contains a flawed argument or buggy program. State precisely which part fails and why, and give a concrete input that exposes the bug.

28.17 † A teammate writes BFS but marks vertices visited at dequeue time instead of at enqueue time:

def bfs_buggy(adj, s):
    from collections import deque
    visited = set()
    queue = deque([s])
    order = []
    while queue:
        v = queue.popleft()
        visited.add(v)            # marks at DEQUEUE
        order.append(v)
        for w in adj[v]:
            if w not in visited:  # w may already be in the queue!
                queue.append(w)
    return order

Explain what goes wrong, and exhibit a small graph on which bfs_buggy appends some vertex to order more than once. Why does marking at enqueue fix it?

28.18 Claim: "DFS pre-order is a valid topological order on any DAG — just record each vertex when you first visit it, no need to reverse anything." "Justification": "DFS visits a vertex before its descendants, and in a DAG a vertex's descendants are exactly the tasks that depend on it." Find the flaw, and give a 3-vertex DAG on which recording at discovery (pre-order) produces an order that violates a dependency.

28.19 † Claim: "To test whether an undirected graph has a cycle, run a DFS and report a cycle the moment you reach any already-visited vertex." "Proof": "an already-visited vertex means you have looped back." Find the flaw. Give the smallest graph (it has two vertices) on which this rule wrongly reports a cycle, and state the one extra condition the correct §28.4 rule adds.

28.20 A student claims connected_components is $\Theta(V \cdot (V+E))$ "because it can launch a full $\Theta(V+E)$ traversal from every one of the $V$ vertices." Explain why the true bound is $\Theta(V+E)$, identifying the exact line of code that prevents the blow-up.

Part E — Model it (⭐⭐ / ⭐⭐⭐)

28.21 † (Model it — the social-network anchor.) A small startup has six employees. Alice messages Bob and Carla; Bob messages Dan; Carla messages Dan; Dan messages Eve; Frank messages no one and is messaged by no one. Treating "messages" as an undirected "communicates with" relation:

(a) Draw the graph and write its adjacency list (label people $A$–$F$). (b) Compute, by hand-running BFS from Alice, everyone's degrees of separation from Alice. (c) Is the communication network connected? Which one change (adding a single edge) would connect it?

28.22 (Model it — build dependencies.) A build system must compile four files with these "must come before" rules: config.h before utils.c; config.h before main.c; utils.c before main.c; utils.c before tests.c. Model the rules as a directed graph, give its adjacency list, argue it is a DAG, and produce one valid build order. How many distinct valid topological orders are there? List them.

28.23 † (Model it — maze as a graph.) A robot sits in a rectangular grid maze; some cells are open and some are walls. The robot may step north/south/east/west into an open, in-bounds neighbor. Explain how to model the maze as a graph (what are the vertices? the edges?), and state precisely which chapter algorithm finds the fewest-step path from start to goal and why it (rather than DFS) is the right choice. You need not write code — give the modeling and the one-sentence justification.

28.24 (Model it — packet routing, unweighted.) A network has routers connected by links, all of equal cost. You want the route from router $s$ to router $t$ that traverses the fewest hops. State the graph model, name the algorithm, and explain in one sentence why this stops being the right algorithm the moment links have different latencies (forward-pointer to Chapter 29).

Part F — Conjecture and test (⭐⭐⭐)

28.25 † (Conjecture and test, then prove.) Define $T(G)$ = (number of tree edges) and $B(G)$ = (number of non-tree edges) discovered by a single DFS of a connected undirected graph $G$ on $n$ vertices with $m$ edges. Using the chapter's has_cycle/DFS code as a starting point, instrument a DFS to count tree edges and back edges on several small connected graphs (a path, a cycle, a triangle, the example graph's large component, $K_4$). Tabulate $n$, $m$, $T(G)$, $B(G)$.

(a) Conjecture a formula for $T(G)$ in terms of $n$, and for $B(G)$ in terms of $n$ and $m$. (b) Prove your conjecture for $T(G)$. (Hint: §28.4 already tells you how many tree edges a traversal of a connected graph produces.) (c) A classmate conjectures "$B(G) = 0 \iff G$ is a tree." Test it on your data, then prove or disprove it. Connect your answer to the cycle-detection rule of §28.4 and to theme four of the book.

28.26 (Conjecture and test.) For BFS on the example graph, conjecture whether the set of vertices returned by bfs_order(adj, s) depends on the source s chosen within the same component — e.g., compare the reachable set from $s = 0$, $s = 3$, and $s = 4$. Test all three by hand, state the conjecture precisely, and prove it using the symmetry of reachability in an undirected graph (cite the equivalence-relation argument of §28.4 / Chapter 12).

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

28.27 † (Ch. 27 + 28.) Use the handshaking lemma ($\sum_{v} \deg(v) = 2m$, Chapter 27) to prove that the total neighbor-scanning work of a BFS or DFS on an adjacency-list undirected graph is exactly $2m = \Theta(E)$. Then state, in one sentence, why this is the step that turns the naive $O(V^2)$ bound into $\Theta(V + E)$.

28.28 (Ch. 14 + 28.) For a sparse graph with $V = 10^6$ and $E = 3 \times 10^6$, give the approximate operation counts for adjacency-list BFS versus adjacency-matrix BFS, and decide which is feasible on a machine doing $10^9$ simple operations per second. (This is the Chapter 14 input-size lesson applied to graphs.)

28.29 † (Ch. 6 + 28.) The §28.2 proof that BFS computes shortest distances rests on a loop invariant about the queue, proved by the initialization/maintenance pattern of Chapter 6. State the invariant in your own words, identify which part of the BFS code establishes initialization and which line maintains it, and name the Chapter 6 technique this mirrors.

28.30 (Ch. 12 + 28.) "Reachable from one another" partitions the vertices of an undirected graph into connected components. Prove that this relation is an equivalence relation (reflexive, symmetric, transitive), citing the partition theorem of Chapter 12 to conclude that the components are disjoint and cover $V$. Which property of undirected (vs. directed) graphs is what makes the relation symmetric?

28.31 (Ch. 13 + 28 — Deep Dive.) In Chapter 13 a topological sort was defined as a linear extension of a partial order. In §28.5 we re-derived it as a reversed DFS post-order. Argue that the two notions coincide: show that the output of topological_sort (a) lists every $a$ before every $b$ whenever $a \to b$, and therefore (b) is a linear extension of the partial order whose covering relation is the edge set. Where does the argument secretly use that the graph is acyclic?

28.32 (Deep Dive — directed cycle detection.) The undirected has_cycle of §28.4 is wrong for directed graphs (Exercise 28.18 / the §28.5 "Find the Error"). Design the correct directed test: keep three states per vertex — unvisited, on the recursion stack (started, not finished), and finished — and report a cycle exactly when DFS follows an edge to a vertex that is on the stack (a back edge to an ancestor). Write the pseudocode, and prove that it reports a cycle if and only if the directed graph has one. (This is the engine a robust topological_sort folds in to reject non-DAGs.)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards a clearly stated claim, correct use of the relevant invariant or definition, explicit appeal to the handshaking lemma or distance invariant where needed, and a clean conclusion. For each program, the rubric rewards a correct hand-derived # Expected output: and a one-line complexity justification.