1

すべてのグラフ ポイントを含むファイルを使用して、boost ライブラリのprim_minimum_spanning_tree関数でPrim アルゴリズムを使用しようとしています。boost ライブラリのkruskal_minimum_spanning_tree関数を使用して、目的のグラフを作成することに成功しました。

しかし、prim_minimum_spanning_treeを使用すると、各ポイントの直接の親しか得られないため、グラフは完全ではありません。

ブーストのドキュメントに記載されている例を使用しました:

プリムの場合: http://www.boost.org/doc/libs/1_47_0/libs/graph/example/prim-example.cpp

そしてクルスカルのものhttp://www.boost.org/doc/libs/1_47_0/libs/graph/example/kruskal-example.cpp

具体的な例:私はこのポイントのファイルを持っています:

10
0 0.655171
0.304819 0.674978
0.106754 0.516587
0.489669 0.602466
0.369945 0.256661
0.374187 0.825587
0.172704 0.2978
0.643544 0.789666
0.987823 0.800592
0.464248 0.538987

私が得るクルカル関数で：

3 <--> 9
1 <--> 5
0 <--> 2
1 <--> 3
6 <--> 4
6 <--> 2
3 <--> 7
2 <--> 1
8 <--> 7

私が得るプリム関数で：

1 <--> 5
2 <--> 0
3 <--> 9
4 <--> 6
5 <--> 1
6 <--> 4
7 <--> 3
8 <--> 7
9 <--> 3

私はそれらのグラフの描画を持っていますが、画像やいくつかのリンクを投稿することはできません. しかし、ご覧のとおり、3 つのリンクがありません。

prim 関数を使用して kruskal と同じ結果を得るにはどうすればよいですか?

ありがとうございました、

PS：私は例のコードをベースとして使用し、成功せずに一連の変更を試みました.Webまたはドキュメントで有用な情報を見つけることができませんでした.

4

1 に答える 1

1

私は自分の質問に対する答えを見つけました。他の誰かにとって役立つかもしれません。

ポイントを2回リンクしていましたが、これはクルスカルのアルゴリズムでは機能しますが、プリムのアルゴリズムでは機能しません。たとえば、エッジでは次のようになります。

0 <--> 1
1 <--> 0

ここで、プリムのアルゴリズムのためにポイントを 1 回だけリンクする必要がありました。

于 2011-10-16T01:57:21.240 に答える