algorithm - 树上的旅行推销员

Question

所以，我有 N 个节点和 N-1 条边。因此，图可以表示为树。现在，我需要找到至少到达每个节点一次所需的最小距离。 N 的上限为 10^5。

有没有什么办法可以在合理的时间内做到这一点？这个问题可能有一个名称，但如果有的话，我找不到它。

我知道 TSP 是 NP 完全的。然而，由于这个图是一棵树，我想知道是否有解决这个问题的实际方法。

谢谢。

Answer 1

如果这是一棵树，那么深度优先或广度优先tree traversal是访问每个节点的简单方法。这是一个 O(N) 操作。

如果它对您没有任何影响，那么使用深度优先遍历，因为它使用更少的内存并且 IMO 更容易实现。