Given an undirected MST with positive weights how can the longest path be found?
Based on the accepted answer in this question Longest path in an undirected tree with only one traversal I've managed to find the number of nodes a longest path includes but I'm having a bit of a hard time finding the nodes themselves and their correct order.
The longest path is regarded as the path with the largest number of crossed edges (where each edge can be crossed only once).
- Adding a backstory, if relevant and if someone can provide some other approach:
Given an unordered set of 3D points that are known to be the boundary of some arbitrary shape. Finding the Euclidean MST and the longest path in it (path with the most nodes) would give an ordered list of the border points while excluding some of the points that are not needed. I've already done this but in a very inefficient way hence trying to work with trees now.