Discussion
Let \(G\) be a directed graph and \(T\) a depth first search (DFS) spanning tree in \(G\) that is rooted at a vertex \(v\). Suppose \(T\) is also a breadth first search (BFS) tree in \(G\), rooted at \(v\). Which of the following statements is/are TRUE for every such graph \(G\) and tree \(T\) ?
Answer: C
The statement that always holds is There are no forward-edges in \(G\) with respect to the tree \(T\).
A forward edge goes from a vertex u to a descendant w of u that is not its child, so w is at least two levels below u in T. In a BFS tree, every edge (u, w) satisfies depth(w) \(\le\) depth(u) + 1, because BFS reaches w no later than one step after u. Since T is a BFS tree, such an edge is impossible.
The other statements can fail. A back edge, such as an edge from a child back to v, is allowed. A cross edge is possible too: with edges v\(\to\)a, v\(\to\)b and b\(\to\)a, the tree {v\(\to\)a, v\(\to\)b} is both a DFS and a BFS tree, and b\(\to\)a is a cross edge. Those examples also show G can have edges outside T.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development