During DFS on a directed graph, you visit node A, then B, then C — and from C you find an edge back to A, which is still on the current recursion stack. What type of edge is this, and what does it indicate?
AA tree edge — it is part of the DFS spanning tree
BA back edge — it indicates a cycle in the directed graph
CA cross edge — it connects two unrelated branches
DA forward edge — it points to a descendant already fully processed
A back edge points from a node to one of its ancestors in the current DFS recursion stack. Finding a back edge proves the graph has a directed cycle (A → B → C → A). Cross edges and forward edges point to already-visited nodes that are not current ancestors, so they do not indicate cycles in directed graphs.
Question 2 True / False
DFS is a good algorithm for finding the shortest path between two nodes in an unweighted graph.
TTrue
FFalse
Answer: False
DFS follows a single path as deep as possible before backtracking. It will find *a* path, but not necessarily the shortest one. BFS (breadth-first search) finds shortest paths in unweighted graphs because it explores all nodes at distance 1 before any at distance 2, guaranteeing the first time it reaches the target is via the shortest route.
Question 3 Short Answer
What is the time complexity of DFS on a graph with V vertices and E edges, and why?
Think about your answer, then reveal below.
Model answer: O(V + E). Each vertex is visited exactly once (O(V)), and each edge is examined exactly once when processing the vertex it originates from (O(E)).
DFS marks each vertex visited on first encounter and never revisits it. When processing a vertex, it checks all outgoing edges to find unvisited neighbors. Across all vertices, the total number of edge checks equals the total number of edges E. So the combined work is proportional to V + E, regardless of graph structure.