6

重複の可能性:
すべての最小スパニング ツリーの実装

無向グラフのすべての最小全域木を効率的に見つけるにはどうすればよいですか?

4

3 に答える 3

1

学術的な回答で申し訳ありません...しかしS、KnuthのTAOCP、Volume 4、Fascicle 4のアルゴリズムは、まさにすべてのスパニングツリーを生成することです(pp. 26ff)。彼がツリーの生成 (スパニング) について話すとき、いくつかの思索がありますが、 TAOCPが最善の策です。

于 2010-12-31T20:57:31.260 に答える
0

はい、グラフ内のすべてのスパニング ツリーを生成するためのアルゴリズムがあります。少なくとも1 つは、ツリー間の差分のみを生成して出力を圧縮します。他の人が指摘しているように、小さなグラフでも最小スパニング ツリーが多数存在する可能性があります。

于 2011-09-25T19:46:49.477 に答える
0

あなたは1つを見つけることができます..BFSアルゴリズムを変更します!

于 2011-09-25T19:03:23.267 に答える