Micro-questions over the edge classification module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why this exists
1. What question motivates the whole lesson?
Answer
“Build A needs B, B needs C, C needs A — is this build order possible?” How does a program find the cycle without checking all orderings?
2. State the naive cycle rule, and why it is wrong.
Answer
“Run DFS, and if you ever meet an already-visited vertex, there is a cycle.” Wrong: on , there is no cycle at all, but C → D meets a visited vertex. A → C → D is simply a second route to D.
3. State the core observation of the lesson in one line.
Answer
“Already visited” is one bit, and one bit is not enough — record not just whether you visited a vertex, but when you arrived and when you left.
4. What two different situations does a visited set merge?
Answer
“Already visited and finished” (the search left it and came back out) versus “already visited and still on the current path”. Only the second is a cycle.
B. The vocabulary
5. What is a traversal tree?
Answer
The subgraph made of exactly the edges the traversal used to reach each vertex for the first time. Every vertex except the start is reached by exactly one such edge, so they form a tree.
6. What is a traversal forest?
Answer
What you get when one traversal cannot reach everything: you start a fresh search from an unvisited vertex, growing a second tree. The collection is a forest.
7. What shape is a DFS tree, and why?
Answer
Long and narrow, because DFS keeps descending.
8. What shape is a BFS tree, and what is its special property?
Answer
Short and wide. Every root-to-vertex path in it is a shortest path in the original graph, measured in edges. Hence its other name: the shortest-path tree.
9. What is discovery time ?
Answer
The counter value at the moment the search first arrives at and colours it grey. Also called entry or arrival time.
10. What is finish time ?
Answer
The counter value at the moment the search has examined every edge out of and leaves it for good. Also called exit or departure time.
11. Define ancestor in traversal-tree terms.
Answer
A vertex on the traversal-tree path from the root down to another. If u is an ancestor of x, the search entered u, and had not yet left u, when it entered x.
12. Is a vertex its own ancestor?
Answer
Yes — trivially both its own ancestor and its own descendant. This is why a self-loop counts as a back edge.
13. Define the four edge kinds.
Answer
Tree edge — used to reach a previously unvisited vertex.
Back edge — points to one of the vertex’s own ancestors.
Forward edge — points to a descendant reached by some other, longer route first.
Cross edge — joins two vertices where neither is an ancestor of the other.
14. Explain the white/grey/black scheme.
Answer
White = not yet discovered. Grey = discovered but not finished, i.e. currently on the recursion stack. Black = finished. A visited set merges grey and black into one bit, which was the whole problem.
C. The clock
15. When does the counter tick, and what does it end at?
Answer
On entering a vertex and on leaving it. With vertices it ends at , because every vertex is entered once and left once.
16. Write the running example’s timeline as brackets.
Answer
1 2 3 4 5 6 7 8 9 10 11 12
(u (v (y (x x) y) v) u) (w (z z) w)
17. What do you notice about the intervals?
Answer
They nest. , and is entirely disjoint from all of them.
D. The parenthesis theorem
18. State the parenthesis theorem in words.
Answer
For any two vertices, their discovery/finish intervals are either completely nested or completely disjoint — never partially overlapping. And nesting is exactly ancestry.
19. State it symbolically.
Answer
20. Why must it be true?
Answer
The search leaves a vertex only after every edge out of it has been examined, which means the whole search below has already returned. If it enters x while still inside u, it cannot leave u until it has left x. The call stack physically prevents interleaving — the same reason you cannot close a function call before closing the calls it made.
21. What does the theorem buy you computationally?
Answer
Ancestry becomes a constant-time test — two integer comparisons, not a walk up the tree.
E. Classifying an edge
22. Give the three-line classification rule for edge .
Answer
vwhite → tree edge (discovered through this edge).vgrey → back edge (the search is currently insidev, sovis an ancestor ofu).vblack → forward if (vis a descendant), else cross.
23. Why is every edge guaranteed to land in exactly one category?
Answer
Because the three rules are exhaustive over the three possible colours, and a vertex has exactly one colour when the edge is examined.
24. In the running example, classify x → v and justify with timestamps.
Answer
Back edge. v is grey, and — v’s interval contains x’s, so v is an ancestor.
25. Classify u → x and w → y.
Answer
u → x: forward — x is black and , so x is below u.
w → y: cross — y is black and , so y belongs to an earlier, different tree.
26. What kind of edge is a self-loop?
Answer
A back edge — a vertex is its own ancestor. It is a cycle of length one.
F. Back edges and cycles
27. Prove: if DFS finds a back edge, the graph has a directed cycle.
Answer
A back edge means v is an ancestor of u, so there is a path of tree edges . Append the back edge and you have a closed directed walk returning to v — a directed cycle.
28. Prove the converse: if the graph has a directed cycle, DFS finds a back edge.
Answer
Let v be the vertex of cycle that DFS discovers first. Every other vertex of is reachable from v along and is white at that moment, so all become descendants of v before v finishes. In particular the vertex p pointing into v along the cycle is a descendant, and when edge is examined v is still grey — a back edge.
29. State the combined theorem.
Answer
A directed graph is a DAG if and only if a DFS over it produces no back edges.
30. What does that theorem justify?
Answer
The correctness of DFS-based topological sort — and it is why that algorithm gets cycle detection for free rather than as an extra pass.
G. Undirected graphs
31. Which edge kinds can an undirected DFS produce?
Answer
Only tree edges and back edges. Forward and cross edges cannot occur.
32. Why can a forward or cross edge not occur?
Answer
An undirected edge is seen from whichever end the search reaches first, and that end defines the classification. If v is not white when examined from grey u, it cannot have finished — finishing v would have required examining this very edge from v’s side, which would have discovered u. So v is grey, and the edge is a back edge.
33. Say it as a slogan.
Answer
A forward edge would be an edge to a descendant the search “missed” on the way down — and in an undirected graph there is no way to miss it.
34. What trap does this create for cycle detection?
Answer
Every child sees its parent as grey, so a naive “grey neighbour means cycle” reports a cycle on every edge of every graph, including a two-vertex graph with one edge.
35. What is the fix, and what is the subtlety in the fix?
Answer
Ignore the edge you arrived on — and ignore it by edge identity, not by vertex. Skipping by vertex also silently drops parallel edges, which genuinely are a two-edge cycle.
H. What BFS leaves behind
36. State the BFS level property.
Answer
Every edge of the graph joins two vertices whose BFS levels differ by at most one.
37. Why can no neighbour of a level- vertex be at level ?
Answer
Every neighbour of u is discovered no later than the moment u is dequeued, so it would have been reached from u at level first. By symmetry it cannot be at either.
38. What is the first consequence?
Answer
It is the shortest-path guarantee restated: the level of v is the minimum number of edges from the source — which is why BFS and not DFS answers “fewest hops”.
39. What is the second consequence — the bipartiteness test?
Answer
Colour each level alternately. Every edge either crosses consecutive levels (fine) or joins two vertices within one level. An edge inside a level is an odd cycle, and an odd cycle is exactly what stops a graph being bipartite. So: BFS, then check for any edge with both endpoints on the same level.
40. Does DFS have an equivalent depth bound?
Answer
No. A DFS tree on a path graph of 5,000 vertices is 5,000 levels deep — exactly the depth that kills the recursive implementation.
I. Facts versus accidents
41. Which edge count is invariant when you change the start vertex?
Answer
The back-edge count — more precisely, whether at least one back edge exists. Back edges correspond to cycles, and cycles are a property of the graph.
42. Which counts are not invariant, and why?
Answer
The forward/cross split. Starting at w instead of u turns one forward + one cross into two cross edges. Forward and cross are artefacts of where you started and what order you listed neighbours — they describe this traversal, not the graph.
43. What do the real algorithms actually use?
Answer
| Algorithm | Uses |
|---|---|
| Directed cycle detection | does any back edge exist |
| Topological sort (DFS) | decreasing finish time |
| Kosaraju’s SCC | decreasing finish time, then DFS on the reversed graph |
| Tarjan’s SCC | discovery times plus lowest-reachable-discovery-time |
| Bridges / articulation points | lowest discovery time reachable via one back edge |
| Bipartite check | BFS levels — no edge within a level |
44. What is the pattern across that table?
Answer
Discovery time, finish time, and back edges. Learn those three and the rest of the graph-algorithm catalogue stops looking like a list of unrelated tricks.
J. Traps
45. What is the symptom of using a visited set where you need three colours?
Answer
A dependency resolver that rejects a perfectly valid build — cycles reported that do not exist.
46. Why is not simply “the order I finished in”?
Answer
It is a comparable number whose relative ordering encodes ancestry. Sorting by decreasing is a topological order; sorting by increasing is not.
47. Can you do this classification with BFS?
Answer
BFS on a directed graph does produce non-tree edges, but they do not correspond to ancestry in the same way, and there is no parenthesis theorem for BFS because there is no nesting. If a problem talks about back edges, it means DFS.
48. What goes wrong if you special-case and skip u == v?
Answer
Self-loops are back edges and cycles of length one. Skipping them silently declares cyclic graphs acyclic.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Traversal Trees & Edge Classification — the module
- Depth-First Search — Question Bank
- Topological Sort — the algorithm this lesson proves correct
Software engineering
Infrastructure & security
Computer science
Hardware & engineering