4

我正在尝试实现 Prim 算法，为此我需要为优先级队列提供 reductionKey 方法（以更新优先级队列中的键值）。我可以在 STL 优先级队列中实现这个吗？

如果有帮助，这就是我正在遵循的算法：

  • 对于图 G 中的每个顶点 u
    • 将 u 的键设置为 INFINITY
    • 将你的父级设置为 NIL
  • 将源顶点的键设置为 0
  • 排队到优先级队列 Q 图中所有顶点与上面的键
  • 而 Q 不为空
    • 弹出 Q 中键最低的顶点 u
    • 对于你的每个相邻顶点 v
      • 如果 (v 还在 Q) 并且 (key(u) + weight-function(u, v) < key(v)) 那么
        • 将 u 设置为 v 的父级
        • 将 v 的键更新为等于 key(u) + weight-function(u, v) // 这部分给我带来了问题，因为我不知道如何在优先级队列中实现 reduceKey
4

4 回答 4

9

我不认为你可以在 STL 容器中实现它。请记住，您始终可以根据向量编写自己的堆（优先级队列），但有一种解决方法：

保持距离数组，比如说d。在您的优先队列中，您放置成对的距离和该距离的顶点索引。当您需要从队列中删除某些值时，请不要删除它，只需更新d数组中的值并将新对放入队列中即可。

每次从队列中获取新值时，检查距离是否真的那么好，就像在你的数组中一样d。如果不忽略它。

时间相同 O(MlogM)。内存为 O(MlogM)，其中 M 是边数。

还有另一种方法：使用 RB-Tree，它可以在 O(logN) 中插入和删除键并获得最小值。std::set您可以在容器中的 RB-Tree 的 STL 中找到实现。

但是，虽然时间复杂度相同，但 RB-Tree 的工作速度较慢且隐藏常数较大，因此可能会稍微慢一些，appx。慢 5 倍。当然，取决于数据。

于 2013-01-19T09:13:45.810 回答
2

对于另一种方法：比使用 std::set 更好。您可以使用 btree::btree_set（或 btree::safe_btree_set）。这是一个与 google 使用 B-Tree 制作的 std::set 相同的实现，与使用 RB-Tree 的 stl 不同。这比 std::set 和 O(logN) 要好得多。检查性能比较： http ://code.google.com/p/cpp-btree/wiki/UsageInstructions 而且它的内存占用也低得多。

于 2013-02-26T12:39:27.277 回答
0

我不是专家，所以希望这不是太愚蠢，但是结合 lower_bound 的向量会很好地工作吗？

如果您使用 lower_bound 找到插入新值的正确位置，则向量将始终在构建时进行排序，无需排序。当您的向量被排序时，lower_bound 不是具有对数类性能的二进制搜索吗？

由于它已排序，因此找到最小值（或最大值）很容易。

要减少键，您将执行 lower_bound 搜索、删除并再次执行 lower_bound 以插入减少的键，这 = 2 对数类操作。还是不错的。

或者，您可以更新键并对向量进行排序。我猜随机访问应该仍然在对数类中，但不知道 stl 在那里做了什么。

使用排序向量，如果您知道候选键小于其中的键，那么您甚至可以对向量中具有所有较小值的部分进行排序以获得更好的性能。

另一个考虑是我认为集合/映射比向量有更多的内存开销？

于 2015-02-06T16:42:24.787 回答
0

我认为大多数排序仅限于 NLogN，因此 2 LogN 用于重新插入而不是排序对于减少键操作可能更好。

另一件事是插入向量不是那么热，但总的来说，向量 w lower_bound 的想法是否值得考虑？

谢谢

于 2015-02-06T20:42:33.250 回答