Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 14
Graphs and Graph Searches (Lecture 14)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
An adjacency matrix for a graph with V vertices and E edges uses memory:
A V × V grid, whatever E is. O(V + E) (a) is the adjacency list.
-
Breadth-first search keeps the vertices waiting to be expanded in a:
First discovered, first expanded. A stack (b) gives DFS; a priority queue (c) gives Dijkstra's algorithm, beyond this course.
-
An undirected graph has 7 vertices with degrees 2, 3, 2, 2, 3, 3 and 1. How many edges does it have?
The degrees add up to 2 + 3 + 2 + 2 + 3 + 3 + 1 = 16, and every edge is counted at both ends: E = 16 / 2 = 8. 16 (a) forgets to halve. (These are the degrees of H.)
-
BFS from s always reaches a vertex first along a path with the fewest edges because:
The queue holds all of distance d before any of distance d + 1, so a vertex is discovered while BFS is expanding the layer just before it. It never tries every path (c) — that would be exponential. Marking on dequeue (b) is a bug (W14-B1).
-
bfs(H, "A")returns:A adds B and D; B adds C and E; D adds nothing new; C adds F; F adds G (W14-T1). (a) is alphabetical order, which BFS does not use.
-
dfs(H, "A")returns:A → B → C → F → E → D, back up to F, then G (W14-T2). (a) is what you get if you think of BFS layers; (b) goes from C to E, but C and E are not adjacent.
-
shortest_path_unweighted(H, "D", "C")returns:D's list is A, E, so A is taken first and becomes B's parent; B then discovers C. D–E–B–C (c) and D–E–F–C (a) are also three edges long — equally short — but BFS keeps the first parent it records (W14-T4).
-
has_edge(u, v)on an adjacency matrix costs:One cell,
matrix[i][j], after two O(1) hash-map lookups for i and j. O(deg u) (b) is the list. -
neighbours(u)on an adjacency matrix costs:The whole row of V cells must be scanned to find the 1s. That is the matrix's price.
-
A BFS on a
MatrixGraphcosts O(V2) even when the graph has very few edges, because:V vertices, each costing a V-cell row scan: V2. The number of edges does not change the work.
-
An undirected graph with E edges is stored as an adjacency list. How many neighbour entries do the lists hold in total?
Each undirected edge u–v is stored in u's list and in v's list. The same fact is Σ deg(v) = 2E.
-
BFS marks a vertex as visited when it is enqueued, not when it is dequeued, because otherwise:
A vertex with two neighbours that are taken before it is enqueued by both, and then appears twice in the order (W14-B1). BFS still finds every vertex (b) — it just repeats some.
-
dfs_iterativepushes each vertex's neighbours in reverse order because:A stack is last in, first out (not a): pushing D then B from A's list B, D puts B on top, so B comes off first — the same choice the recursive
forloop makes. -
The recursive
dfsis run on a graph that is one path of 5,000 vertices. In Python, with the default settings, it:One call frame per vertex on the path; Python's default limit is 1,000 frames. The reference
dfsalready fails on a path of 1,000 edges.dfs_iterativehandles it. -
A DAG is:
Directed acyclic graph. (a) describes a tree.
-
topological_sorton the directed graph A → B, B → C, C → A returns:Every vertex keeps in-degree 1, so the ready queue starts empty, nothing is output, and 0 < 3 vertices means a cycle:
None. TheValueError(d) is for an undirected graph. -
Undirected cycle detection ignores a visited neighbour that is the vertex's parent, because:
When DFS enters B from A, B's list contains A. Without the check every edge would be reported as a cycle (W14-B3).
-
In the directed diamond A → B, A → C, B → D, C → D, a DFS from A meets D a second time, from C. That is not a cycle, because at that moment D is:
D was finished when the search backed up from B; it is no longer on the current path A → C. Only an edge to a grey vertex (b) closes a cycle.
-
A graph has vertices A to I and the undirected edges A–B, B–C, D–E, F–G. How many connected components does it have?
{A, B, C}, {D, E}, {F, G}, and H and I on their own. A vertex with no edges is a component of its own; 4 (a) and 3 (b) forget H and I.
-
topological_sort(P)returns:In-degree 0 at the start: A and B, queued in node order. A releases nothing (C still waits on B); B releases C and D; C, then D, then E, then F (W14-T5). (b) is also a valid topological order — it is the DFS one — but it is not what Kahn's algorithm returns. (c) puts C before B, although B → C.
-
Which of these can BFS on its own not answer correctly?
BFS counts edges; with road lengths the fewest roads is not the fewest kilometres. That needs Dijkstra's algorithm, which this course only names.
-
One BFS over an adjacency list costs:
Every vertex is enqueued and dequeued once; every list is read once, Σ deg = 2E entries in total.
19 marks
Written questions
5 written questions (19 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 19
-
Compare the adjacency list and the adjacency matrix: memory,
has_edge,neighbours, and the cost of one BFS. Which would you choose for a road map of 100,000 junctions, and which for a graph of 500 people in which almost everyone knows almost everyone and you ask "do these two know each other?" millions of times? Justify with numbers.Model answer and marking points
- Memory: list O(V + E) — V + 2E cells undirected; matrix V2 cells, however few edges.
has_edge(u, v): list O(deg u), scan u's neighbours; matrix O(1), one cell.neighbours(u): list O(deg u); matrix O(V), a row scan. One BFS/DFS: list O(V + E); matrix O(V2).- Road map, V = 100,000, about three roads per junction (E about 150,000): the list holds about 100{,}000 + 300{,}000 = 400{,}000 cells; the matrix 1010 cells — about 10 GB even at one byte each. The list, without question; a BFS on it is a few hundred thousand steps.
- 500 people, nearly everyone knows everyone: E is close to 500 × 499 / 2 ≈ 125{,}000 and the matrix is only 250{,}000 cells — about the same as the list. Each
has_edgeis O(1) on the matrix against a scan of up to about 500 neighbours on the list; asked millions of times, the matrix wins by a large factor.
-
Describe breadth-first search. Explain why it finds shortest paths by number of edges, how
shortest_path_unweightedrebuilds the path, and why the answer can be wrong on a road map with different road lengths.Model answer and marking points
- Algorithm: put s in a queue and mark it; repeatedly dequeue a vertex, output it, and enqueue (and mark) each unmarked neighbour. O(V + E).
- Why shortest: the queue holds the vertices in non-decreasing order of distance from s — all of distance d before any of distance d + 1 — so a vertex is first discovered from a vertex one layer nearer, and no later route can be shorter.
- Rebuilding the path: record, for each vertex, the vertex it was discovered from (the parent,
Nonefor s). When the goal is dequeued, follow the parents back to s and reverse the list; if the queue empties first, the goal is unreachable —None. - Weighted roads: BFS minimises the number of edges. A route of two 40 km roads beats one of three 1 km roads by BFS's measure. Weighted shortest paths need Dijkstra's algorithm (a priority queue), beyond this course.
-
Recursive DFS and DFS with your own stack: what does the call stack remember for you? Why must
dfs_iterativemark a vertex when it is popped and push neighbours in reverse to give the same order asdfs? Why write the iterative version at all in Python?Model answer and marking points
- The call stack holds one frame per vertex on the current path: which vertex it is, and how far its
forloop over the neighbours has got. Returning from a call is backing up. - Mark on pop: recursion marks a vertex when it enters it, and may reach it by a deeper route before an earlier vertex's loop gets to it. Marking on push would fix it to the earlier route. So allow a vertex to be pushed more than once and skip it if it is already visited when popped.
- Push in reverse: the stack returns the last push first; to take the first neighbour first, it must be pushed last.
- Why bother in Python: the recursive version fails with
RecursionErroronce the path is about 1,000 vertices deep; your ownStackcan grow as large as memory allows. (It also shows exactly what recursion was doing.)
- The call stack holds one frame per vertex on the current path: which vertex it is, and how far its
-
Explain cycle detection in an undirected graph and in a directed graph. Why does each rule give wrong answers when used on the other kind of graph? Give a small example of each failure.
Model answer and marking points
- Undirected: DFS remembering each vertex's parent; a visited neighbour that is not the parent closes a cycle. The parent must be excluded because every edge is stored at both ends.
- Directed: three colours — white (unseen), grey (on the current path), black (finished). An edge to a grey vertex closes a cycle; an edge to a black one does not.
- Parent rule on a directed graph fails: A → B, B → A is a cycle, but at B the neighbour A is its parent and is skipped — "no cycle".
- Visited-only rule on a directed graph fails: the diamond A → B → D, A → C → D, or simply B → C and A → C searched from B first: C is visited when reached again, and the check says "cycle" wrongly (W14-B4).
- Colour rule on an undirected graph fails: at B, entered from A, the neighbour A is grey, so every edge is reported as a cycle.
-
Define a topological order. When does one exist? Describe Kahn's algorithm, how it detects that no order exists, and one real application.
Model answer and marking points
- Definition: an order of the vertices of a directed graph in which, for every edge X → Y, X comes before Y. It exists exactly when the graph is a DAG: a cycle would need each of its vertices to come before the next.
- Kahn: count in-degrees; queue the vertices with in-degree 0; repeatedly dequeue one, output it, and subtract 1 from the in-degree of each vertex it points to, queueing any that reach 0. O(V + E).
- No order: if fewer than V vertices are output, the rest wait on each other — they contain a cycle — so return
None. - Application: course prerequisites (a valid study plan), build systems (compile after dependencies), package managers, spreadsheet recalculation.