Ошибка при поиске минимального остовного дерева по алгоритму Крускала

Question

Я пишу код от добавления вершины в граф и обновляю вес ребра, а затем нахожу минимальное остовное дерево. Я думаю, что я сделал это, но, кажется, в этом есть какая-то ошибка, но я не могу это выяснить. Система использует Valgrind и указывает, что "неверная запись размера 4" и "неверное чтение размера 4" в вызове MST, но я думаю, что это работает нормально. Вся ошибка Valgrind - https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing

Следующий код вызывается как

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

и результат будет (1,2) (2,4) (3,4).

и позвонить

UpdateEdge(1, 3, 0.1);
GetMST(mst_edges);

и результат будет (1,2) (1,3) (2,4).

Он отправляется в систему для выполнения, и он будет вызываться, как указано выше, но через много времени, указанного выше.

#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

Я думаю, проблема в том, как вы устанавливаете родительские указатели. Обратите внимание, что вы настроили parents как

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

Это создает одну запись в parent массив для каждого ребра в графе, плюс один дополнительный. Однако у каждого узла есть родительский элемент, а не каждое ребро, и количество узлов в графе может быть больше количества ребер плюс один. Например, предположим, что вы получили этот набор ребер:

1  2
3  4
5  6

Этот график явно содержит шесть узлов (пронумерованных 1 ... 6), но ваш код освободит место только для 4 записей в parents,

Попробуйте изменить свой код так, чтобы вы установили parents чтобы получить правильный размер, возможно, найдя максимальный и минимальный пронумерованный узел в списке ребер и определив размер массива соответствующим образом. В качестве альтернативы рассмотрите возможность использования std::unordered_map<int, int>, который более гибок, если номера вершин не начинаются непрерывно с 0.

Надеюсь это поможет!