优先队列和Prim算法

Question

我已经阅读了C++参考手册,目前还不清楚如何在STL中使用priorityqueue数据结构.

所以,基本上我一直在尝试使用堆来实现自己的.

我这样做是为了实现Prim的算法.

Vector <int, int> pq;

这是我的优先队列.第一个字段是节点,第二个字段是现有树的权重.

我计划每次通过更新其邻居节点的权重将新节点添加到树中时修改pq中的权重值.

• 如何访问此向量的各个元素？我还需要能够随意删除元素.

这是实现优先级队列的好方法吗？如果我想在容器中添加另一个字段,即

Vector<int, int, int> MST

• 我如何访问第三个元素？我希望以这种方式存储生成的MST,使得前两个字段表示形成边缘的顶点,第三个字段表示权重.

如果有人能告诉我如何使用push_back为这个向量分配元素,这也会有所帮助.

• 此外,传统的C++ STL优先级队列是否有助于此,因为每次将新元素添加到MST时我需要更新优先级值？当值被修改时,它会根据优先级自我纠正吗？

• 另外一个问题,这些向量,当我将它们传递给函数,并尝试进行更改时,它是值传递还是通过引用传递 - 或者,更改是否反映在函数外部？

Answer 1

在Prim的算法中,随机访问不需要的元素.您只需要跳过连接已连接并向前传递的队列中的元素.

所以算法如下:

1. 选择一个节点 N
2. 将所有边添加N到PQ
3. 从PQ中获得最低成本优势
   • 如果它连接已在树中的节点,则跳过它
   • 否则将此边添加到树中,调用新节点N并返回到第2点.

添加节点后,只需检查树的大小是否已经存在size of graph - 1.如果是,那么完成.

请注意,PQ的操作只有add_element和pop_minimum-从而std::priority_queue将工作.