在c++中做BFS时出现分段故障。

Question

我已经开始学习图形理论，正在做一道Hackerrank的题。https:/www.hackerrank.comchallengesbfsshortreachproblem基本上是要求执行BFS，将同一级别的所有元素标记为6*level，将所有不可到达的节点标记为-1。我尝试了以下方法，在创建我的adjList时，我得到了一个seg故障，我是否访问了输入的内容 vector<vector<int>> edges 还是有其他的问题.这是我的2-3个bfs的代码，所以我也想知道我的实现是否没问题，是做了它应该做的事情还是我做的不对？(我知道这个问题问的是 ans vector 将要 1-n 而不是像现在这样的访问顺序，也许我可以用一个地图，或者一个直方图，或者用原始值的对子，然后用后面的第二种排序什么的，还没有想好这部分）谢谢你。

代码。

vector<vector<int>> Graph(vector<vector<int>>& edges) {
    vector<vector<int>> ans;
    for(auto i: edges) {
        ans[i[0]].push_back(i[1]);
        ans[i[1]].push_back(i[0]);
    } return ans;
}

vector<int> bfs(int n, int m, vector<vector<int>>& edges, int s) { // no. of vertex, no. of edges, edges, start
    vector<vector<int>> adjList;
    // adjList.resize(n);
    adjList = Graph(edges);
    vector<int> ans(n + 1);
    vector<bool> visited(n + 1);
    queue<int> q;
    visited[s] = true;
    q.push(s);
    int i = 0;
    while(!q.empty()) {
        int temp = q.front(); q.pop();
        // int len = q.size();
        for(int j: adjList[temp]) {
            if(!visited[j]) {
                ans.push_back(6*i);
                visited[j] = true;
                q.push(j);
            }
        } i++;
    }
    for(int i = 1; i <= n; i++) if(i % 6 != 0 && i != s) ans[i] = -1;
    ans.erase(ans.begin() + s);
    return ans;
}

已测试

int main() {
    vector<vector<int>> edges = {{1, 2}, {1, 3} };
    vector<int> som = bfs(4, 2, edges, 1);
    return 0;
}

Answer 1

的 vector<vector<int>> ans 的顶点数量来调整大小。Graph.

工作代码：

vector<vector<int>> Graph(vector<vector<int>>& edges, int n) {
    vector<vector<int>> ans(n);
    for(auto i: edges) {
        ans[i[0]].push_back(i[1]);
        ans[i[1]].push_back(i[0]);
    } return ans;
}

vector<int> bfs(int n, int m, vector<vector<int>>& edges, int s) {
    vector<vector<int>> adjList;
    adjList = Graph(edges, n + 1);
    vector<int> ans(n + 1, -1);
    ans[s] = 0;                          // starting point
    vector<bool> visited(n + 1);
    queue<int> q;
    visited[s] = true;
    q.push(s);
    while(!q.empty()) {
        int temp = q.front(); q.pop();
        for(int i: adjList[temp]) {
            if(!visited[i]) {
                ans[i] = 6 + ans[temp];   // just use it as DP array!
                visited[i] = true;
                q.push(i);
            }
        }
    }
    ans.erase(ans.begin() + s); // remove starting point(as per question)
    ans.erase(ans.begin());     // remove 0 (graph starts from 1)
    return ans;
}