如何使用STL实现Prim算法？

Question

我正在尝试实现一个数据结构，该数据结构是堆和无序地图的组合。堆将保存图形节点，其中包含标识符和成本。我使用MIN_EXTRACT函数来获取节点在日志（n）时间中的下一个扩展。[我正在使用std :: vector和std :: make_heap，pop_heap等从算法实现堆]

无序地图保存节点，位于向量映射中。无序的地图用于支持包含和更新节点功能。但是对于我来说，我需要节点与其在向量中的位置之间的映射，否则我被迫对项目进行线性搜索。

更令人担忧的是，我推开或弹出项目，然后调用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中做到这一点。

Answer 1

如果将 edges 放入优先级队列而不是节点，则您不需要该更新节点函数，并且一切变得更加容易。

• 使用某种设置实现来跟踪树中哪些顶点。
• 使用优先队列维护可能边的有序队列。

然后：

1. 在集合中添加一个初始顶点，然后将其边缘添加到优先级队列

2. 从优先队列中删除最便宜的边缘E。

3. 如果E的一个顶点V不在树上，则将E和V添加到树上。V进入您的场景。如果V对不在集合中的节点有任何边缘，请将这些边缘添加到优先级队列。

4. 返回步骤2，直到队列为空。

Answer 2

这个想法是从空堆开始，然后在我们继续前进。我们可能会多次将相同的顶点推入堆，但是我们仍然正确地形成了MST（使用父列表），并且总体复杂性仍然保持O（E * log（v））。这样，我们不必实现decrease_key函数。

一个人可以使用priority_queue实现此功能。但是，我使用push_heap和pop_heap功能实现了它：

#include <iostream>
#include <vector>
#include<algorithm>
#include<climits>
using namespace std;
void addEdge(vector<vector <pair<int, int> > >&adj, int u, int v, int w) 
{ 
    adj[u].push_back(make_pair(v, w)); 
    adj[v].push_back(make_pair(u, w)); 
}
int main(){
  vector<vector <pair<int, int> > >adj(9); // Taking a 9 node graph for testing.
  addEdge(adj, 0, 1, 4); 
  addEdge(adj, 0, 7, 8); 
  addEdge(adj, 1, 2, 8); 
  addEdge(adj, 1, 7, 11); 
  addEdge(adj, 2, 3, 7); 
  addEdge(adj, 2, 8, 2); 
  addEdge(adj, 2, 5, 4); 
  addEdge(adj, 3, 4, 9); 
  addEdge(adj, 3, 5, 14); 
  addEdge(adj, 4, 5, 10); 
  addEdge(adj, 5, 6, 2); 
  addEdge(adj, 6, 7, 1); 
  addEdge(adj, 6, 8, 6); 
  addEdge(adj, 7, 8, 7);
  vector<int> key(9, INT_MAX);
  vector<int> parent(9, -1);
  vector<bool> isInMST(9, false);
  key[0] = 0; // Source node is 0, its key value is also 0.
  vector<pair<int, int> > heap; // Vector named as heap.
  heap.push_back(make_pair(0, 0)); // No need to call make_heap as it has only 1 element.
  while(!heap.empty()){
    pair<int, int> temp = heap.front();
    pop_heap(heap.begin(), heap.end(), [ ] (pair<int, int> l, pair<int, int> r){
      return l.first > r.first;
    });
    heap.pop_back();
    int u = temp.second;
    isInMST[u] = true;
    for(int i=0; i<adj[u].size(); i++){
      int v = adj[u][i].first;
      int w = adj[u][i].second;
      if(!isInMST[v] && key[v] > w){
        key[v] = w;
        heap.push_back(make_pair(w, v));
        push_heap(heap.begin(), heap.end(), [ ] (pair<int, int> l, pair<int, int> r){
          return l.first > r.first;
        });
        parent[v] = u;
      }
    }
  }
  for (int i = 1; i < 9; i++) // Starting from 1, as 0 is source.
    cout << parent[i] << " - " << i << endl; // Print edges of MST using parent array.
  return 0;
}