質問: ツリーを同じ部分に分割する 私はそれから1つのエッジを削除することによってNノード(各ノードの最大次数が3である)を持つツリーを分割するアルゴリズムを探しているので、結果として得られる2つのツリーはできるだけN/2に近い。 「最も中心がある」エッジを見つけるにはどうすればよいですか? ツリーはアルゴリズムの前段階からの入力として提供され、グラフとして入力されるため、どのノードがルートであるかは明確ではありません。 私の考えは、ツリー内で最長のパスを見つけて、最も長いパスの途中でエッジを選択することです。それは動作しますか? 最適には、どちらのツリーにも2N/3ノード以上が存在しないようにするソリューションを探しています。 あなたの答えをありがとう。
回答: 私はあなたの最初のアルゴリズムが私がコメントで言及した理由のために働くとは思わない。しかし、修正されたDFSを使ってO(n)時間と空間でこれを解決できると思います。 まずグラフを歩いて、そこにあるノードの数を数えます。これをnと呼ぶ。ここで、任意のノードを選択し、ツリーをルートにします。ルートから始まるツリーを再帰的に探索し、各サブツリーのノード数を計算します。これは単純な再帰を使用して行うことができます: * If the current node is null, return 0. * Otherwise: + For each child, compute the number of nodes in the subtree rooted at that child. + Return 1 + the total number of nodes in all child subtrees この時点で、エッジの下にあるサブツリーにk個のノードがある場合、こぼれ落ちは(k、n - k)になるため、各エッジに対して、そのエッジを削除することによって得られる分割を知ります。したがって、すべてのノードを反復し、最も均等にバランスをとるノード(k、n-k)を探すことで、最適なカットを見つけることができます。 ノードを数えるにはO(n)時間がかかり、再帰を実行すると各ノードとエッジをたかだかO(1)回訪問するので、O(n)時間もかかります。最適カットを見つけるには、O(n)のネット実行時間に対して、追加のO(n)時間が必要です。サブツリーのノード数を格納する必要があるため、O(n)メモリーも必要です。 お役に立てれば!