使用优先队列实现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]。除此之外我这里运行没有看到问题。


请确认你的测试代码是否有问题。如果测试代码部分还包含其他代码的执行,请确定是不是这些其他的代码导致的。


继续加油!:)

0
0

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11213 学习 · 1617 问题

查看课程