### Bug in finding mininum spanning tree using Kruskal's algorithm

I write the minmium spanning tree using kruskal algorithm and it comes out the error with invalid read of size 4 in the (code.cpp:30). I have google it and know that it is happens when your program reads or writes memory at a place which Memcheck reckons it shouldn't.But I see the line 30 https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing
 1234 int findset(int x){ if(x != parent[x])parent[x] = findset(parent[x]); return parent[x]; }

and it indicate different with the error indicate and cannot find the problem. I think that the index X in vector Parent should be good because I use the maximum to record the largest element
 12 if(u > maximum)maximum = u; if(v > maximum)maximum = v;

and use it to initialize all before element in the vector Parent.

for(int i = 0; i <= maximum; i ++)parent.push_back(i);
The following code is called by like

and the result will be (1,2) (2,4) (3,4).

and call UpdateEdge(1, 3, 0.1); GetMST(mst_edges); and the result will be (1,2) (1,3) (2,4).

It is sent to a system to execute and it will be called like above but in a lot of time cycle above.

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980 #include #include #include using namespace std; namespace HOMEWORK{ int maximum = 0; class Edge{ public: Edge(unsigned int, unsigned int, double); unsigned int u; unsigned int v; double w; friend bool operator<(const Edge& a, const Edge& b){ return a.w < b.w; } }; Edge::Edge(unsigned int source = 0, unsigned int destination = 0, double weight = 0.0){ u = source; v = destination; w = weight; } vector graph(0); vector parent(0); int findset(int x){ if(maximum + 1 > x){ if(x != parent[x])parent[x] = findset(parent[x]); } return parent[x]; } void CreateNewGraph(){ graph.clear(); parent.clear(); maximum = 0; } void AddEdge(unsigned int u, unsigned int v, double w){ graph.push_back(Edge(u,v,w)); if(u > maximum)maximum = u; if(v > maximum)maximum = v; } void UpdateEdge(unsigned int u, unsigned int v, double w){ for(int i = 0; i < graph.size(); i ++){ if(graph[i].u == u && graph[i].v == v)graph[i] = Edge(u,v,w); } } void GetMST(vector >& mst_edges){ mst_edges.clear(); parent.clear(); int e = graph.size(); parent.resize(maximum + 1); for(int i = 0; i <= maximum; i ++)parent.push_back(i); stable_sort(graph.begin(), graph.end()); for(int i = 0; i < e; i ++){ //cout << graph[i].u << ":" << graph[i].v << ":" << graph[i].w << ":" << parent[i + 1] << endl; int pu = findset(graph[i].u); int pv = findset(graph[i].v); if(pu != pv){ parent[pu] = parent[pv]; mst_edges.push_back(make_pair(graph[i].u, graph[i].v)); } } } void Init(){ } void Cleanup(){ } }
Last edited on
Topic archived. No new replies allowed.