使用优先队列实现prim算法时,pq.push()出现错误
来源:9-4 换一种方法实现 Dijkstra 和 Prim

慕函数1453606
2021-11-15
波波老师,我按照您使用优先队列实现Dijkstra算法的方式写了一下Prim算法的实现。
使用上图测试时,pq.push(0),pq.push(7),pq.push(1)都没有问题,但是找到下一个权值最小的边(2-3)以后,pq.push(3)的时候出现了中断,请问是哪里出现了问题?代码如下
#include <iostream>
#include <vector>
#include <cassert>
#include <queue>
#include "Edge.h"
using namespace std;
template<typename Graph, typename Weight>
class PrimMST
{
private:
Graph &G;
vector<Edge<Weight>*> edgeTo;
Weight *distTo;
bool * marked;
vector<Edge<Weight>> mst;
Weight mstWeight;
public:
PrimMST(Graph & graph) :G(graph)
{
//auto comp = [this](Edge<Weight> a, Edge<Weight> b) {return a.wt() > b.wt(); };
//priority_queue<Edge<Weight>, vector<Edge<Weight>>, decltype(comp)>pq(comp);
auto comp = [this](int a, int b) { return this->distTo[a] > this->distTo[b]; };
priority_queue<int, vector<int>, decltype(comp)> pq(comp);
assert(graph.E() >= 1);
distTo = new Weight[G.V()];
marked = new bool[G.V()];
for (int i = 0; i < G.V(); i++)
{
distTo[i] = 10000;
marked[i] = false;
edgeTo.push_back(NULL);
}
mst.clear();
distTo[0] = 0;
edgeTo[0] = new Edge<Weight>(0, 0, 0);
pq.push(0);
//pq.push(Edge<Weight> edge(-1, 0, 0));
while (!pq.empty())
{
//Edge<Weight> temp = pq.top();
int v = pq.top();
pq.pop();
if (marked[v]) continue;
marked[v] = true;
typename Graph::adjIterator adj(G, v);
for (Edge<Weight> * e = adj.begin(); !adj.end(); e = adj.next())
{
int w = e->other(v);
if (!marked[w])
{
if (edgeTo[w] == NULL || e->wt() < distTo[w])
{
distTo[w] = e->wt();
edgeTo[w] = e;
pq.push(w);
}
}
}
assert(edgeTo[v]);
mst.push_back(*edgeTo[v]);
}
mstWeight = mst[0].wt();
for (int i = 0; i < mst.size(); i++)
mstWeight += mst[i].wt();
}
~PrimMST()
{
delete[] marked;
delete[] distTo;
delete[] edgeTo[0];
}
vector<Edge<Weight>> mstEdges()
{
return mst;
}
Weight result()
{
return mstWeight;
}
};
写回答
1回答
-
liuyubobobo
2021-11-15
我没有具体看你的代码,但测试了一下,没有中断,没有遇到问题。
一个小问题是析构的时候,edgeTo[0] 是一个 Edge,不是一个数组,所以应该是 delete edgeTo[0] 而不是 delete[] edgeTo[0]。除此之外我这里运行没有看到问题。
请确认你的测试代码是否有问题。如果测试代码部分还包含其他代码的执行,请确定是不是这些其他的代码导致的。
继续加油!:)
00
相似问题