如何找到树上一组节点之间的最大距离？ [英] How to find the max distance between a set of nodes on a tree?

问题描述

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

我可以很容易地解决O（n ^ 2）通过计算每个节点到每个其他节点之间的距离并获得最大值，但是我希望更好，因为对于我的应用场景，这太慢了。

（额外信息：在我的应用场景中，这些节点实际上是文件，树是一个目录结构，因此树很浅（深度<〜10），但可能有300,000 +节点，这些文件的大小可以在〜3到200之间，实际上，我想知道每个文件在我的文件中的分布范围。）*

编辑：也许我可以问一个等价的问题来提示更多的答案：考虑原始树的一个子集，它只包含我的集合中的节点以及连接它们。然后问题变成：我如何在无向非循环图中找到最长的简单路径？
$ b

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

表示树的直径S通过d（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。递归地计算S 
 2的子树的d（S 1）... d（S d）和h（S 1）... h（S d）。由Si表示最深的子树并且S j表示第二最深的子树
 3. return max（d（S1），...，d（Sd），h（Si）+ h（Sj）+2）
   
 $ h2> Analysis  
 
 
第2行和第3行每个都需要O（d）时间来计算。但是每个节点只被这些行检查一次，所以在递归中，这总共需要O（n）。  
I have a set of n nodes on a (non-binary) tree. I want to find the maximum of the distances between any two of the nodes. (I define the distance between two nodes to be the sum of the distances between those nodes and their lowest common ancestor).

I can easily solve this problem in O(n^2) by just computing the distance between each node to each other node and getting the maximum, however I'm hoping for something better as this is far too slow* for my application scenario.

(Extra info: In my application scenario, these nodes are actually files and the tree is a directory structure. Therefore, the tree is quite shallow (depth < ~10), but it may have 300,000+ nodes. The sets of files can be anywhere between ~3-200 in size. Effectively, I'm trying to figure out how far spread out are my files in each set.)*

Edit: Perhaps I can ask an equivalent question to prompt more answers: Consider a subset of the original tree that only contains the nodes in my set and the nodes necessary to connect them. Then the question becomes: How do I find the longest simple path in an undirected acyclical graph? 

*Edit 2: As didierc pointed out, I actually should be considering sets of folders not files. This makes my sets smaller and the exhaustive approach may be fast enough. Still, it would be beneficial to see a faster solution, and I'm curious to see if there is one.
解决方案
Your problem is also known as finding the diameter of a tree: among all shortest paths between pairs of nodes, you're seeking the longest.

Denote the diameter of a tree S by d(S), and its height by h(S).

The two most distant nodes in a tree S with subtrees S1...Sd can be either under one of its subtrees, or they might span two subtrees. In the first case, when the two most distant nodes are under subtree Si, d(S) is just d(Si). In the second case, when the two most distance nodes span two subtrees, say Si and Sj, their distance is h(Si) + h(Sj) + 2 because the two nodes must be the two deepest nodes in each subtree, plus two more edges to join the two subtrees. In fact, in this second case, Si and Sj must be the heighest and second heighest subtree of S.

An O(n) algorithm would proceed as follows

Algorithm 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)


Analysis

Lines 2 and 3 each take O(d) time to compute.  But each node is examined only once by these lines, so in recursion, this takes a total of O(n). 

                        
这篇关于如何找到树上一组节点之间的最大距离？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！