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.)
Follow
1
Add comment
More
Report
1 Expert Answer
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.