-1

根据视频，我编写了 Kruskal 算法。但我有“小”问题——不是找到最低的权重，而是发现我的权重最高。这听起来可能很有趣，但我找不到我犯错的地方。

collection::collection(int vert){ coll = new SNode[vert]; }
collection::~collection(){}
void collection::Create(int vert)
{
    coll[vert].up = vert;
    coll[vert].rank = 0;
}
int collection::Find(int vert)
{
    /*if (coll[vert].up != vert) coll[vert].up = Find(coll[vert].up);
    return coll[vert].up;*/
    if (coll[vert].up == vert) return coll[vert].up;
    else Find(coll[vert].up);
}
void collection::Union(graf::Edges e)
{
    int home, dest;
    home = Find(e.v1);
    dest = Find(e.v2);
    if (home != dest){
        if (coll[home].rank > coll[dest].rank){ coll[dest].up = home; }
        else if (coll[home].rank < coll[dest].rank){ coll[home].up = dest; }
        else{
            coll[home].up = dest;             
            //if (coll[home].rank == coll[dest].rank) 
                coll[dest].rank++;
        }
    }
}

和主要算法。权重保存在称为“weightmat”的二维矩阵中。Vertex 是顶点的数量，Edges 是带有变量 v1,v2,weight 的结构体。使用这个结构，我创建了边数组。：

collection newcollection(vertex);

        struct CompareMat{
            bool operator()(Edges &node1, Edges &node2){
                if (node1.weight < node2.weight) return true;
                else return false;
            }
        };

        priority_queue<Edges, vector<Edges>, CompareMat> EdgesQueue;
        Edges temp;
        Edges* edges = new Edges[edge];
        Edges* MSTTree = new Edges[vertex-1];

        for (int i = 0; i < vertex; i++){
            for (int j = 0; j < vertex; j++)
            {
                if (nbhmat[i][j] != 0){
                    edges[i].v1 = i;
                    edges[i].v2 = j;
                    edges[i].weight = weightmat[i][j];
                }
            }
            EdgesQueue.push(edges[i]);
        }

        for (int i = 0; i < vertex; i++){
            newcollection.Create(i);
        }

        for (int i = 1; i < vertex; i++)          
        {
            do
            {
                temp = EdgesQueue.top();             
                EdgesQueue.pop();                    
            } while (newcollection.Find(temp.v1) == newcollection.Find(temp.v2));
            MSTTree[i - 1] = temp;
            newcollection.Union(temp);
        }

        cout << endl << endl << "Kruskal's algorithm for matrix:" << endl;
        for (int i = 0; i < vertex - 1; i++){
            cout << MSTTree[i].v1 << " " << MSTTree[i].v2 << " weight " << MSTTree[i].weight << endl;
        }
4

1 回答 1

2

priority_queue顶部有最大的元素（是的，比较器类相当于less），但首先需要最小的边。你需要颠倒你的CompareMat::operator()比较。

还有两个笔记。

首先，CompareMat::operator()您可以直接返回比较结果：

//return node1.weight < node2.weight; // your version
return node1.weight > node2.weight;  // correct version

其次，为什么需要优先队列？一个简单的排序就足够了，因为你似乎没有改变你的边缘。

于 2015-05-18T13:53:55.010 回答