重み付けされていないエッジを持つ無向グラフが接続されています。すべてのノードの深さの合計が最小になるようなスパニングツリー（ソリューションは一意でないかもしれません）を構築するにはどうすればよいですか？エッジの「重み」は実際には子供の奥行きによって異なるため、これは明らかに最小スパニングツリーを見つけることはありません。ノードの深さの合計を最小化するスパニングツリーの検索
私は、指定されたルートが与えられていると、深さの合計が最小のツリーは、子供として接続できるすべてを垣間見ることで各ノードに貪欲に接続することで形成できると思います。したがって、この同じ手順をN回適用し、N個のノードのそれぞれをルートとして指定し、N個の候補の中から最小のものを選択することによって、最小全深度を有するツリーを見つける。これは有効なアルゴリズムですか？それが間違っているか、より効率的なものが存在するかどうかを指摘してください。
これは有効なアルゴリズムですか？
はい、アルゴリズムは正しいです。
スパニングツリーのルートと見なされるべきであるノードR考えると、スパニングツリー内のノードNの深さは、少なくともグラフでRからNへの最短経路の長さなので、合計でありますは、少なくとも最短経路の長さの合計（R）である。
アルゴリズムによって構築されたツリーは、各ノードを最短経路の1つと接続します。したがって、深さの合計は距離の合計です。これは上で見たものが下限です。
小さな最適化として、ノードの数が3以上の場合、次数1のノードはツリーのルートとみなす必要はありません。 （Rの次のノードをルートとするツリーについては、Rのネイバーをルートとするツリーとみなされる同じグラフを考えてみましょう。Rの深さは1だけ増加し、他のすべてのノードの深さは1減少します。深さの減少はnumber_of_nodes - 2で減少する。）
+1、すばらしい質問に対する優れた答え。さらなる最適化として、各BFS内で、深度の合計がこれまでに見出された最小値よりも大きい場合に早期に終了する。いくつかのタイプのグラフでは、度数の降順で頂点をループすると役立つかもしれません。 –
それは本質的に最短経路の問題であることに気付かなかった。ありがとう!! – klkh
興味深いアプローチ。アルゴリズムが有効であれば 'O（n^2）'はかなり良いです。 –
それは私には正しいようです。グレートアルゴリズム –
スパニングツリーには実際にルートノードがないため、ノードの深さの概念はわかりません。多分、ノードの深さによって、Primアルゴリズムで訪れた最初のノードに根ざしていれば、ツリーの直径や深さを意味するでしょうか？ –