Computer Sciences > GATE 2024 SET-1 > Graph Traversals
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?
A
There are no back-edges in G with respect to the tree T
B
There are no cross-edges in G with respect to the tree T
C
There are no forward-edges in G with respect to the tree T
D
The only edges in G are the edges in T

Explanation

Correct : a,b,c,d

Similar Questions

What is the worst-case time complexity of insertion in an AVL tree?
Question #23 Medium
Which operations on a binary search tree have O(h) complexity?
Question #31 Easy
Compare search complexities of sorted array vs balanced BST.
Question #47 Hard

Related Topics

Data Structures Binary Search Tree Time Complexity Algorithm Analysis Tree Algorithms Computer Science