techtud

Question

Let G is a graph with n vertices and m edges. Consider following statements : i. In DFS traversal, number of tree edges produced is independent of selection of starting vertex. ii. In BFS traversal, number of tree edges produced is independent of selection of starting vertex. iii. In DFS traversal, number of tree edges produced is dependent of selection of starting vertex. iv. In DFS traversal, number of tree edges produced is dependent of selection of starting vertex.

(A) Only statements (i) and (ii) are correct
(B) Only statements (ii) and (iii) are correct
(C) Statements (ii) and (iv) both are wrong
(D) None of these

Comments

In both traversal initial vertex matters.

statements are wrongly typed.

---

Yes that what i was thinking but not for undirected graph right??

---

How the selection of initial vertex matters for both dfs and bfs ? please explain

As you said both traversal matters then option D may be the answer for this question.

---

I think the edges would be same in both DFS and BFS tree  i.e (N-1) becoz a tree with N vertices has (N-1) edges,so option (A) Is correct ,but the height of both DFS and BFS  tree depends on starting vertex