重みのないエッジを持つ無向連結グラフがあります。すべてのノードの深さの合計が最小になるように、スパニングツリーを構築するにはどうすればよいですか（ソリューションは一意ではない可能性があります）？エッジの「重み」は実際には子供の深さによって異なるため、これは明らかに最小スパニングツリーを見つけていません。
根が指定されていれば、子として接続できるものすべてを幅優先で各ノードに貪欲に接続することで、深さの合計が最小のツリーを形成できると思います。したがって、これと同じ手順をN回適用し、N個のノードのそれぞれをルートとして指定し、N個の候補の中から最小のものを選択することによって、合計の深さが最小のツリーを見つけます。これは有効なアルゴリズムですか？それが間違っているかどうか、またはより効率的なものが存在するかどうかを指摘してください。
これは有効なアルゴリズムですか？
はい、アルゴリズムは正しいです。
Rスパニングツリーのルートと見なされるノードが与えられた場合、スパニングツリー内のノードの深さは、少なくともグラフ内のからまでNの最短パスの長さであるため、深さの合計は少なくとも合計になります。最短経路の長さの（から）。RNR
アルゴリズムによって構築されたツリーは、各ノードをR最短パスの1つに接続します。したがって、深さの合計は距離の合計であり、上記で見たのは下限です。
小さな最適化として、ノードの数が少なくとも3である場合、次数1のノードをツリーのルートと見なす必要はありません。（次数1のノードをルートとするツリーの場合、隣接するノードをルートRとするツリーとして表示される同じグラフを検討します。深さが1増加すると、他のすべてのノードの深さが1減少するため、深さの合計が減少します。によって。）RRnumber_of_nodes - 2