1

向我解释如何构建优先级队列以及为什么必须以这种方式构建，就好像我对优先级队列的经验的限制是知道队列是什么（我一生中从未使用过）。

当我在看这个网站时： http ://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html

priority_queue<Time, vector<Time>, CompareTime> pq;

我知道时间是为了让你有一个时间队列，比较时间决定了将时间放入队列的优先级，但是为什么vector<Time>需要在构造函数中呢？

关于 Dijkstra：我将图实现为节点向量，每个节点包含该向量中所有邻居位置的列表），所以它看起来像这样：

class Node {
  protected:
  string name;
  int value;
  list<int> nodes
}

我将如何实现 Dijkstra 的这一部分：

for each vertex v in Graph:                                
    dist[v] := infinity ;                               
    previous[v] := undefined ;

对于 dist[v] = infinity，我假设我将每个节点的值设置为无穷大，但是什么变量可以让我这样做？而对于previous[v]，未定义是什么意思？

4

2 回答 2

3

它是一个编程练习（也就是你必须实现everithing），还是一个真正的程序？

如果是最后一个，请查看标准库优先级队列：http ://en.cppreference.com/w/cpp/container/priority_queue

另一方面，如果它真的是一个学习练习，经过一番谷歌搜索后，你会发现： http: //pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

我可以写一篇关于priority_queues 实现的介绍/解释（最大/最小堆、推送/弹出操作等），但那篇论文（我认为）有很好的例子、解释和图片。

编辑：看到你对我的问题的回答“它是一个练习还是一个真正的程序？” . 我更喜欢在这里写下整个答案，并附上示例。

第 1 步：设置

std::priority_queue具有三个模板参数：

  • T : 很明显，存放在容器中的物品的类型。
  • 底层容器：顾名思义，是实现中使用的底层容器的类型。它的默认值为std::vector<T>.
  • 比较器： priority_queue用来比较项目的函子类。它的默认值为std::less<T>（因此，默认情况下，std::priority_queue 是最大优先级队列）。如果您想要一个最小优先级队列（如您的情况，Dijkstra 算法），您必须通过一个比较器来做到这一点。通常，您operator >为您的类型实现二进制文件，以使std::greater<T>仿函数工作。

STEP2：使用std::priority_queue

所以，如果你已经做好了设置，你就可以使用std::priority_queue. 它具有三个主要业务：

  • push()：在 piority_queue 中插入一个值。
  • pop()：移除优先级队列的顶部。
  • top()：返回对存储在 priority_queue 中的具有最大（或最小，取决于您的比较器）优先级的元素的 const 引用。请注意， top() 不会删除，它是pop()的工作。

例子：

#include <queue>
#include <iostream>

//User defined type. For this short example, a simple uint wrapper:
struct Foo
{
    unsigned int i;

    Foo(unsigned int _i) : i(_i) {}
};

//Implementation of operator> for class Foo, to make std::greater<Foo> work:
bool operator>(const Foo& f1 , const Foo& f2)
{
    return f1.i > f2.i;
}

int main()
{
    std::priority_queue<Foo,std::vector<Foo>,std::greater<Foo>> foo_min_priority_queue;

    foo_min_priority_queue.push(Foo(2));
    foo_min_priority_queue.push(Foo(1));
    foo_min_priority_queue.push(Foo(0));

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 0 
    foo_priority_queue.pop();

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 1 
    foo_min_priority_queue.pop();

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 2 
    foo_min_priority_queue.pop();

    return 0;
}

参考：

于 2013-06-07T23:32:20.320 回答
3

在 C++ 中，int 最大值可以用作无限

#include <limits>

然后使用

int imax = std::numeric_limits<int>::max();
于 2013-06-07T23:02:53.220 回答