Questions: Depth-First Search: Implementation and Applications

Question 1

While running DFS on a directed graph, you encounter an edge from node u to node v, where v has already been discovered but not yet finished. What does this indicate?

• A. A cross edge — v is in a different DFS tree and was finished in a previous call
• B. A forward edge — v is a descendant of u that was already visited
• C. A back edge — v is an ancestor of u on the current DFS path, proving a cycle exists
• D. A tree edge — v is being discovered for the first time through u

Answer: (C)

A node that has been discovered but not yet finished is still on the call stack — it is an ancestor of the current node in the ongoing DFS. An edge to such a node goes 'backward' up the current path, creating a cycle. This is the definition of a back edge. Cross edges go to nodes in different DFS subtrees that have already been completed (finished). Forward edges go to descendants previously discovered through another path. Tree edges go to newly discovered nodes. Only back edges — edges to in-progress ancestors — prove a cycle exists.

Question 2

After running DFS on a DAG with 5 nodes, finish times are: A=8, B=4, C=6, D=2, E=10. Which is the valid topological ordering?

• A. A, B, C, D, E (alphabetical order)
• B. E, A, C, B, D (reverse finish time order)
• C. D, B, A, C, E (ascending finish time order)
• D. D, B, C, A, E (discovery time order)

Answer: (B)

Topological sort outputs nodes in reverse order of finish times — nodes that finish last come first. Sorting by finish time descending: E(10), A(8), C(6), B(4), D(2) → E, A, C, B, D. This works because in a DAG, if there is an edge from u to v, u always finishes after v (v must complete before DFS backtracks to finish u). Reversing finish times therefore places every node before the nodes it has edges to. Option C lists ascending finish order — the exact reverse of the correct answer.

Question 3

If node B's discovery-to-finish interval falls entirely within node A's discovery-to-finish interval in a DFS, then B is a descendant of A in the DFS tree.

• T. True
• F. False

Answer: True

This is the parenthesis theorem of DFS. The discovery and finish times of any node form an interval, and for any two nodes, these intervals are either completely nested (one is a descendant of the other) or completely disjoint (neither is a descendant of the other). If B's interval [d(B), f(B)] is fully contained within A's interval [d(A), f(A)], B was discovered and finished entirely during A's recursive call — which is exactly what it means to be a descendant in the DFS tree.

Question 4

In an undirected graph, any edge discovered during DFS that leads to an already-visited node (other than the direct parent) indicates a cycle.

• T. True
• F. False

Answer: True

In an undirected graph, DFS produces only tree edges and back edges — there are no cross or forward edges. Any edge to a non-parent visited node goes 'backward' to an ancestor, creating a cycle. Note this differs from directed graphs: in directed DFS, edges to already-finished nodes (cross or forward edges) do not indicate cycles. Only back edges (to ancestors still on the stack) do. The undirected case is cleaner: any non-parent visited neighbor signals a cycle.

Question 5

Why does reversing the finish-time ordering of DFS produce a valid topological sort of a DAG? What property of DFS makes this work?

Model answer: In a DAG, if there is a directed edge from u to v, then v must be fully explored before DFS can return from u — meaning v always finishes before u, giving v a smaller finish time. Therefore u has a larger finish time than v. Reversing finish times places u before v in the sorted order, which is exactly the topological requirement: every node appears before the nodes it has edges to. Because the graph has no cycles (no back edges), this relationship holds consistently for all edges.

The DFS finish time encodes when a node's entire downstream subtree has been resolved. A node with a large finish time is one whose dependents were all finished before it — they came first in exploration, last in time. Placing large-finish-time nodes first in the output means placing 'upstream' nodes before 'downstream' ones. The absence of back edges (the DAG property) is what makes this globally consistent: no edge ever points from a low-finish node to a high-finish node, so no contradiction arises.