我在我的图形应用程序中使用 STL priority_queue 作为数据结构。您可以放心地将其假设为 Prim 生成树算法的高级版本。在算法中，我想有效地在优先级队列中找到一个节点（而不仅仅是一个最小节点）。[这是需要的，因为节点的成本可能会改变并且需要在 priority_queue 中修复] 我所要做的就是增加priority_queue 并根据我的节点键索引它。我找不到任何可以在 STL 中完成的方法。谁能更好地了解如何在 STL 中做到这一点？
问问题
3365 次
1 回答
2
std::priority_queue<T>不支持有效查找节点：它使用d -ary heap，通常使用d == 2. 这种表示不会保留节点。如果您真的想使用std::priority_queue<T>Prim 算法，唯一的方法是添加具有当前最短距离的节点，并可能多次添加每个节点。但是，这会将 的大小变为O(E)而不是O(N)，即，对于具有许多边的图，它将导致更高的复杂性。
您可以使用类似的东西，std::map<...>但实际上会遇到几乎相同的问题：您可以找到下一个节点以有效提取，也可以找到节点以有效更新。
“正确”的方法是使用基于节点的优先级队列，例如Fibanocci-heap：由于节点保持原位，您可以在插入节点时从堆中获取句柄，并通过处理。使用堆树集中的几个顶部节点访问最近的节点是有效的。斐波那契堆的基本堆操作（ 、 和 ）的整体性能push()比top()d pop()-ary 堆慢，但单个节点的有效更新使得它们的使用值得。我似乎记得 Prim 的算法实际上需要斐波那契堆来实现严格的复杂性界限。
我知道在Boost有一个斐波那契堆的实现。斐波那契堆的有效实现并非完全微不足道，但它们比仅仅具有理论意义更有效。
于 2013-11-15T00:27:51.783 回答