Let ๐บ be a directed graph and ๐ a depth first search (DFS) spanning tree inโฆ
GATE ยท 2024 ยท CS ยท Set 1 ยท Computer Science & IT
Let ๐บ be a directed graph and ๐ a depth first search (DFS) spanning tree in ๐บ that is rooted at a vertex ๐ฃ. Suppose ๐ is also a breadth first search (BFS) tree in ๐บ, rooted at ๐ฃ. Which of the following statements is/are TRUE for every such graph ๐บ and tree ๐ ?ย ย ย ย
- A.
There are no back-edges in ๐บ with respect to the tree ๐
- B.
There are no cross-edges in ๐บ with respect to the tree ๐
- C.
There are no forward-edges in ๐บ with respect to the tree ๐
- D.
The only edges in ๐บ are the edges in ๐
Attempted by 134 students.
Sign up free to check your answer
Sign up freeLoading lessonโฆ