分割错误（核心转储）实现union-find C++

问题描述：

我正在做Kruskal最小生成树并编写了一些union-find函数来执行set操作。以前它工作得很好，直到我将KruskalMST（）函数从传值改为传递引用。现在，它看起来像这样：分割错误（核心转储）实现union-find C++

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)

似乎崩溃在迭代的随机数，但始终没有脱离的，对循环。这有什么可能的原因？请帮帮我！

编辑

查找和联盟功能：

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); 
    } 
}

我没有改变联盟找兼职，只是改变KruskalMST(vector<Edge> EV, vector<Node> mynodelist)到KruskalMST(vector<Edge>& EV, vector<Node>& mynodelist)

如果您之前没有使用过调试器，现在是做这件事的好时机。使用'-g'选项生成调试信息，然后在调试器中运行程序。调试器会在发生崩溃时停止，让您检查函数调用堆栈以及变量的值。至少编辑你的问题以包含函数调用堆栈。 –

哦，顺便说一下，你可能想用'-Wall -Wextra'编译你的代码来获得更多的警告。虽然警告不是错误，但它们通常会指出一些可能导致未定义行为的问题。 –

你可以发布Union函数的代码吗？ – nemasu

答

你的回报矢量是一个指针，但传递的向量按值获取项目。当你建立结果时，你正在推送指向传入EV矢量值的指针。这不是安全的。如果在任何时候改变EV矢量 - 在功能期间或甚至在返回之后 - 该矢量中的值的地址将改变。因此访问返回的指针将是无效的。

如果KruskalMST()方法按值取参数，这会使情况更糟，因为您会返回指向已销毁向量中元素的指针。

你能给我一些建议，我应该怎么做？我只是希望输出是一个向量'矢量 mst'，什么是安全和有效的内存记录方法？ –

分割错误（核心转储）实现union-find C++

相关推荐