STLを使用してPrimのアルゴリズムを実装する方法は？

Question

ヒープマップと順序付けされていないマップの両方を組み合わせたデータ構造を実装しようとしています。 ヒープには、識別子とコストを含むグラフノードが保持されます。 min_extract関数を使用して、log（n）時間内にノードを次に展開するようにします。 [アルゴリズムからstd :: vectorとstd :: make_heap、pop_heapなどを使用してヒープを実装しています。

順序付けられていないマップは、ベクトルマッピングのノード、位置を保持します。順序付けられていないマップは、包含ノードおよび更新ノードの機能をサポートするために使用されます。しかし、私がこれを行うためには、ノードとベクトル内の位置の間のマッピングが必要です。そうでなければ、アイテムの線形検索を余儀なくされます。

さらにアイテムをプッシュまたはポップし、push_heapまたはpop_heapを呼び出すと、これがベクトル内のノードの周りを移動し、マップ内で維持している位置が間違ってしまう。

ノードとその位置の間のマッピングを維持できる機能を実装するにはどうすればよいですか。 O（LG： インサートO（LG n）が： に含まれるO（LG n）が：O（1） 更新ノード 分を見つける：

void push(T elem) // This will 0(n)... As the element has to be found 
    { 
     heapVec_.push_back(elem); // add tp vec 

     std::push_heap<compar_> (heapVec_.begin() , heapVec_.end()); 
     // sort ? or just find in the vec ? 
     std::size_t pos = 0 ; 

     // find position of the item in the vector 
     std::find_if(heapVec_.begin() , heapVec_.end() , [&pos , &elem](const T& item) 
       { 

        if(item == elem) 
        { 
         return true; 
        } 
        else 
        { 
         ++pos; 
        } 
       }); 


     // add to map 
     heapMap_.emplace_back(elem , pos); // how to keep track of the element where this object is added to ? 

    } 

私が探していたデータ構造をサポートしなければなりませんn）

私が自分のヒープを展開するのは簡単です。気泡を上下に動かすと、マップ内のノードの位置が更新されます。私がそれをする前に、私はSTLでそれをすることができないことを確かめたかったのです。

Answer 1

のエッジをノードではなくプライオリティキューに入れると、そのノードを更新する必要はなく、すべてが非常に簡単になります。

• 何らかの種類の実装を使用して、どの頂点がツリーにあるかを追跡します。
• 優先キューを使用して、可能なエッジの順序付きキューを維持します。

その後：

1. セットに最初の頂点を追加し、優先度キューから安いエッジEを削除するプライオリティキューに

2. をその辺を追加します。

3. Eの頂点Vの1つがツリーにない場合は、EとVをツリーに追加します。 Vがあなたのセットに入ります。 Vにセットに含まれていないノードへのエッジがある場合は、それらのエッジを優先キューに追加します。

4. キューが空になるまで手順2に戻ります。