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
  1. v white → tree edge (discovered through this edge).
  2. v grey → back edge (the search is currently inside v, so v is an ancestor of u).
  3. v black → forward if (v is 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
AlgorithmUses
Directed cycle detectiondoes any back edge exist
Topological sort (DFS)decreasing finish time
Kosaraju’s SCCdecreasing finish time, then DFS on the reversed graph
Tarjan’s SCCdiscovery times plus lowest-reachable-discovery-time
Bridges / articulation pointslowest discovery time reachable via one back edge
Bipartite checkBFS 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Traversal