given an unweighted graph, does the graph diameter equal to the maximum DFS tree depth?
and the same about BFS?
regarding both directed and undirected graphs.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Regarding DFS the answer is no. Here there is a counter example.
The red arcs represent the DFS tree starting from the topmost node. This tree depth is 5 while the diameter is 3.
On the other hand, the maximum BFS tree depth coincides with the diameter of the graph (of course, this is valid if the graph is connected). If you run BFS from a source node S, all path found from this point to any other point will be of minimal length, i.e it contains all shortest path from point S to any other point. Though the maximum BFS tree depth is the maximum among all shortest path.