Dar*_*ryl 10 algorithm tree graph
我在(非二进制)树上有一组n个节点.我想找到任意两个节点之间的最大距离.(我将两个节点之间的距离定义为这些节点与其最低共同祖先之间的距离之和).
我可以很容易地计算只是每个节点之间的距离,彼此节点,获得最大的解决为O这个问题(N ^ 2),但我希望的东西,因为这更实在太慢*为我的应用场景.
(额外的信息:在我的应用场景,这些节点实际上是文件和树的目录结构.因此,树是很浅(深度<〜10),但它可能有300,000节点文件的集合可以.大约3到200之间的任何地方.实际上,我正在试图弄清楚我的文件在每组中的分布范围.)*
编辑:也许我可以问一个等效的问题来提示更多的答案:考虑原始树的一个子集,它只包含我的集合中的节点和连接它们所需的节点.然后问题变成:如何在无向非周期图中找到最长的简单路径？
*编辑2:正如didierc指出的那样,我实际应该考虑的是文件夹集而不是文件.这使得我的设置更小,并且详尽的方法可能足够快.不过,看一个更快的解决方案是有益的,我很想知道是否有一个.
你的问题也被称为寻找树的直径:在节点对之间的所有最短路径中,你寻找的是最长的.
用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)算法将如下进行
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).
假设两个节点之间的最大长度路径穿过我们的根节点。然后，两个节点之一必须属于一个孩子的子树，而另一个必须属于另一个孩子的子树。因此，很容易看出，这两个节点是这两个孩子中最低/最深的后代，这意味着这两个节点之间的距离为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）空间。
对于这个有趣的问题，我有一个简单的O（n）贪心算法。
根据证明中的定理，我们可以解决另一个更具挑战性的问题：对于树中的每个顶点，计算谁是该树的远顶点。