根系k树树的直径

我想找到一个线性时间算法，使用递归来解决实现相邻列表的有根k-tree树的直径问题。树的直径是任何一对树叶之间的最大距离。如果我选择一个根r（即度数大于1的节点），则可以看出，直径是相同子树中两个叶子之间的最大距离，或者是一个路径的两个叶子之间的最大距离通过r。我的这个问题的伪代码：根系k树树的直径

Tree-Diameter(T,r) 
    if degree[r] = 1 then 
     height[r] = 0 
     return 0 
    for each v in Adj[r] do 
     for i = 1 to degree[r] - 1 do 
      d_i = Tree-Diameter(T,v) 
    height[r] = max_{v in Adj[r]} (height[v] 
    return max(d_i, max_{v in V} (height[v]) + secmax_{v in V} (height[v], 0) + 1)

为了得到线性时间，我同时计算直径和每个子树的高度。然后，我选择每个子树的直径与树的两个最大高度+1之间的最大数量（函数在height[v]和0之间选择，因为某个子树只能有一个孩子：在这种情况下，第二大高度是0）。我问你这个算法是否正常工作，如果没有，问题是什么？我试图推广一种解决二叉树相同问题的算法，但我不知道它是否是一种很好的泛化。

任何帮助表示赞赏！提前致谢！

来源

2012-03-14 Dree

什么是V（首都）？它与Adj [r]相同吗？ – 2012-03-14 14:25:14

不是。 V是包含树T的所有节点的集合。 – Dree 2012-03-14 14:31:42

由于您的max_ {v in V}（...）不依赖于r，我假设您正在计算单独的而不是每个递归。 – 2012-03-14 21:04:49

这是我相信你感兴趣的python实现。在这里，树被表示为子树的列表。

def process(tree): 
    max_child_height=0 
    secmax_child_height=0 
    max_child_diameter=0 
    for child in tree: 
    child_height,child_diameter=process(child) 
    if child_height>max_child_height: 
     secmax_child_height=max_child_height 
     max_child_height=child_height 
    elif child_height>secmax_child_height: 
     secmax_child_height=child_height 
    if child_diameter>max_child_diameter: 
     max_child_diameter=child_diameter 
    height=max_child_height+1 
    if len(tree)>1: 
    diameter=max(max_child_diameter,max_child_height+secmax_child_height) 
    else: 
    diameter=max_child_diameter 
    return height,diameter 

def diameter(tree): 
    height,diameter=process(tree) 
    return diameter

来源

2012-03-17 14:37:04

非常感谢！我不习惯Python，但我想我已经理解了实现。只有一件事：process（）函数返回一个pair（高度，直径），不是吗？ – Dree 2012-03-18 21:33:47

@QAndy没错。 – 2012-03-19 01:19:34

在所有的树中寻找直径做如下：

选择一个随机节点一个，此节点上运行BFS，要找到一个最远节点。将该节点命名为S。
现在运行BFS从小号做起，从找到最远的节点S，将其命名为d。

路径S和d之间是你的树直径。这个算法是O（n），并且只是两次遍历树。证明有一点棘手，但并不难。（尝试自己，或者如果你认为不对，我会稍后再写）。并且要小心我说的是树而不是一般图。（树中没有循环并且已连接）。

来源

2012-03-14 11:42:59

感谢您的回复，我已经找到了使用BFS的解决方案，并且我也证明它的工作原理。我正在寻找使用递归的解决方案。我试图收集所有可能的方法来解决这个问题:) – Dree 2012-03-14 11:58:32

@QAndy，你可以使用类似DFS的方法，为什么只是寻找递归？目前我没有时间，但稍后，我会阅读你的方法并说出我对它的正确性的看法。 – 2012-03-14 12:05:19

@Dree您是否仍然需要链接到使用BFS的解决方案及其证明？ – SilverSlash 2017-12-09 13:05:52

根系k树树的直径

回答

相关问题