如何使用STL實現Prim的算法？

我想實現一個數據結構，它既是堆又是無序映射的組合。堆將保存包含標識符和成本的圖節點。我使用min_extract函數在log（n）時間內讓節點下一次展開。 [我正在使用std :: vector和std :: make_heap，pop_heap等從算法中實現堆]如何使用STL實現Prim的算法？

無序映射包含節點，矢量映射中的位置。無序映射用於支持包含和更新節點函數。但是對於我來說，我需要節點和它在矢量中的位置之間的映射，否則我不得不對該節點進行線性搜索。

更令人擔心的是，我推或者彈出一個項目，並調用push_heap或pop_heap，這將圍繞向量中的節點和我在地圖中維護的位置轉移，最終會出錯。

那麼如何實現功能，我可以在哪裏維護節點與其位置之間的映射。

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 ? 

    }

的數據結構我尋找具有支持：找到分鐘：O（LG n）的包含：O（1）更新節點：O（LG n）的插入：O（LG N）

這將是微不足道的實施，如果我推出我自己的堆在那裏，當我做泡漲還是跌，我更新地圖節點的位置。在我這樣做之前，我想確保我不能在STL中做到這一點。

來源

2016-11-28 nnrales

http://www.geeksforgeeks.org/prims-algorithm-using-priority_queue-stl/ – AndyG

如果您將邊緣放入您的優先級隊列中而不是節點中，那麼您不需要該更新節點功能，並且一切都變得容易很多。

使用某種集合實現來跟蹤樹中的哪些頂點。
使用優先級隊列來維護可能邊的有序隊列。

然後：

添加的初始頂點的集合，並且其邊緣添加到優先級隊列
刪除從優先級隊列的最低邊E。
如果E的頂點V之一不在樹中，則將E和V添加到樹中。 V會進入你的設定。如果V對於不在集合中的節點有任何邊緣，則將這些邊緣添加到優先級隊列中。
返回到步驟2，直到隊列是空的。

來源

2016-11-28 18:46:50

如何使用STL實現Prim的算法？

回答

相關問題