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

Question

我有一组 n 个节点组成的(非二叉)树。我想要找到任意两个节点之间距离的最大值。(我定义两个节点之间的距离是它们和它们的最近公共祖先之间距离之和).

我可以通过计算每对节点之间的距离并获取最大值来轻松解决此问题，但是我希望有更好的方法，因为这对于我的应用场景来说速度太慢了*。

(额外信息：在我的应用场景中，这些节点实际上是文件，而树是一个目录结构。因此，树相当浅(depth < ~10)，但可能有300,000+个节点。文件集大小可以在 ~3-200 之间。实际上，我正在试图确定每个集合中的文件分布情况有多远。)*

编辑:也许我可以问一个等效的问题来引出更多答案：考虑原始树的子集，该子集仅包含我的集合中的节点和连接它们所需的节点。然后问题变成：如何在无向非循环图中找到最长简单路径？

*编辑2:正如 didierc 指出的那样，我实际上应该考虑文件夹而不是文件的集合。这使得我的集合更小，穷举法可能足够快。尽管如此，看到一个更快的解决方案会很有好处，我也很想知道是否存在这样的解决方案。

- Daryl

---

如果您考虑到您只是在比较文件夹而不是文件（因为许多文件共享同一个文件夹），那么您可以使用详尽的比较。换句话说，n 实际上是文件夹的数量。 - didierc

首先构建一个内存模型来避免受到IO的限制。 - didierc

@didierc 我确实有一个内存模型。关于节点是文件夹而不是文件的观点很好；在这种情况下，详尽的方法实际上可能足够快。不过，我仍然很好奇是否有更快的解决方案。 - Daryl

你想要距离还是“冒犯”的节点？ - didierc

@ColonelPanic 对于这个例子，我认为距离是5。这是我在“sublime”和“code”之间最短路径上计算的边数。大多数情况下，距离将用于比较目的。 - Daryl

Answer 1

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

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

树 S 中距离最远的两个节点，其中一个可以在其子树 S1…Sd 中，或者它们可能横跨两个子树。在第一种情况下，当两个最远的节点都在子树 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) 时间。

- moos

---

由于某种原因，它不允许我在@BlueRaja的解决方案下评论，所以我在这里评论。有可能两个最远的节点位于同一子树下，这种情况下你的算法会错误地尝试跨越两个子树。例如，当根节点有两个子树时，其中一个是非常深的平衡树，另一个只有一个节点时，你的算法会得到错误的直径。 - moos

我的算法没有任何缺陷；事实上，我们的算法完全相同。 - BlueRaja - Danny Pflughoeft

感谢您提供有关树的直径的信息，我之前并不知道。我选择了您的答案，因为它完整、深入、易懂且实用易行。 - Daryl

有另一种很好的线性算法来查找直径:选择任何一个节点并在树上运行DFS。取离起始节点最远的节点。从该最远节点进行DFS。第二个DFS中的最大距离即为直径。 - Niklas B.

Answer 2

我有一个简单的O(n)贪心算法来解决这个有趣的问题。

算法

1. 选择任意顶点X作为树的根，然后找到与根X距离最远的顶点Y。此步骤的复杂度为O(n)。
2. 将顶点Y作为新的根，然后找到与根Y距离最远的顶点Z。Y和Z之间的距离是树中距离最大的距离。此步骤的复杂度也是O(n)。
3. 该贪心算法的总复杂度为O(n)。

证明

• 显然，Y和Z构成了树的直径，我们称Y和Z为树的一对角落。
• 定理：对于树中的每个顶点P，Y或Z将是与其距离最远的顶点。
• 算法的第一步基于定理，因此我们可以轻松地得到树的一个角落（Y）。
• 第二个角落Z也是基于定理找到的。

扩展

根据证明中的定理，我们可以解决另一个更具挑战性的问题：对于树中的每个顶点，计算距离它最远的顶点。

• 我们可以在O(n)的复杂度内找到树的两个角落，然后再次使用定理。
• 从Y和Z两个角落分别进行深度优先搜索（DFS），对于每个顶点p[i]，我们可以得到到Y和Z的距离（称为disY[i]和disZ[i]），因此p[i]的最远距离是max(disY[i]，disZ[i])。由于我们只需要进行两次DFS，所以可以在O(n)的复杂度内得到信息。
• 这个扩展问题也可以通过复杂的树形动态规划来解决，其复杂度也是O(n)。

- Jun HU

---

哇，我真的很欣赏这个解决方案的简单优雅。 - Daryl

很棒的解决方案。这里有一个证明它有效的证据。该算法找到一对节点x0，y0，使得max_x d（x，x0）= max_y d（x0，y）（也就是说，x0和y0是彼此最远的节点）。对于任何这样的一对，d（x0，y0）是直径。证明：设x，y是两个节点，使得d（x，y）是直径。存在节点r和s，使得路径看起来像x0--r--s--y0和x*--r--s--y。假设d（x0，y0）<d（x*，y*），则d（x0，y*）> d（x0，y0）或d（y，x0）> d（y0，x0），这与x0和y0是彼此最远的点的事实相矛盾。因此d（x0，y0）= d（x，y）。 - moos

Answer 3

假设两个节点之间的最长路径经过根节点。那么其中一个节点必须属于一个子树，另一个节点必须属于另一个子树。很容易看出，这两个节点是这两个子节点的最低/深度后代，这意味着这两个节点之间的距离为height(child1) + height(child2) + 2。因此，通过我们的根节点的两个节点之间的最长路径是max-height-of-a-child + second-to-max-height-of-a-child + 2。

这为我们提供了一种简单的O(n)算法来查找整个最长路径：只需对每个非叶节点执行上述操作即可。由于每条路径必须以某个非叶节点为根，因此这保证了我们在某个时刻考虑了正确的路径。

查找子树的高度是O(n)，但是由于可以递归地构建高度，因此方便地查找每个子树的高度也是O(n)。实际上，您甚至不需要将高度作为单独的步骤查找；您可以同时查找最大长度路径和子树高度，这意味着该算法仅需要O(n)时间和O(height-of-tree)空间。

- BlueRaja - Danny Pflughoeft

---

这个算法存在一个微妙的缺陷。有可能最远的两个节点在同一子树下，这种情况下你的算法会错误地尝试跨越两个子树。例如，当根节点有两个子树时，其中一个是非常深的平衡树，另一个只有一个节点，你的算法会得到错误的直径。 - moos

@moos：不正确；如果两个节点都在同一子树下，则根节点将不是两个节点之间最长路径的一部分（也就是说，它不是这些节点的最近公共祖先）。在这种情况下，您将在递归时找到最近公共祖先（请记住，在运行此算法后，您需要跟踪所有非叶节点上找到的最大距离）。我已更新此答案，希望能更清楚地说明这一点。 - BlueRaja - Danny Pflughoeft

还有一个问题尚未解决：+1 应该变成 +2（跨越根节点需要两条边，而不仅仅是一条）。 - moos

@moos：嘿嘿，是的，我刚刚注意到了这个问题，并已经修复了 :) - BlueRaja - Danny Pflughoeft

Answer 4

这是一个递归算法。以下是伪代码（未经过测试的OCaml代码）:

 type result = {n1 : node; n2 : node; d1 : int (* depth of node n1 *); d2 : int; distance: int}
(* a struct containing:
    - the couple of nodes (n1,n2),
    - the depth of the nodes, with depth(n1) >= depth(n2)
    - the distance between n1 & n2 *)


let find_max (n : node) : result =
 let max (s1 : result) (s2 : result) = if s1.distance < s2.distance then s2 else s1 in
 let cl : node list = Node.children n in
 if cl = []
 then { n1 = n; n2 = n; d1 = 0; d2 = 0; distance = 0 }
 else 
   let ml = List.map find_max cl in
   let nl = List.map (fun e -> e.n1, e.d1+1) ml in
   let (k1,d1)::(k2,d2)::nl = nl in
   let k1,d1,k2,d2 = if d1 > d2 then k1,d1,k2,d2 else k2,d2,k1,d1 in
   let s = {n1 = k1;n2 = k2; d1 = d1; d2 = d2; distance = d1+d2} in
   let m1 =  List.fold_left (fun r (e,d) -> 
                      if r.d1< d
                      then { r with n1 = e; d1 = d; distance = d+d2 }
                      else if r.d2 < d 
                               then { r with n2 = e; d2 = d; distance = d+d1 }
                               else r) s nl in
   max m1 (List.fold_left max (List.hd ml) (List.tl ml))

m1 值是通过保留 nl 列表中深度最深的两个节点，其距离为它们深度之和而构建的。

List.map 是一个函数，将给定函数应用于列表的所有元素，并返回结果列表。

List.fold_left 是一个函数，递归地将给定函数应用于累加器和列表的元素，每次使用前一次应用的结果作为新的累加器值。结果是最后一个累加器值。

List.hd 返回列表的第一个元素。

List.tl 返回不包含第一个元素的列表。

- didierc