找到最小化树深度的根

给出一棵树，内容无周期（例如最小生成树：http://fr.wikipedia.org/wiki/Fichier:Minimum_spanning_tree.svg）如何计算哪个节点最小化树深度（如果它用作根）？找到最小化树深度的根

2012-03-30 luxcem

澄清：你问，给定完全连接的无向非循环图，选择距离最近的节点最近的节点？ – DRVic 2012-03-30 23:28:36

所有树木都不包含周期。根据定义，树是一个无周期的连通图。如果有一个顶点，答案是微不足道的。所以假设至少有两个顶点。

让ù和v是两个顶点，使得它们的距离d（ü，v）是最大的。应该很容易看出，如果一个选择沿最短UV路径顶点是根，深度将至少天花板（d（ü，v）/ 2）。还应当指出的是，如果一个选择顶点是路径上的根没有，深度将大于天花板（d（ü，v）/ 2）。

假设我们选择了根- [R为沿着最小UV路径，使得d中间顶点（ü，- [R）= 天花板（d（ü，v）/ 2）和d（- [R，v）≤ 天花板（d（u,v）/ 2）。如果有另一个顶点，瓦特，这样d（[R，瓦特）>天花板（d（ü，v）/ 2），我们将不得不d（ü，- [R）< d（瓦特，- [R），然后，因为有是在一个树中的任何两个不同的顶点之间只有一个路径，我们有d（ü，v）= d（ü，- [R）+ d（- [R，v）< d（ü，- [R）+ d（- [R，瓦特）= d（ü，瓦特），这与该ù和v有最大的距离。所以，现在的深度，给定- [R为根，是天花板（d（ü，v）/ 2）。

所以我们需要找到距离最远的两个顶点。一旦我们做到这一点，我们可以用最短路径搜索算法UV，注意长度，并遍历中途沿上述路径和使用中的顶点作为根。

我们如何找到这些顶点？选取顶点w并将其放入队列中。当队列非空时，将队列中下一个顶点的邻居添加到队列末尾。当队列为空时，请记下最近移除的顶点。这将是ü。再次执行该程序，您将有诉。

为什么这样吗？上述算法找到距离最远的顶点w。如果瓦特恰好是ü或v，该算法显然没有分别v或ü。因此，假设瓦特既不是ü也不v。如果算法在第一遍中发现了或或v，那么它又会起作用（因为它会在第二遍中找到另一个），所以假设通过相反的方式在第一遍之后找到x，使得它不是树的最大路径的末端。从三角不等式，我们有d（ü，v）≤ d（ü，瓦特）+ d（瓦特，v）和d（v，x）≤ d（v,w）+ d（w,x）。从减去第二，第一，我们有d（ü，v） - d（v，X）≤ d（ü，瓦特） - d （w,x）。然后，我们可以重新安排到d（ü，v）+ d（瓦特，X）≤ d（ü，瓦特）+ d（v，x）。由于d（瓦特，Ú）≤ d（瓦特，X）（X是从瓦特的最大路径的端部; 武不能超过WX ）和d（v,x）< d（ ü，v）（X不是最大路径的结束），我们可以强化不平等d（ü，v）+ d（瓦特，X）< d（ü，v）+ d（瓦特，x）。但这不可能，所以x必须在最大路径的末尾。

来源

2012-03-30 23:33:03

谢谢！没有其他方法？ – luxcem 2012-03-31 21:32:08

我的算法/方法与Saeed完全一样。我只是给出了一个解释/证明，以便你可以阅读并知道我的答案是正确的。我可以尝试考虑一种替代算法/方法。这个有什么问题？ – 2012-03-31 22:18:27

这个问题没有问题，它完美的工作，但我想知道是否有其他方法可以做到这一点（只是出于好奇） – luxcem 2012-05-11 12:36:52

找到树的diameter后选择直径的中间节点作为根。为了找到运行两个BFS的直径，第一个BFS从随机节点v开始，并从v找到最远的节点，将其命名为x，第二个BFS从x找到最远的节点，其命名为y。现在x和y之间的路径是直径。

来源

2012-03-31 01:14:21

@nax，代码的哪一部分，如果你有一个很好的数据结构，你可以简单地使用任何的Web上可用的样本BFS代码。 – 2012-03-31 02:48:47

对不起，我的英文，我的意思是不是来源 – luxcem 2012-03-31 10:03:24

@nax，我的英文不比你好，但你想参考哪个部分？你是否在寻找证据（并不难，最好自己尝试）。但这是一种民间传说和众所周知的问题和解决方案。 – 2012-03-31 21:35:52

我认为下面的算法可能工作（我没有验证它），从图的任何树表示开始。

S = set of all leaves of the tree 
foreach node in S: mark(node) 
repeat: 
    # at each iteration, S is the set of all nodes at 
    # a given min distance to a leave 
    # initially this distance is 0, then 1, etc. 
    S' = empty set 
    foreach node in S: 
    parent = parent(node) 
    if !marked(parent): S' += parent; mark(parent) 
    if S' is empty then S contains all innermost nodes, we are done 
    S = S' and continue

来源

2012-03-31 01:47:49

找到最小化树深度的根

回答

相关问题