ルーテッドk-aryツリーの直径

Question

私は、隣接リストを使って実装されたルートk-aryツリーの直径問題を解くために、再帰を使って線形時間アルゴリズムを見つけようとしています。樹木の直径は、任意の数の葉の間の最大距離である。ルートr（degree>> 1のノード）を選択すると、同じサブツリー内の2つのリーフの間の最大距離か、パスの2つのリーフ間の最大距離のいずれかが表示されますrまでこの問題の私の擬似コード：

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) 

線形時間を得るために、各サブツリーの直径と高さを同時に計算します。次に、各サブツリーの直径とツリーの2つの最大高さの間の最大量を選択します（​​関数はheight[v]と0の間で選択します）。これは、 0）。私はこのアルゴリズムがうまく動作するかどうかを尋ねます。そうでない場合、問題は何ですか？私はバイナリツリーで同じ問題を解決するアルゴリズムを一般化しようとしましたが、それが良い一般化であるかどうかはわかりません。

ご協力いただきましてありがとうございます。前もって感謝します！

直径は以下のように行う見つけるためのツリーのすべてで

Answer 1

これは私があなたが興味を持っていると思っているものの、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 

Answer 2

：

1. は、ランダムなノードを選択し、から遠いノードを見つけるために、このノード上でBFSを実行します。このノードの名前をSとします。

2. は、今ではD名、Sから遠いノードを見つけ、Sから始まるBFSを実行します。

パス D S 間とはあなたの木の直径です。このアルゴリズムはO（n）であり、ツリーを2回通過するだけです。証拠は少しトリッキーですが、難しくありません。 （あなた自身を試してみてください。そうでないと思われる場合は、後で書きます）。そして、私はツリーが一般的なグラフではないことに注意しています。 （ツリーにループがなく、接続されています）。