Graph Traversals GATE 2026 Question #10268 with Solution

GATE 2026 · session-8

Programming, Data Structures and AlgorithmsGraph TraversalsmediumMCQ2 marks

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\)?

AIf \(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\).BIn \(G^R\), the BFS traversal from \(v\) will visit exactly the same set of vertices as the DFS from \(v\) in \(G\).CThe 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\).DIf \(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\).

Save your progress

Related Programming, Data Structures and Algorithms PYQs

GATE 2026 · session-8

Consider that the quick sort algorithm is used to sort an array of \(n\) distinct randomly ordered elements. In every call, the pi…

GATE 2026 · session-8

Consider the given Python program. def append_to_lst(val, lst=[]): lst.append(val) return lst print(append_to_lst(1)) print(appe…

GATE 2026 · session-8

You are given the following Pre-order and In-order traversals of a Binary Tree \(T\) with nodes E, F, G, P, Q, R, S. Pre-order: P…

GATE 2026 · session-8

Let \(A\) be a sorted array containing 1000 distinct integers. You perform a recursive binary search on \(A\) to find an element \…

GATE 2026 · session-8

A recursive function in Python is given. def mystery(n): if n <= 0: return 1 else: return mystery(n-1) + mystery(n-2) Now, consi…

GATE 2026 · session-8

Consider the problem of sorting the given array in ascending order: \(P = [1, 2, 3, 5, 4]\) Consider two sorting algorithms Bubb…

Saved progressKeep answers, mock results and completion history across devices.

Adaptive practiceGet questions matched to your recent accuracy and difficulty level.

Bookmarks and notesBuild a personal revision list and record why a question was difficult.

Performance insightsSee weak subjects, accuracy trends, streaks and exam readiness.

Related Programming, Data Structures and Algorithms PYQs

Turn practice into measurable progress