0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ When you talk about MST, it is the minimum spanning tree of a graph (which is generally not a tree). If your question is just interested in the path along this MST, you should say "given a tree" as the original graph is out of the problem. Please also clarify "longest path", are you talking of the largest number of crossed edges, or the largest total weight ? $\endgroup$ – Vince May 14 at 15:33
  • $\begingroup$ Yeah I wasn't sure if saying that I'm trying to do this on MST would help in some way. The longest path is the one with largest number of crossed edges. $\endgroup$ – Elia May 14 at 15:45
  • $\begingroup$ "I'm having a bit of a hard time finding the nodes themselves and their correct order." Will you consider an answer that explains how to output the nodes in the longest path of a given tree in order good enough? $\endgroup$ – Apass.Jack May 14 at 16:15
  • $\begingroup$ Certainly, my issue is that the longest path isn't always found by following the parent node but might be by following a leaf multiple levels up to a parent then along its sibling path (that might have another multiple children so it gets confusing there). I hope that was clear. $\endgroup$ – Elia May 14 at 16:25
  • $\begingroup$ I'm hoping to do this recursively in one traversal, otherwise it could be done using two DFS I guess $\endgroup$ – Elia May 14 at 16:32

Your Answer

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

Browse other questions tagged or ask your own question.