Consider a directed graph πΊ = (π,πΈ), where π is the finite set of verticesβ¦
GATE Β· 2026 Β· DA Β· Data Science & AI
Consider a directed graph πΊ = (π,πΈ), where π is the finite set of vertices and πΈ is the set of directed edges between the vertices. πΊ may contain cycles but there is no self-loop. Further, πΊ may not be strongly connected. Let πΊπ be the graph obtained by reversing the directions of all the edges in πΊ without changing the set of vertices. Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex π£ of a graph visits only the reachable vertices from π£ in that graph. Which of the following statements must always be true, regardless of the structure of πΊ?
- A.
If π’ is a reachable vertex in the BFS of πΊπ from π£, then π’ is also a reachable vertex in the DFS of πΊ from π£.
- B.
In πΊπ , the BFS traversal from π£ will visit exactly the same set of vertices as the DFS from π£ in πΊ.
- C.
The order of vertices visited in the BFS of πΊπ from π£ is the reverse of the order of vertices visited in the DFS of πΊ from π£.
- D.
If π’ is a reachable vertex in the DFS of πΊ from π£, then π£ is also a reachable vertex in the BFS of πΊπ from π’.
Attempted by 15 students.
Sign up free to check your answer
Sign up freeLoading lessonβ¦