は最小spannningツリー

Question

の高さを計算し、私は私が最小スパニングツリーの高さを見つけることができJAVAコードが必要です。 基本的に私は、MSTの高さを与えるだけでなく、その高さを与えるだけでなく、 プリムさん/クラスカルのアルゴの延長を探してい。

ありがとうございます。

Answer 1

私はあなたにヒントを与えて、ここにコードを書いていないです。
すべてのノードで、そのノードの高さ/深さを格納する変数を保持します。

ので、開始ノードのための深さは、今すぐ0 になりますあなたはMSTにエッジを追加するたびに、1により、新しいノードの深さを増します。

現在、次の深さの検出ノードがあります。
C 1
B 1


は今、あなたはDにCからエッジを追加したいとし、そのノードの深さは、Dは（深さになりますc）+1、すなわち1 + 1 = 2である。

また、アルゴリズムの各ステップですべてのノード間で最大の深さのトラックを保持することができます。
最後に、答えはツリーのすべてのノードの中で最大の深さになります。