11

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

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

（额外信息：在我的应用场景中，这些节点实际上是文件，而树是目录结构。因此，树很浅（深度 < ~10），但它可能有 300,000+ 个节点。文件集可以是大小在〜3-200之间。实际上，我试图弄清楚我的文件在每组中的分布范围。）*

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

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

4

4 回答 4

11

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

用 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)。

于 2012-11-21T21:51:59.467 回答
6

对于这个有趣的问题，我有一个简单的 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 将是与其具有最大距离的顶点。
  • 该算法的第 1 步是基于Theorem，因此我们可以很容易地得到树的一个角 (Y)。
  • 第二个角 Z 也是基于定理找到的。

延长

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

  • 我们可以在 O(n) 复杂度中找到树的两个角，然后我们可以再次使用定理。
  • 从角 Y 和 Z 我们分别做 dfs，对于每个顶点 p[i] 我们可以得到到 Y 和 Z 的距离（我们称它们为 disY[i] 和 disZ[i]），所以 p[i 的最远距离] 是最大值（disY[i]，disZ[i]）。由于我们只进行了两次 dfs，因此我们可以获得 O(n) 复杂度的信息。
  • 这个扩展问题也可以通过复杂度也是 O(n) 的复杂树动态规划来解决。
于 2012-11-22T04:06:11.303 回答
5

假设两个节点之间的最大长度路径通过我们的根节点。那么这两个节点中的一个必须属于一个孩子的子树，而另一个必须属于另一个孩子的子树。那么很容易看出，这两个节点是这两个孩子的最低/最深的后代，这意味着这两个节点之间的距离是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(树高度) 空间。

于 2012-11-21T21:13:12.517 回答
1

这是一个递归算法。这是伪代码（未经测试的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返回没有第一个元素的列表。

于 2012-11-21T22:12:17.170 回答