c++ - 具有std::vector和std::queue的Prim算法，我的代码有什么问题？

我正在尝试使用STL和重载运算符()在Prim算法中对边缘进行排序，但是我遇到了运行时错误Invalid operator和Invalid Heap。

当我在CodeBlocks中编译我的代码时，一切正常，但Visual Studio 2015显示了运行时错误。我该怎么办？

struct edge {
    int cost;
    int start;
    int end;
};

struct sorting {
    bool operator() (const edge &a, const edge &b)
    {
        if (a.cost<b.cost) return false;
        else return true;
    }

};

priority_queue <  edge , vector <edge> , sorting> queue;

edge tree[1005];

int T[1000][1000];
int G[1005][1005];

bool ISIT[1005];
string STRINGS[1005];
int ID[40005];
int howmany = 0;
int howmanyneigh[1005];

void PRIM() {
    int w = 1;
    ISIT[w] = 1;
    edge K;
    howmany++;

    for (int i = 0; i<howmanyneigh[w]; i++) {
        K.start = w;
        K.end = G[w][i];
        K.cost = T[w][G[w][i]];
        queue.push(K);
    }


    while (howmany<N)
        edge b;
        b = queue.top();
        queue.pop();
        while (ISIT[b.end]) {
            b = queue.top();
            queue.pop();
        }

     ISIT[b.end] = 1;
        tree[howmany - 1] = b;

        for (int i = 0; i<howmanyneigh[b.end]; i++) {
            K.start = b.end;
            K.end = G[b.end][i];
            K.cost = T[b.end][G[b.end][i]];
            queue.push(K);
        }
        howmany++;
    }

}

最佳答案

您的sorting比较器似乎有问题。此比较器应为provide strict weak ordering。严格弱排序的要求之一是comp(a, a) == false。从更改您的sorting::operator()

 if (a.cost<b.cost) return false;
 else return true;

至:

 if (a.cost>b.cost) return true;
 else return false;

或者简单地:

 return a.cost > b.cost;

关于c++ - 具有std::vector和std::queue的Prim算法，我的代码有什么问题？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43909810/