During a DFS of a directed graph, you encounter an edge (u, v) where v is already discovered and is an ancestor of u in the DFS tree. What does this edge indicate?
AA cross edge — v was discovered in a different DFS subtree
BA forward edge — v is a descendant of u
CA back edge — and this means there is a cycle in the graph
DA tree edge — v has not been fully processed yet
An edge (u, v) where v is an ancestor of u in the DFS tree is a back edge. Back edges are the signature of cycles: you can traverse from v down to u (via the tree path) and then jump back to v (via the back edge), forming a cycle. This is why DFS-based cycle detection is straightforward: a back edge exists if and only if a cycle exists. Cross edges go between different subtrees; forward edges go to already-finished descendants; tree edges are the edges DFS actually traversed.
Question 2 Multiple Choice
You run DFS on a graph with V = 1,000 vertices and E = 50,000 edges. Which best describes the time complexity, and why?
AO(V²) — because DFS must compare every pair of vertices to decide if they're connected
BO(V + E) — because each vertex is processed once and each edge is examined once
CO(E log V) — because the DFS tree requires sorting edges by discovery order
DO(V × E) — because each vertex may trigger exploration of all edges
DFS runs in O(V + E): each vertex is discovered and finished exactly once (O(V) total), and each edge is examined exactly once when DFS processes its source vertex (O(E) total). There is no sorting, no repeated work, and no nested iteration over all vertices per edge. O(V + E) is optimal for graph traversal — you cannot process a graph without visiting every vertex and edge at least once.
Question 3 True / False
In a DFS tree, if vertex v is a descendant of vertex u, then u's discovery time is less than v's discovery time, which is less than v's finish time, which is less than u's finish time.
TTrue
FFalse
Answer: True
This is the parenthesis theorem for DFS timestamps. Because DFS recurses into v's subtree while u is still on the stack, u's interval [disc(u), fin(u)] completely contains v's interval [disc(v), fin(v)]. This nesting property is the key structural insight behind topological sorting (vertices finish in reverse topological order) and strongly connected component algorithms (Kosaraju's and Tarjan's both exploit finish-time ordering).
Question 4 True / False
DFS is preferred over BFS when you need to find the shortest path between two vertices in an unweighted graph.
TTrue
FFalse
Answer: False
BFS, not DFS, finds shortest paths in unweighted graphs. BFS explores vertices level by level (by hop count), so the first time it reaches a vertex is via the shortest path. DFS dives deep immediately and may reach a vertex via a long, indirect path long before it would try a shorter one. The file mentions this directly as a common misconception. DFS's strength lies in cycle detection, topological sort, and SCC — not shortest paths.
Question 5 Short Answer
Why do DFS discovery and finish timestamps enable topological sorting of a directed acyclic graph?
Think about your answer, then reveal below.
Model answer: In a DAG, if there is a directed edge from u to v (u must come before v), DFS will always finish u after it finishes v — because DFS fully explores v's subtree before returning to finish u. So processing vertices in reverse finish-time order gives a valid topological ordering: every vertex appears before the vertices it has edges to.
The finish-time ordering works because the DFS parenthesis structure captures 'comes before' relationships: if u depends on nothing that v depends on, u finishes later. Reversing this gives the topological order. This is why a single DFS pass suffices for topological sort — the timestamps implicitly encode the dependency ordering without any additional work.