Q19

MSQ1 mark

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 $G$ is a Shortest Path tree of $G$ .

(B)

Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.

(C)

If $(u, v)$ is a non-tree edge of $G$ with respect to a BFS tree, then the distances from the source vertex $s$ to $u$ and $v$ in the BFS tree are within $\pm 1$ of each other.

(D)

Both BFS and DFS can be used to find the connected components of $G$ .

Loading…