Question:
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\)?
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\)?
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\)?
Show Hint
Reversing every edge on a path from v to u in G turns it into a path from u to v in G^R.
Updated On: Jul 22, 2026
- 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\).
- In \(G^R\), the BFS traversal from \(v\) will visit exactly the same set of vertices as the DFS from \(v\) in \(G\).
- 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\).
- 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\).
Show Solution
Verified By Collegedunia
The Correct Option is D
Solution and Explanation
Step 1: Translate reachability into a path statement.
Saying "\(u\) is reachable from \(v\) in \(G\)" means there is a directed path \(v \to \cdots \to u\) using edges of \(G\), each edge pointing forward along the path. A BFS or DFS from \(v\) visits exactly the set of vertices reachable from \(v\), by the assumption given in the question.
Step 2: Understand what reversing edges does to a path.
If there is a directed path from \(v\) to \(u\) in \(G\), then reversing every edge on that path, which is exactly what forming \(G^R\) does to every edge of \(G\), turns it into a directed path from \(u\) to \(v\) in \(G^R\), with the same vertices visited in the opposite order. So: \(u\) reachable from \(v\) in \(G\) if and only if \(v\) reachable from \(u\) in \(G^R\).
Step 3: Check option (D) against this fact.
Option (D) says: if \(u\) is reachable from \(v\) by DFS in \(G\) (i.e. there is a path \(v \to u\) in \(G\)), then \(v\) is reachable from \(u\) by BFS in \(G^R\) (i.e. there is a path \(u \to v\) in \(G^R\)). This is exactly the fact proven in Step 2, so option (D) must always be true, regardless of how \(G\) is shaped, whether it has cycles, or whether it is strongly connected.
Step 4: Rule out the other options with a small counterexample.
Take a simple graph with edges \(v \to a\) and \(b \to v\), so \(a\) is reachable from \(v\) in \(G\), but nothing lies on a path from \(v\) toward \(b\) in \(G\). In \(G^R\) the edges become \(a \to v\) and \(v \to b\), so from \(v\), BFS in \(G^R\) reaches \(b\), not \(a\).
Option (A) fails: reachable sets from the same vertex \(v\) in \(G\) and in \(G^R\) can be entirely different (here \(\{v,a\}\) versus \(\{v,b\}\)), so a vertex reachable in BFS of \(G^R\) from \(v\) need not be reachable via DFS of \(G\) from that same \(v\).
Option (B) fails for the same reason: the reachable set from \(v\) in \(G\) is \(\{v, a\}\), while the reachable set from \(v\) in \(G^R\) is \(\{v, b\}\); these are different sets, so BFS of \(G^R\) from \(v\) does not visit the same vertices as DFS of \(G\) from \(v\).
Option (C) fails too: since the visited sets can differ entirely, there is no meaningful "reverse of the order" relationship between them in general, and even when the sets coincide, BFS and DFS can visit vertices in different orders.
Final Answer:
Option (D) is the statement that must always be true.
Saying "\(u\) is reachable from \(v\) in \(G\)" means there is a directed path \(v \to \cdots \to u\) using edges of \(G\), each edge pointing forward along the path. A BFS or DFS from \(v\) visits exactly the set of vertices reachable from \(v\), by the assumption given in the question.
Step 2: Understand what reversing edges does to a path.
If there is a directed path from \(v\) to \(u\) in \(G\), then reversing every edge on that path, which is exactly what forming \(G^R\) does to every edge of \(G\), turns it into a directed path from \(u\) to \(v\) in \(G^R\), with the same vertices visited in the opposite order. So: \(u\) reachable from \(v\) in \(G\) if and only if \(v\) reachable from \(u\) in \(G^R\).
Step 3: Check option (D) against this fact.
Option (D) says: if \(u\) is reachable from \(v\) by DFS in \(G\) (i.e. there is a path \(v \to u\) in \(G\)), then \(v\) is reachable from \(u\) by BFS in \(G^R\) (i.e. there is a path \(u \to v\) in \(G^R\)). This is exactly the fact proven in Step 2, so option (D) must always be true, regardless of how \(G\) is shaped, whether it has cycles, or whether it is strongly connected.
Step 4: Rule out the other options with a small counterexample.
Take a simple graph with edges \(v \to a\) and \(b \to v\), so \(a\) is reachable from \(v\) in \(G\), but nothing lies on a path from \(v\) toward \(b\) in \(G\). In \(G^R\) the edges become \(a \to v\) and \(v \to b\), so from \(v\), BFS in \(G^R\) reaches \(b\), not \(a\).
Option (A) fails: reachable sets from the same vertex \(v\) in \(G\) and in \(G^R\) can be entirely different (here \(\{v,a\}\) versus \(\{v,b\}\)), so a vertex reachable in BFS of \(G^R\) from \(v\) need not be reachable via DFS of \(G\) from that same \(v\).
Option (B) fails for the same reason: the reachable set from \(v\) in \(G\) is \(\{v, a\}\), while the reachable set from \(v\) in \(G^R\) is \(\{v, b\}\); these are different sets, so BFS of \(G^R\) from \(v\) does not visit the same vertices as DFS of \(G\) from \(v\).
Option (C) fails too: since the visited sets can differ entirely, there is no meaningful "reverse of the order" relationship between them in general, and even when the sets coincide, BFS and DFS can visit vertices in different orders.
Final Answer:
Option (D) is the statement that must always be true.
Was this answer helpful?
0
0
Top GATE DA Data Science and Artificial Intelligence Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to 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 to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions
Top GATE DA Data Structures and Algorithms Questions
Given the Python code:
- Consider that the quick sort algorithm is used to sort an array of \(n\) distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.
Let \(T(n)\) denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.
Which of the following recurrence relations correctly represents \(T(n)\) in this scenario? - 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 Q S E R F G
In-order: S Q E P F R G
Which of the following statements is/are true about the Binary Tree \(T\)? - Let \(A\) be a sorted array containing 1000 distinct integers. You perform a recursive binary search on \(A\) to find an element \(y\). Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than \(y\).
The maximum number of comparisons that may have to be performed if \(y\) is not an element of \(A\) is __________. (Answer in integer)
Top GATE DA Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to 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 to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions