Self-Assessment Quiz: Graph Representations, Traversal, and Search

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Throughout, "the example graph" is the chapter's running graph (adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3], 5: []}).

Question 1

The adjacency matrix of an undirected simple graph on $n$ vertices is always:

A) lower-triangular B) symmetric with a zero diagonal C) symmetric with a diagonal of all 1s D) asymmetric in general

Question 2

On an adjacency list, the cost of testing whether a specific edge $\{i,j\}$ exists is:

A) $\Theta(1)$ B) $\Theta(\deg(i))$ C) $\Theta(n)$ D) $\Theta(n^2)$

Question 3

You have a dense graph and must answer ten million "is $\{i,j\}$ an edge?" queries. The better representation is:

A) adjacency list, because it is always the default B) adjacency matrix, because each query is $\Theta(1)$ and density removes its space penalty C) it makes no difference D) neither — you need a balanced tree

Question 4

The data structure that gives BFS its ring-by-ring behavior is:

A) a LIFO stack B) a FIFO queue C) a priority queue D) a hash set only

Question 5

The data structure that gives DFS its plunge-deep behavior is:

A) a FIFO queue B) a LIFO stack (often the call stack via recursion) C) a min-heap D) a deque used as a queue

Question 6

In BFS, a vertex must be marked visited at the moment it is:

A) dequeued and processed B) enqueued (discovered) C) added to the final order list D) it does not matter when

Question 7

bfs_order(adj, 0) on the example graph returns:

A) [0, 1, 3, 2, 4] B) [0, 1, 2, 3, 4] C) [0, 1, 2, 3, 4, 5] D) [0, 2, 1, 3, 4]

Question 8

dfs_order(adj, 0) on the example graph (neighbor lists increasing) returns:

A) [0, 1, 2, 3, 4] B) [0, 1, 3, 2, 4] C) [0, 2, 3, 1, 4] D) [0, 1, 3, 4, 2]

Question 9 (True/False, justify)

True or false: On the example graph, bfs_distances(adj, 0) returns a dist map whose keys include 5. Justify in one sentence.

Question 10

BFS computes correct shortest paths:

A) on any graph, weighted or not B) only when every edge counts the same (unweighted or all weights equal) C) only on trees D) only on directed graphs

Question 11

To detect a cycle in an undirected graph with DFS, you report a cycle when you find an edge to an already-visited vertex that is:

A) any visited vertex B) the parent you arrived from C) a visited vertex other than the parent (a back edge) D) an unvisited vertex

Question 12

Topological sort via DFS records each vertex:

A) at discovery (pre-order), no reversal B) at finish (post-order), then reverses the list C) at finish (post-order), no reversal D) in the order the outer loop visits keys

Question 13

A topological order of a directed graph exists if and only if the graph:

A) is connected B) has no directed cycle (is a DAG) C) is undirected D) has at most $n - 1$ edges

Question 14

On an adjacency list, both BFS and DFS run in time:

A) $\Theta(V^2)$ B) $\Theta(V \cdot E)$ C) $\Theta(V + E)$ D) $\Theta(E^2)$

Question 15

On an adjacency matrix, both BFS and DFS run in time:

A) $\Theta(V + E)$ B) $\Theta(V^2)$ C) $\Theta(E)$ D) $\Theta(V \log V)$

Question 16 (True/False, justify)

True or false: The neighbor-scanning work of a traversal on an adjacency list is $\Theta(V \cdot E)$ because each of the $V$ vertices scans a neighbor list. Justify in one sentence.

Question 17

The lemma that makes the total neighbor-scanning work sum to $\Theta(E)$ rather than $\Theta(V^2)$ is:

A) the pigeonhole principle B) the handshaking lemma, $\sum_v \deg(v) = 2E$ C) the master theorem D) Euler's formula

Question 18 (Short answer)

A graph has $n = 4$ vertices and exactly $n - 1 = 3$ tree edges after a BFS. In one sentence, why can the BFS tree never contain a cycle?

Question 19 (Short answer)

State the one-line test (in terms of the size of the reached set) for whether a traversal from a single vertex proves the whole undirected graph is connected.

Question 20 (True/False, justify)

True or false: Reusing the undirected cycle-detection routine on a directed graph (by ignoring edge directions) correctly detects directed cycles. Justify with the kind of graph that breaks it.

Answer Key

Topics to review by question