3
$\begingroup$

I have a tree. This tree has no particular root (free-tree). I want to find a path that visit all nodes. This path has to be the shortest possible.

All edges are considered to have a distance of 1.

My problem is not finding a Hamiltonian path, because I don't have any restriction on the number of times a node can be visited.

We don't know the source node of the path. The source has to be one allowing us to find the shortest path visiting all nodes.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? What approaches have you considered and rejected, and why? We don't want to just do your exercise for you. We want to help you gain understanding, but as it is not clear what your specific problem is, it's not clear how to help. Assuming you've tried to solve it, please edit the question to show your thoughts and the answers to these questions. If you haven't made a serious effort to try to solve it on your own, you should do that before posting here. $\endgroup$ – D.W. Oct 20 '15 at 2:01
  • $\begingroup$ So what other restrictions do you have for the algorithm? $\endgroup$ – Juho Oct 20 '15 at 7:03
2
$\begingroup$

Hint: Start from a source $s \in V$ to visit all vertices that $V$ is the set of vertices of the tree. All edges are visited twice except those which contribute to the longest path.

Then, the shortest possible path, visiting all nodes, is equal to $2 \times |E| - |P_{L}|$, where $|E|$ denotes the number of edges, and $|P_{L}|$ is the number of edges in the longest path. This can be achieved with time complexity $O (E)$.

$\endgroup$
0
$\begingroup$

In a DFS traversal of the tree (starting from an arbitrary node) every edge is traversed twice: once down and once up. Some of these edges need not be traversed down.

Say your DFS traverses the children from left to right. Then the edges drawn in red in the following figure need to be traversed once only (we don't need to traverse them on the way back from the deepest node).

enter image description here

Now we want to find a red path that is as long as possible. This is known as the diameter of the tree and it can be found in linear time. The diameter of the tree above is equal to 5 for example.

$\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.