2

我正在做 Kruskal 最小生成树并编写了一些联合查找函数来执行集合操作。以前它运行良好，直到我将 KruskalMST() 函数从按值传递更改为按引用传递。现在它看起来像这样：

vector<Edge*> KruskalMST(vector<Edge>& EV, vector<Node>& mynodelist){
    int setcount = NVAR;
    vector<Edge*> mst;   //mst
    vector<int> umark;         //setmark
    for(int i=0;i<NVAR;i++)
    {
      umark.push_back(i);
    }


    /*Kruskal*/    
    while(setcount>1){
        cout<<"# USER DEFINED EDGES = "<<USER_DEFINED_EDGES<<endl;
        cout<<"Threshold = "<<THRESHOLD<<endl;
        cout<<"# edges = "<<EV.size()<<endl;

        for(int j = 0; j < EV.size(); j++){
            cout<<"Find(v1) = "<<Find(&mynodelist[EV[j].readv1()->readi()])->readi()<<endl;
            cout<<"Find(v2) = "<<Find(&mynodelist[EV[j].readv2()->readi()])->readi()<<endl;
            if(Find(&mynodelist[EV[j].readv1()->readi()])->readi()!= Find(&mynodelist[EV[j].readv2()->readi()])->readi()){

                mst.push_back(&EV[j]);                  //add this edge to mst
                cout<<"mst.size() = "<<mst.size()<<endl;    
                Union(&mynodelist[EV[j].readv1()->readi()], &mynodelist[EV[j].readv2()->readi()]);          //
                cout<<"after Find(v1) = "<<Find(&mynodelist[EV[j].readv1()->readi()])->readi()<<endl;
                cout<<"after Find(v2) = "<<Find(&mynodelist[EV[j].readv2()->readi()])->readi()<<endl;
            }
        }
      cout<<"it never reaches here"<<endl;
      std::list<int> listmark;
      for(int i=0;i<NVAR;i++){
         mynodelist[i].setmark(Find(&mynodelist[i]));
         listmark.push_back(mynodelist[i].readmark());
      }
      listmark.sort();
      listmark.unique();
      setcount = listmark.size();

      umark.clear();
      umark.insert(umark.begin(), listmark.begin(),listmark.end());   //assign list to vector (clear first)


      cout << "# disjoint components: " << setcount << endl;
      cout << endl;

      }
    return mst;
    }

奇怪的是它跑了一段时间就崩溃了，屈服了

All Vertices: #100
All Edges: #4950
# USER DEFINED EDGES = 0
Threshold = 15
# edges = 4950
Find(v1) = 96
Find(v2) = 36
mst.size() = 1
after Find(v1) = 96
after Find(v2) = 96
Find(v1) = 81
Find(v2) = 48
mst.size() = 2
after Find(v1) = 81
after Find(v2) = 81
...
...
Find(v1) = 57
Find(v2) = 84
mst.size() = 26
after Find(v1) = 84
after Find(v2) = 84
Find(v1) = 29
Segmentation fault (core dumped)

似乎它在随机迭代次数时崩溃，但从未退出该 for 循环。造成这种情况的可能原因是什么？请帮帮我！

编辑

查找和联合功能：

Node* Find(Node* node) {          //FINDING THE REPRESENTATIVE FOR EACH SET
    Node* temp;
    Node* root = node;

    while (root->readp() != NULL)
        root = root->readp();    //readp() reads its parent

    /* Updates the parent pointers */
    while (node->readp() != NULL) {
        temp = node->readp();
        node->setp(root);   //setparent
        node = temp;
    }

    return root;
}


/* Merges two nodes based on their rank */
void Union(Node* node1, Node* node2) {
    Node* root1 = Find(node1);
    Node* root2 = Find(node2);

    if (root1->readrank() > root2->readrank()) {                //WHOSE RANK IS LARGER, WHO'S THE PARENT. RANK IS THE NUMBER OF CHILDREN FOR THE VERTEX
        root2->setp(root1);
    } else if (root2->readrank() > root1->readrank()) {
        root1->setp(root2);
    } else {                                        //EQUAL, ROOT1'S RANK INCREMENTS AND IS THE PARENT
        root2->setp(root1);
        root1->setrank((root1->readrank())+1);
    }
}

我没有更改 Union-find 部分，只是更改KruskalMST(vector<Edge> EV, vector<Node> mynodelist)为KruskalMST(vector<Edge>& EV, vector<Node>& mynodelist)

4

1 回答 1

3

您的返回向量是指针，但传递的向量按值获取项目。当您构建结果时，您正在推动指向传递的 EV 向量中的值的指针。这不是保险箱。如果您在任何时候更改了传递的 EV 向量——在函数期间甚至在KrustalMST()返回之后——该向量中的值的地址将会改变。因此访问返回的指针将是无效的。

如果该KruskalMST()方法按值获取参数，那会使情况变得更糟，因为您将返回指向已破坏向量中元素的指针。

于 2013-09-25T05:29:38.017 回答