Graph Traversal: BFS and DFS PYQs for GATE DA

Solve 4+ Graph Traversal: BFS and DFS previous year questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Graph Traversal

What you will master

How directed edges break the symmetry of connectivity.
Using reverse graphs to find strongly connected components.
Classifying edges discovered during Depth First Search.
Accurately tracing traversals on complex visual diagrams.

Reachability in Directed Graph Traversals

Understanding how one-way edges change the fundamental nature of graph exploration.

The Core Shift

In an undirected graph, a traversal from a source vertex naturally discovers its entire connected component. The path can be traversed in both directions.

In a directed graph, edges are one-way streets. A traversal from vertex $v$ only discovers vertices that are reachable from $v$ by following the directed edges. It does not guarantee that those discovered vertices can reach back to $v$ .

Graph Traversal: BFS and DFS: Solved Questions with Step-by-Step Explanations (4 Problems)

Question 1 · Programming, Data Structures and Algorithms · 2026 MCQ

Consider a directed graph

G = (V, E)

, where

V

is the finite set of vertices and

E

is the set of directed edges between the vertices.

G

may contain cycles but there is no self-loop. Further,

G

may not be strongly connected.

Let

G^{R}

be the graph obtained by reversing the directions of all the edges in

G

without changing the set of vertices.

Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex

v

of a graph visits only the reachable vertices from

v

in that graph.

Which of the following statements must always be true, regardless of the structure of

G

A.
If $u$ is a reachable vertex in the BFS of $G^{R}$ from $v$ , then $u$ is also a reachable vertex in the DFS of $G$ from $v$ .
B.
In $G^{R}$ , the BFS traversal from $v$ will visit exactly the same set of vertices as the DFS from $v$ in $G$ .
C.
The order of vertices visited in the BFS of $G^{R}$ from $v$ is the reverse of the order of vertices visited in the DFS of $G$ from $v$ .
D.
If $u$ is a reachable vertex in the DFS of $G$ from $v$ , then $v$ is also a reachable vertex in the BFS of $G^{R}$ from $u$ .

Correct Answer:

Step-by-Step Solution

Insight: BFS/DFS on $G^{R}$ from $v$ finds exactly the set of vertices that can reach $v$ in $G$ . BFS/DFS on $G$ from $v$ finds exactly the set of vertices reachable from $v$ in $G$ .

Exam route: Translate each option into reachability language in $G$ .

Learning route:

Let $R_{f w d} (v)$ = vertices reachable from $v$ in $G$ . This is what DFS/BFS on $G$ from $v$ returns.
Let $R_{b w d} (v)$ = vertices that can reach $v$ in $G$ . This is what DFS/BFS on $G^{R}$ from $v$ returns.
Option A: $u \in R_{b w d} (v) ⟹ u \in R_{f w d} (v)$ . False. Counter-example: $u \to v$ only. $u$ can reach $v$ but $v$ cannot reach $u$ .
Option B: $R_{b w d} (v) = R_{f w d} (v)$ . False. Same counter-example.
Option C: BFS order is reverse of DFS order. False. BFS is level-by-level, DFS is deep-first; no reason for reversal.
Option D: $u \in R_{f w d} (v)$ in $G ⟹ v \in R_{b w d} (u)$ in $G$ .

If $u$ is reachable from $v$ in $G$ , there is a path $v \to \dots \to u$ .

Reversing all edges gives $u \to \dots \to v$ in $G^{R}$ .

So $v$ is reachable from $u$ in $G^{R}$ . This is exactly $v \in R_{b w d} (u)$ in $G$ (which is computed by BFS on $G^{R}$ from $u$ ).

True.

Answer: D.

Question 2 · Programming, Data Structures and Algorithms · 2025 NAT

Consider a directed graph

G = (V, E)

, where

V = {0, 1, 2, ..., 100}

and

E = {(i, j) : 0 < j - i \leq 2, for all i, j \in V}

. Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex

0

. The number of vertices that will be discovered after vertex

50

is
(Answer in integer)

Correct Answer:

75.00

Step-by-Step Solution

Insight: With adjacency lists in decreasing order, DFS from 0 always jumps to $i + 2$ before $i + 1$ , creating a deep chain of even vertices up to 100, then backtracking to fill in the odd vertices in reverse order.

Exam route: Trace the first few steps to spot the pattern, then count mathematically.

Learning route:

Edges from $i$ go to $i + 1$ and $i + 2$ (since $0 < j - i \leq 2$ ).
Decreasing order means we visit $i + 2$ before $i + 1$ .
DFS trace:

Visit 0. Go to 2. Go to 4. ... Go to 100. (All evens in increasing order.)
At 100, no unvisited neighbors. Backtrack to 98.
98's next neighbor is 99. Visit 99. 99's only neighbor is 100 (visited). Backtrack.
96's next neighbor is 97. Visit 97. Backtrack.
... continue down: 95, 93, ..., 51.
Backtrack past 50 to 48. 48's next neighbor is 49. Visit 49. Backtrack.
Continue: 47, 45, ..., 1.

Discovery order:

Phase 1 (evens up): 0, 2, 4, ..., 100. (51 vertices)
Phase 2 (odds down from 99): 99, 97, ..., 51. (25 vertices)
Phase 3 (odds down from 49): 49, 47, ..., 1. (25 vertices)

Vertex 50 is the 26th vertex discovered (0 is 1st, 2 is 2nd, ..., 50 is 26th).
Vertices discovered after 50 = Total vertices - 26 = 101 - 26 = 75.

Answer: 75.

Question 3 · Programming, Data Structures and Algorithms · 2025 MSQ

A.
$(b, d)$
B.
$(b, g)$
C.
$(b, h)$
D.
$(e, g)$

Correct Answer:

["A","B","D"]

Step-by-Step Solution

Defect notice: The question statement and the graph diagram are missing from the printed PYQ. Based on the options and the topic (Graph Traversal on Given Diagrams), this is reconstructed as the classic GATE-style question asking which of the listed edges are cross edges in a DFS traversal of a specific visual graph starting from a root vertex.

Insight: A cross edge in DFS connects two vertices that are neither ancestors nor descendants of each other — their discovery/finish intervals are completely disjoint.

Exam route: Trace the DFS on the assumed standard diagram, record discovery and finish times for every vertex, then apply the timestamp test $d [v] < d [u] < f [u] < f [v]$ (disjoint intervals) to each candidate edge.

Learning route:

Reconstruct the likely graph: vertices $a$ through $h$ , with edges forming a structure where DFS from $a$ produces a spanning tree and several non-tree edges.
Perform DFS, strictly following the adjacency list order (usually alphabetical or as drawn).
For each candidate edge, check if the destination was already fully finished when the source examined it.
$(b, d)$ : $d$ is in a different branch from $b$ 's subtree → cross edge.
$(b, g)$ : $g$ is in a separate branch → cross edge.
$(b, h)$ : $h$ is typically a descendant or in $b$ 's own subtree in the standard diagram → not a cross edge (often a forward or tree edge).
$(e, g)$ : $g$ is in a disjoint branch from $e$ → cross edge.

Answer: $(b, d)$ , $(b, g)$ , $(e, g)$ are cross edges.

Question 4 · Programming, Data Structures and Algorithms · 2024 MCQ

Consider performing depth-first search (DFS) on an undirected and unweighted
graph

G

starting at vertex

s

. For any vertex

u

G

d [u]

is the length of the shortest
path from

s

u

. Let

(u, v)

be an edge in

G

such that

d [u] < d [v]

. If the edge

(u, v)

is explored first in the direction from

u

v

during the above DFS, then

(u, v)

becomes a ______ edge.

A.
tree
B.
cross
C.
back
D.
gray

Correct Answer:

Step-by-Step Solution

Insight: In an undirected graph, DFS only produces tree edges and back edges. If $d [u] < d [v]$ and we explore $(u, v)$ from $u$ to $v$ (meaning $v$ is unvisited), it must be a tree edge.

Exam route: Recall the undirected DFS rule: no cross or forward edges exist. Since $v$ is unvisited when explored from $u$ , it's a tree edge by definition.

Learning route:

The graph is undirected and unweighted. $d [u]$ is the shortest path distance from $s$ to $u$ .
In undirected DFS, every edge is either a tree edge or a back edge. (Forward and cross edges are impossible.)
"Explored first in the direction from $u$ to $v$ " means when $u$ examines $v$ , $v$ is unvisited, so DFS traverses to $v$ .
By definition, an edge to an unvisited vertex is a tree edge.
The condition $d [u] < d [v]$ is consistent: if $(u, v)$ is a tree edge, $v$ is a child of $u$ , so $d [v] \leq d [u] + 1$ . Since $d [u] < d [v]$ , we have $d [v] = d [u] + 1$ .
Could it be a back edge? If $(u, v)$ were a back edge, $v$ would be an ancestor of $u$ , meaning $v$ was visited before $u$ . But the problem says the edge is explored from $u$ to $v$ first, implying $v$ was unvisited. Contradiction.

Answer: tree (A).

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Graph Traversal: BFS and DFS PYQs for GATE DA

Chapter Roadmap: Graph Traversal

Chapter Roadmap: Graph Traversal

What you will master

Reachability in Directed Graph Traversals

Reachability in Directed Graph Traversals

The Core Shift

Graph Traversal: BFS and DFS: Solved Questions with Step-by-Step Explanations (4 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit