algorithm - 树上的旅行推销员

Question

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

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

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

谢谢。

Answer 1

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

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

Answer 2

您可以做的是隔离图中的循环并将它们分组为一个巨大的节点。当你这样做时，你应该有一个由节点组成的循环组的有向无环图。找到到达 dag 中每条路径的最短路径很容易，所以此时唯一要做的就是确保每个组的端点与您要遍历的组中的正确节点连接。

Answer 3

好吧，我最终自己解决了这个问题。基本上，访问节点中每棵树的最短路径将遍历每条边两次，除了从原点到离原点最远的节点的路径。因此，您使用 dfs，并存储最长的路径。这是我的代码。

long long dfs(int a, int b){ //a is the current node, b is the node you reached the current node from.
ll ans=0;
for(int i=0;i<elist[a].size();i++){ //elist is just a vector of all the edges.
    int x=elist[a][i];
    if(x==b) continue;          //this checks to make sure you aren't going straight back to the previous node you visited.
    ans=max(ans,cost[a][i]+dfs(elist[a][i],a)); //ans is the longest distance. Cost is an array of all the edge costs.
}
return ans;

}