Which of the following statements regarding Breadth First Search (BFS) and…

GATE · 2025 · CS · Set 2 · Computer Science & IT

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 193 students.