0

C++ で MST のプリムのアルゴリズムを実装しようとしています。デザインに関する質問があります

整数を取る最小ヒープを実装し、最小値を抽出し、キーを減らし、キーを挿入できます。

プリムで理解しているように、各頂点の重みと隣接情報を維持する必要があります。私が持っているいくつかのアイデアは次のとおりです。

1]構造を定義する

struct node {
    int vertex;
    int weight;
    int neighbor;
};

最小ヒープを使用して、重みが最小のノードを返します。しかし、問題はキーの減少です。キーの減少の場合、呼び出し元はキーを減少させたい頂点を渡す必要があるためです。ヒープは要素を頻繁にスワップするため、リスト全体を調べて頂点を見つけ、そのキーを減らす必要があります。これは O(n) です。これを行うと Prim の状態が悪化すると思います。

2] もう 1 つの方法は、min-heap キュー内の頂点の位置を追跡する別の配列を維持することです。しかし、最小ヒープ操作中に位置を追跡するのは面倒です。

基本的に、reduce-key(v) を実行する必要がある場合、重みに基づく最小ヒープ キューで v を見つける方法。これを行うエレガントな方法はありますか？まだ複雑さを保持できるのはどれですか?

4

1 に答える 1

1

基本的に、データ構造間の相互参照を行う必要があります。しかし、あなたは書く

ただし、最小ヒープ操作中に位置を追跡するのは面倒です

これは正確ではありません。以下を使用すると、これを必要としない再利用可能なデータ構造を再利用または書き込むことができます。

  1. まず、プライオリティ キューは、 O(1)アクセスを許可するある種のiteratorを公開する必要があります。これには、直接使用するか (以下の注を参照)、そこからインターフェースがどのように見えるべきかについてのアイデアを得ることができます。boost.Heap

  2. ここで、( O(1)で) ノード ラベルをキューの反復子にマップする別のデータ構造を使用します。たとえば、ノード ラベルが (連続した) 整数の場合、vectorof イテレータを使用できます。それらが基本的に他のものである場合は、おそらく を使用する必要がありますunordered_map。

  3. 各ノード構造には、2 のデータ構造で使用されるラベルも含める必要があります。

項目 3. は、上記のコードに以下を追加する必要があることを意味します。

struct node {
     ...
     // Identifies
     Label label;
};

これにより、プライオリティ キューを他のデータ構造から分離できることに注意してください。を実行し、優先キュー内decrease_keyを移動する場合、各ノードにはメンバーnodeが含まれているため、何も心配する必要はありません。label

以上のことをすべて述べた上で、すでに Prim のアルゴリズムを備えているBoost Graph Libraryを使用することも検討する必要があります。

于 2015-05-16T07:16:37.177 に答える