7

Adaの Kruskal のアルゴリズムを参照すると、どこから始めればよいかわかりません。

実際にプログラムを書く前に、すべてを考えようとしていますが、どのデータ構造を使用すべきか、すべてをどのように表現するかについてかなり迷っています。

私の当初の考えは、隣接リストで完全なツリーを表すことでしたが、ウィキペディアを読むと、アルゴリズムは次のように述べられてcreate a forest F (a set of trees), where each vertex in the graph is a separate treeおり、非常に面倒にならずにこれを実装する方法がわかりません。

次にやるべきことは ですがcreate a set S containing all the edges in the graph、繰り返しになりますが、これを行う最善の方法が何であるかはわかりません。to、 、fromを含むレコードの配列を考えていましたが、 .weightで迷ってしまいましたforest。

最後に、エッジが 2 つのツリーを接続しているかどうかを知る方法を見つけようとしていますが、これをすべて行う最善の方法が何であるかはわかりません。

4

2 に答える 2

3

彼らのアルゴリズムの説明では、どこから始めればよいのか混乱してしまうことがわかります。それは私を同じように残しました。

代わりに、後の例のセクションを読むことをお勧めします。これにより、進め方がかなり明確になり、おそらくそこから必要なデータ構造を思いつくことができます。

基本的な考え方は次のようです。

  • グラフを取り、少なくとも 1 つの新しい頂点を導入する最短のエッジを見つけて、それを「スパニング ツリー」に入れます。
  • すべての頂点が得られるまで、上記の手順を繰り返します。
于 2011-10-17T12:57:06.500 に答える
2

「森の部分を作成する」とは、実際には次のことを意味します: Disjoint-set data structureページから疑似コードを実装します。あなたが C++ を読めるなら、私はかなり単純な実装をここに持っています。（その実装は機能します。私はそれを使用して、クラスカルのアルゴリズムを自分で実装しました:)

于 2011-10-17T13:21:41.917 に答える