c ++:在圖類中的廣度優先搜索中的分段錯誤 - c++ : segmentation fault in breadth first search in graph class -开发者知识库

c ++:在圖類中的廣度優先搜索中的分段錯誤 - c++ : segmentation fault in breadth first search in graph class -开发者知识库,第1张

I am a bit experienced in c and tried to implement a graph class with nodes which are numbered from 1 to n (and every edge is weighted with 6) with a method to find all reachable nodes from a given one by breadth depth first. However, in some testcases I get a segmentation fault and don't know why. The error seems to happen when i push the next node to visit into the queue - if I comment out this line, the program works. I used heap storage to avoid any problems with any empty pointers, still I get this kind of fault. I would be thankful for any help.

我在c 方面有一點經驗,並試圖實現一個圖表類,其節點編號從1到n(每個邊用6加權),方法是首先通過寬度深度從給定的節點中找到所有可到達的節點。但是,在某些測試用例中,我遇到了分段錯誤而不知道原因。當我推動下一個節點訪問隊列時,似乎發生了錯誤 - 如果我注釋掉這一行,程序就可以正常工作。我使用堆存儲來避免任何空指針的任何問題,但我仍然遇到這種錯誤。我會感謝任何幫助。

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

class node{
public:
std::vector<node*> connections;
int number;

node(int x){
    number = x;
}

void connect(node *B){
    connections.push_back(B);
}

bool hasConnectionTo(int y){
    for(node *n : connections){
        if(n->number == y){
            return true;
        }
    }
    return false;
}
};

class graph{
public:
std::vector<node> nodes;

bool nodeExists(int x){
    for(node n : nodes){
        if(n.number == x){
            return true;
        }
    }
return false;
}

node* find(int x){
    node *returnNode;
    if(nodeExists(x)){
        for(int i = 0 ; i < this->nodes.size() ; i  ){
            if(this->nodes[i].number == x){
                returnNode = &this->nodes[i];
                return returnNode;
            }
        }
    }    
    return NULL;
}    

void addEdge(int x, int y){     //adds a connection between node1 and node2
    if(this->nodeExists(x) && this->nodeExists(y)){
        node *nodex = this->find(x);
        node *nodey = this->find(y);
        if(!nodex->hasConnectionTo(y)){
            nodex->connect(nodey);
            nodey->connect(nodex);
        }
    }else if(this->nodeExists(x) && !this->nodeExists(y)){
        node *nodex = this->find(x);
        node *nodey = new node(y);
        nodex->connect(nodey);
        nodey->connect(nodex);
        this->nodes.push_back(*nodey);
    }else if(this->nodeExists(y) && !this->nodeExists(x)){
        node *nodey = this->find(y);
        node *nodex = new node(x);
        nodey->connect(nodex);
        nodex->connect(nodey);
        this->nodes.push_back(*nodex);
    }else{
        node *nodex = new node(x);
        node *nodey = new node(y);
        nodex->connect(nodey);
        nodey->connect(nodex);
        this->nodes.push_back(*nodex);
        this->nodes.push_back(*nodey);
    }
}

void breadthFirstLookup(int root, int numberOfNodes){
    std::queue<node*> q;
    int distances[numberOfNodes];    //store the distance to node n in distances[n-1]
    bool visited[numberOfNodes];
    for(int j = 0 ; j < numberOfNodes ; j  ){
        distances[j] = 0;
        visited[j] = false;
    }
    if (this->nodeExists(root)){
        node *start = new node(1);
        start = this->find(root);
        node *tmp = new node(1);
        q.push(start);
        while(!q.empty()){
            tmp = this->find(q.front()->number);
            visited[tmp->number-1] = true;
            q.pop();
            for(int i = 0 ; i < tmp->connections.size() ; i  ){
                if(!visited[tmp->connections[i]->number-1]){
                    distances[tmp->connections[i]->number-1] = distances[tmp->number-1]   6;
                    q.push(tmp->connections[i]);    //<--this is where the error happens
                }
            }
        }
    }
    for(int k = 0 ; k < numberOfNodes ; k  ){    //print distance to all nodes except the root node, -1 if no connections exists
        if(k 1 != root){
            if(distances[k] != 0){
                cout << distances[k] <<" ";
            } else{
                cout << -1 <<" ";
            }
        }
    }
    cout <<"\n";
}
};

1 个解决方案

#1


1  

The basic problem is that your nodes have pointers to each other, but you store nodes in a vector. A vector has the right to move its elements around in ways that can invalidate old pointers. And even if the vector never moved any of its elements, you have code like this:

基本問題是您的節點具有彼此的指針,但您將節點存儲在向量中。向量有權以可能使舊指針無效的方式移動其元素。即使向量從未移動過任何元素,您也可以使用以下代碼:

else if(this->nodeExists(x) && !this->nodeExists(y)){
  node *nodex = this->find(x);
  node *nodey = new node(y);
  nodex->connect(nodey);
  nodey->connect(nodex);
  this->nodes.push_back(*nodey);
}

After nodex->connect(nodey);, node x contains the pointer nodey. But after nodes.push_back(*nodey); (the this-> is superfluous), the vector nodes contains a copy of the node that nodey points to. So nodey -- which is the pointer stored in node x -- points to a node which still exists, but is not in the vector.

在nodex->​​ connect(nodey);之后,節點x包含指針nodey。但是在nodes.push_back(* nodey)之后; (this->是多余的),向量節點包含nodey指向的節點的副本。因此nodey(存儲在節點x中的指針)指向仍然存在但不在向量中的節點。

The specific way in which this code causes a segfault depends on code you haven't shown us, but this handling of pointers is the fundamental cause.

此代碼導致段錯誤的具體方式取決於您未向我們展示的代碼,但這種指針處理是根本原因。

最佳答案:

DABAN RP主题是一个优秀的主题,极致后台体验,无插件,集成会员系统
U19学习网站 » c ++:在圖類中的廣度優先搜索中的分段錯誤 - c++ : segmentation fault in breadth first search in graph class -开发者知识库