DFS Applications MCQs: 12 Solved Questions with Explanations

DFS questions become harder when the examiner moves beyond the stack to recursion depth, forest edges, timestamps, cross edges, articulation points and low-link values. The same traversal can test ordering, component structure or the effect of deleting a vertex or edge.

Attempt each item yourself before reading its explanation, without guessing from the options. Draw the recursion stack for traversals, write both d[u] and f[u] for timestamps, and classify tree and back edges before calculating low values. The Coding & DSA Courses for Placements page and Coding for Placements: C, C++, Java, Python course provide the wider practice route.

DFS rules and a fixed trace

DFS uses an explicit LIFO stack or the call stack. Mark a vertex when it is pushed or its call begins, finish every unvisited neighbour, then pop it. A vertex finishes only after every reachable unvisited neighbour below it has finished. Adjacency lists cost O(V + E); a matrix forces O(V^2) row scans. Neighbour order controls preorder, so DFS order is not unique.

For the undirected graph, use V = {A, B, C, D, E, F, G, H} and E = {AB, AC, BD, BE, EF, FG, CG, CH}. From A, scanning alphabetically, preorder is A, B, D, E, F, G, C, H. The stack is [A], [A,B], [A,B,D], [A,B], [A,B,E], [A,B,E,F], [A,B,E,F,G], [A,B,E,F,G,C], [A,B,E,F,G,C,H], then pops H, C, G, F, E, B, A.

Tree edges are AB, BD, BE, EF, FG, GC, CH; AC is the back edge from C to ancestor A. Pairs are A(1,16), B(2,15), D(3,4), E(5,14), F(6,13), G(7,12), C(8,11), H(9,10). Thus d[B]=2 < d[C]=8 < f[C]=11 < f[B]=15. Use Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step for a concept rebuild.

DFS MCQs 1-2: stack behaviour and the visited set

Question 1

Depth First Search graph search algorithm uses ______ data structure for its implementation.

Options:

• A. Stack

• B. tree

• C. Dequeue

• D. Queue

Correct answer: A. Stack.

DFS is LIFO. In the fixed trace, the full finish order is D,H,C,G,F,E,B,A. An iterative implementation uses an explicit stack; recursion uses the call stack. FIFO drives BFS.

Question 2

In a Depth First Search (DFS) traversal, what is the purpose of marking nodes as visited?

Options:

• A. To avoid revisiting nodes and prevent infinite loops

• B. To keep track of the parent node

• C. To prioritize nodes

• D. To find the shortest path

Correct answer: A. To avoid revisiting nodes and prevent infinite loops.

Without visited marks, A-B-E-F-G-C-A repeats. Marking A makes C-A a back edge. Parent tracking and shortest paths are separate.

DFS MCQs 3-4: representation cost and forest arithmetic

Question 3

Let \(G\) be a graph with \(n\) vertices and \(m\) edges. What is the tightest upper bound on the running time of Depth First Search on \(G\), when \(G\) is represented as an adjacency matrix?

Options:

• A. \(\theta (n)\)

• B. \(\theta (n + m)\)

• C. \(\theta (n^2)\)

• D. \(\theta (m^2)\)

Correct answer: C. \(\theta (n^2)\).

An n x n matrix may inspect n^2 cells when sparse. At n=8, that is 64; lists for m=8 scan 2m=16 incidences.

Question 4

The number of edges present in the forest generated by the DFS traversal of an undirected graph 𝐺 with 100 vertices is 40. The number of connected components in 𝐺 is _________

Answer format: numerical response.

Correct answer: 60.

Forest edges equal n-c. Thus 40=100-c, so c=60. A concrete check is 40 two-vertex trees plus 20 isolated vertices: 40 edges and 60 components.

DFS MCQs 5-6: connected components and guarantees DFS does not give

Question 5

Connected components in a graph can be found using which graph traversal algorithm?

Options:

• A. DFS

• B. BFS

• C. Both DFS and BFS

• D. Neither DFS nor BFS

Correct answer: C. Both DFS and BFS.

Both exhaust one reachable set. For {12,23,45} plus isolated 6, starts 1,4,6 reveal {1,2,3}, {4,5}, {6} using either frontier.

Question 6

Which of the following statements about DFS are correct? A. It can detect cycles in a graph B. It can be used to find connected components. C. It works for both directed and undirected graph. D. Guarantees shortest path in unweighted graphs. Choose the correct answer from the options given below:

Options:

• A. A, B, C Only

• B. A, B, C, D

• C. C, D Only

• D. B, C Only

Correct answer: A. A, B, C Only.

A, B and C hold. With {SA,AT,SB,BC,CT}, DFS can give S-B-C-T, length 3, versus S-A-T, length 2. Directed cycles use active calls; undirected checks exclude parents.

DFS MCQs 7-8: edge classes and finish times

Question 7

Let \(G\) be a simple undirected graph. Let \(T_D\) be a depth first search tree of \(G\). Let \(T_B\) be a breadth first search tree of \(G\). Consider the following statements. (I) No edge of \(G\) is a cross edge with respect to \(T_D\). (A cross edge in \(G\) is between two nodes neither of which is an ancestor of the other in \(T_D\).) (II) For every edge \((u,v)\) of \(G\), if \(u\) is at depth \(i\) and \(v\) is at depth \(j\) in \(T_B\), then \(|𝑖 − 𝑗| = 1\). Which of the statements above must necessarily be true?

Options:

• A. I only

• B. II only

• C. Both I and II

• D. Neither I nor II

Correct answer: A. I only.

Undirected DFS non-tree edges join ancestors and descendants, so I holds. In triangle {rx,ry,xy}, BFS puts x,y at depth 1; xy has |1-1|=0, disproving II.

Question 8

A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph ?

Options:

• A. d[u] < d[v]

• B. d[u] < f[v]

• C. f[u] < f[v]

• D. f[u] > f[v]

Correct answer: D. f[u] > f[v].

For {A->B,A->C,B->D,C->D}, DFS gives A(1,8), B(2,5), D(3,4), C(6,7). Edges satisfy 8>5, 8>7, 5>4, 7>4; reversal needs a back edge.

DFS MCQs 9-10: topological order and articulation roots

Question 9

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: Depth first search can be used to perform a topological sort of a directed acyclic graph. Reason R: A topological sort of a directed acyclic graph G = (V, E) is a linear ordering of its vertices such that if G contains an edge (u, v) then u appears before v in the ordering. In the light of the above statements, choose the most appropriate answer from the options given below:

Options:

• A. Both A and R are correct and R is the correct explanation of A

• B. Both A and R are correct but R is NOT the correct explanation of A

• C. A is correct but R is not correct

• D. A is not correct but R is correct

Correct answer: B. Both A and R are correct but R is NOT the correct explanation of A.

R defines the output, not the mechanism. Decreasing finishes A(8),C(7),B(5),D(4) give A,C,B,D because every DAG edge has f[u]>f[v].

Question 10

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?

Options:

• A. Root of T can never be an articulation point in G.

• B. Root of T is an articulation point in G if and only if it has 2 or more children.

• C. A leaf of T can be an articulation point in G.

• D. If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Correct answer: B. Root of T is an articulation point in G if and only if it has 2 or more children.

For {RX,RY}, root R has two children; removing it separates X,Y. One child leaves one subtree. A leaf cannot separate descendants.

DFS MCQs 11-12: low-link values and bridges

Question 11

The function low [u] in DFS traversal is used to

Options:

• A. Store the lowest sequence number reachable from u or its descendants

• B. Store the highest sequence number of a vertex reachable from u

• C. Keep track of the number of times u has been visited

• D. Count the number of connected components in the graph

Correct answer: A. Store the lowest sequence number reachable from u or its descendants.

low[u] is the smallest discovery reachable using subtree edges and at most one back edge. Here C-A gives low[C]=low[B]=1; F-D gives low[F]=low[E]=low[D]=4.

Question 12

In the context of finding bridges in a connected undirected graph using Depth-First-Search (DFS), an edge (u, v) is identified as a bridge. Which of the following conditions hold true? (Here pre [ ] holds pre-order traversal numbering of the node. low [ ] holds the lowest pre-order of any vertex connected to node.)

Options:

• A. low [v] < pre [u]

• B. low [v] > pre [u]

• C. low [v] < low [u]

• D. pre [v] == pre [u]

Correct answer: B. low [v] > pre [u].

For tree edge (u,v), the inequality means no ancestral bypass. Thus C-D is a bridge since 4>3; B-C is not since 1<=2, via C-A.

DFS traps and the next practice step

Under timed conditions, draw stack; mark on entry; assign discovery before and finish after scanning. Count disconnected roots; calculate low upward. Reproduce 40=100-c and low[D]=4>pre[C]=3 unaided.

Solve Graph MCQs: 10 Solved BFS, DFS, Connectivity (GATE). Continue with DFS Applications PYQ Questions for a larger topic-specific set.

Short version: DFS is stack-driven. Entry, exit and low-link invariants make component, topological-order, articulation-point and bridge questions traceable.