Bug in finding minimum spanning tree using Kruskal's algorithm

Question

I write the code from adding vertex into a graph and update the weight of edge and then find the minimum spanning tree. I think that I have done it but there seems to be some error in it but I cannot find it out.The system using Valgrind and indicate that "invalid write of size 4" and "invalid read of size 4 " in the call of MST, but I think it work fine.The whole error of Valgrind is https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing

The following code is called by like

CreateNewGraph();
AddEdge(1, 2, 10);
AddEdge(2, 4, 10);
AddEdge(1, 3, 100);
AddEdge(3, 4, 10);
GetMST(mst_edges);

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.

#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

namespace HOMEWORK{
    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<Edge> graph(0);
    vector<int> parent(0);

    int findset(int x){
        if(x != parent[x])parent[x] = findset(parent[x]);
        return parent[x];
    }

    void CreateNewGraph(){
        graph.clear();
        parent.clear();
    }

    void AddEdge(unsigned int u, unsigned int v, double w){
        graph.push_back(Edge(u,v,w));
    }

    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<pair<unsigned int, unsigned int> >& mst_edges){
        mst_edges.clear();
        parent.clear();
        int e = graph.size();
        for(int i = 0; i <= e + 1; 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(){
    }
}

Answer 1

I think the issue is how you're setting up parent pointers. Note that you've set up parents as

for(int i = 0; i <= e + 1; i ++) parent.push_back(i);

This creates one entry in the parent array for each edge in the graph, plus one extra one. However, each node has a parent, not each edge, and the number of nodes in a graph can be bigger than the number of edges plus one. For example, suppose you're given this set of edges:

1  2
3  4
5  6

This graph clearly has six nodes in it (numbered 1 ... 6), but your code would only make space for 4 entries in parents.

Try changing your code so that you set parents to be the proper size, probably by finding the maximum and minimum numbered node in the list of edges and sizing the array appropriately. Alternatively, consider using a std::unordered_map<int, int>, which is more flexible if the vertex numbers don't contiguously begin at 0.

Hope this helps!