Asked • 06/01/19

Longest path in an undirected tree with only one traversal?

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: * Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. * Now start a DFS from $v'$ to find the vertex farthest from it. This path is the longest path in the graph.The question is, can this be done more efficiently? Can we do it with a single DFS or BFS?(This can be equivalently described as the problem of computing the [diameter](https://en.wikipedia.org/wiki/Graph_diameter) of an undirected tree.)

1 Expert Answer

By:

No expert answers yet

Answers can only be accepted by verified, expert tutors.


Still looking for help? Get the right answer, fast.

Ask a question for free

Get a free answer to a quick problem.
Most questions answered within 4 hours.

OR

Find an Online Tutor Now

Choose an expert and meet online. No packages or subscriptions, pay only for the time you need.