C++ STL 广度优先搜索

Question

#include <queue>
#include <vector>
#include <iostream>
using namespace std;


int main() {
int x;
cin >> x;
for(int tt=0;tt<x;tt++)
    {
    //cout << "HI" << endl;
    int n, m;
    cin >> n >> m;
    vector< vector<int> > g(n);
    for(long j =0; j< m;j++)
        {
        int u , v;
        cin  >> u >> v;

        g[u-1].push_back(v-1);
        g[v-1].push_back(u-1);

    }

    int s;
    cin >> s;

    vector<int> out(n,-1);
    vector<int> visited(n,0);
    int value = 0;
    queue<int> q;
    q.push(s-1);
    q.push(-1);
    visited[s-1] =1;
    int flag =0;
    while(!q.empty())
        {
        int v = q.front();
        out[v] = value;
        q.pop();
        if(v == -1)
            {
            value += 6;
        }
        else{
            for(vector<int>::iterator it = g[v].begin(); it != g[v].end();it++)
                {
                if(visited[*it] == 0)
                    {
                    q.push(*it);
                    visited[*it] =1;
                }
            }
        }

    }
    //cout << "hello" << endl;
    for(int k =0; k<n; k++)
        {
        if(k!= s-1)
            {
            cout << out[k] << " ";
        }
    }
    cout << endl;
    //cout << "yo";
}
//cout << "you";
return 0;
}

如果起始节点只有一级邻居，则此代码运行良好。为了使其适用于所有情况，当我更改

if(v == -1)
{
       value += 6;
}

至

if(v == -1)
{
     value += 6;
     if(!q.empty())
          q.push(-1);
}

它现在甚至不适用于所有测试用例。然后程序中止，来自 hacker rank 的错误信息是 *“解决方案”中的错误：双重释放或损坏（输出）：0x00000000009e5cf0 *

我不明白为什么会这样。为什么我在处理队列的时候for循环有问题。

Link 到 hackerrank 问题。

https://www.hackerrank.com/challenges/bfsshortreach

Answer 1

你需要

去掉 value ，不需要。
向量越界访问就在那里。什么是 out[-1] ？
适当的缩进
Bfs 总是明智地访问级别。您不需要通过在队列中推送负值来维护它。

正确的代码是：

#include <queue>
#include <vector>
#include <iostream>
using namespace std;


int main() {
    int x,n, m,u , v;
    cin >> x;
    for(int tt=0;tt<x;tt++){
        cin >> n >> m;
        vector< vector<int> > g(n);
        for(long j =0; j< m;j++){
            cin  >> u >> v;
            g[u-1].push_back(v-1);
            g[v-1].push_back(u-1);
        }

        int s;
        cin >> s;

        vector<int> out(n,-1);
        vector<bool> visited(n,0);
        queue< int > q;
        q.push(s-1);
        visited[s-1] =1;
        out[s-1]=0;

        while(!q.empty()){
            int v = q.front(); q.pop();

            for(vector<int>::iterator it = g[v].begin(); it != g[v].end();it++){
                if(visited[*it] == 0){
                    q.push(*it);
                    visited[*it] =1;
                    out[*it]=out[v]+6;
                }
            }

        }
        for(int k =0; k<n; k++){
            if(k!= s-1){
                cout << out[k] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

C++ STL 广度优先搜索

C++ STL Breadth first search

c++

breadth-first-search