ユークリッド重みの隣接行列として表される無向グラフがあります。これを使用して、より大きな完全なグラフの最小スパニング ツリーを表します。
私が見つけたいのは、グラフ内の単一のノードであり、ルート ノードとして使用すると、可能な限り短いツリーの高さを作成します。私が思いついたのは、すべてのノードをルートとして使用して深さ優先のトラバーサルを実行し、見られる最短の高さを追跡することです。これを達成するためのより速い方法はありますか？
1768 次
1 に答える
2
これは古典的なアルゴリズムの質問です。探しているものはツリーの中心と呼ばれ、単純な反復アルゴリズムを使用して見つけることができます。 この質問には、その方法を説明する優れた回答があります。
お役に立てれば！
于 2011-04-01T17:58:20.750 に答える