algorithm - 如何找到树上一组节点之间的最大距离？

Question

我在一棵(非二叉树)树上有一组 n 个节点。我想找到任意两个节点之间的最大距离。 (我将两个节点之间的距离定义为这些节点与其最低共同祖先之间的距离之和)。

我可以在 O(n^2) 中轻松解决这个问题，只需计算每个节点与其他节点之间的距离并获得最大值，但是我希望有更好的东西，因为这对我来说太慢了*应用场景。

(Extra info: 在我的应用场景中，这些节点实际上是文件，树是目录结构。因此，树很浅(深度 < ~10)，但它可能有 300,000+ 个节点。文件集的大小可以在 ~3-200 之间。实际上，我试图弄清楚我的文件在每组中的分布有多远。)*

编辑:也许我可以问一个等效的问题来提示更多答案:考虑原始树的一个子集，它只包含我的集合中的节点和连接它们所必需的节点。那么问题就变成了:如何在无向无环图中找到最长的简单路径？

*编辑 2: 正如 didierc 所指出的，我实际上应该考虑文件夹集而不是文件集。这使我的集合更小，并且详尽的方法可能足够快。尽管如此，如果能找到更快的解决方案还是很有帮助的，我很想看看是否有这样的解决方案。

Answer 1

您的问题也称为查找树的直径:在节点对之间的所有最短路径中，您正在寻找最长的路径。

用 d(S) 表示树 S 的直径，用 h(S) 表示树的高度。

具有子树 S1...Sd 的树 S 中距离最远的两个节点可以位于其子树之一下，也可以跨越两个子树。在第一种情况下，当两个最远的节点在子树 Si 下时，d(S) 就是 d(Si)。在第二种情况下，当距离最远的两个节点跨越两个子树时，比如说 Si 和 Sj，它们的距离是 h(Si) + h(Sj) + 2 因为这两个节点必须是每个子树中最深的两个节点，加上两个更多边连接两个子树。事实上，在第二种情况下，Si 和 Sj 必须是 S 的最高和第二高子树。

O(n) 算法将按如下方式进行

算法d(S)

1. recursively compute d(S1)...d(Sd) and h(S1)...h(Sd) of the subtrees of S.
2. denote by Si be the deepest subtree and Sj the second deepest subtree
3. return max(d(S1), ..., d(Sd), h(Si)+h(Sj)+2)

分析

第 2 行和第 3 行各需要 O(d) 的时间来计算。但是每个节点只被这些行检查一次，所以在递归中，这总共需要 O(n)。