1
$\begingroup$

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.

thanks :)

$\endgroup$
1
$\begingroup$

Regarding DFS the answer is no. Here there is a counter example.

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.