Which of the following statements regarding Breadth First Search (BFS) and…
PYQ GATE 2025
Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?
- A.
A DFS tree of 𝐺 is a Shortest Path tree of 𝐺.
- B.
Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
- C.
If (𝑢, 𝑣) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex 𝑠 to 𝑢 and 𝑣 in the BFS tree are within ±1 of each other.
- D.
Both BFS and DFS can be used to find the connected components of G.
Attempted by 230 students.
Sign up free to check your answer
Sign up freeLoading lesson…

