所以，我有N个节点和N-1条边因此，图可以表示为树现在，我需要找到到达每个节点至少一次所需的最小距离N的上界是10^5。
有没有办法在合理的时间内做到这一点这个问题可能有个名字，但如果有，我找不到。
我知道tsp是np完全的。然而，由于这个图是一棵树，我想知道是否有一个实际的解决方案这个问题。
谢谢。
最佳答案
如果这是一棵树，那么深度优先或宽度优先tree traversal是访问每个节点的简单方法。这是一个O（N）操作。
如果它对您没有任何影响，那么使用深度优先遍历，因为它使用更少的内存，而且IMO更容易实现。