尝试解决 HackerRank 上的 BFS 挑战时出现错误的分配异常

Question

所以我试图挑战：广度优先搜索：HackerRank 上的最短距离，但是当测试有大量 node/edges 时，我不断收到错误的分配异常。该程序在第一次测试中运行，所以我不认为，它的实现有问题。所以这里是实现：（抱歉缩进，我的第一个问题）

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


int main() {
//test numbers
int t;
//the cost
int cost = 6;
cin >> t;
//for each test
for (int nt = 0; nt < t; ++nt) {
    int n, e;
    int snode;
    queue <int> *que = new queue<int>();
    //read the node/edges
    cin >> n >> e;
    //distance/visited/parents arrays/adjlist vector
    int dist[n + 1] = {-1};
    bool visited[n + 1] = {false};
    int parents[n + 1] = {-1};
    vector< vector<int> > adjList(n + 1);

    //read into the adjlist, unoriented graph, each edge has 6 weight
    for (int ne = 0; ne < e; ++ne) {
        int x, y;
        cin >> x >> y;
        adjList[x].push_back(y);
        adjList[y].push_back(x);
    }

    //read the starting node
    cin >> snode;
    dist[snode] = 0;

    //do actual bfs
    que->push(snode);
    visited[snode] = true;
    while(!que->empty()) {
        int c_node = que->front();
        que->pop();
        for (int i = 0; i < adjList[c_node].size(); ++i) {
            if (visited[adjList[c_node].at(i)] == false) {
                que->push(adjList[c_node].at(i));
                parents[adjList[c_node].at(i)] = c_node;
                dist[adjList[c_node].at(i)] = dist[parents[adjList[c_node].at(i)]] + cost;
                visited[adjList[c_node].at(i)] == true;
            }
        }
    }

    //print at output the distance from the starting node to each other node
    //if unreachable, print -1
    for (int i = 1; i < n + 1; ++i) {
        if (i == snode) {

        } else if (dist[i] == 0 && i != snode) {
            cout << "-1 ";
        } else {
            cout << dist[i] << " ";
        }
    }
    cout << "\n";
}
return 0;
}

我是不是做错了什么，我没有看到其他人在网站的讨论部分抱怨这件事。我怎样才能避免抛出异常以及它从哪里来？谢谢！

Answer 1

我不知道你的异常的确切原因是什么；而且我不知道如何重现您的问题，因为（我想）取决于输入值。我想有很多输入值。

但是我看到了您的代码中的一些弱点（恕我直言），所以我试着让您注意它们。

1) 你在你的for周期

中分配了一个std::queue

queue <int> *que = new queue<int>();

但你从来没有释放过它；这是浪费内存

2) 你正在使用 C 风格的可变长度数组

int dist[n + 1] = {-1};
bool visited[n + 1] = {false};
int parents[n + 1] = {-1};

它们不是有效的 C++ 标准代码。我建议您使用标准容器（std::vector 或 std::queue）。

3) 您正在使用仅包含一个元素（-1 或 false）的初始化列表来初始化 C 风格的可变长度数组。我想您的意图是用 -1 和 false 初始化所有 n+1 元素。但是此语法仅使用 -1 和 false.

初始化数组的第一个元素

如果要将所有 n+1 元素初始化为 -1 和 false，解决方案是（再次）使用标准容器；举个例子

std::vector<int>   dist(n+1, -1);
std::vector<bool>  visited(n+1, false);
std::vector<int>   parents(n+1, -1);

4) 你访问数组时没有边界检查。例如：

cin >> snode;
dist[snode] = 0;

其中 snode 是一个 int 变量；如果你插入一个负值，或者一个超过 n 的值，你就会把 dist 写出它的范围，破坏内存。我想这可以解释你的 "bad alloc exception".

建议：（再次）使用标准容器而不是 C 风格的数组，并使用 at()（执行边界检查）而不是 []；所以

cin >> snode;
dist.at(snode) = 0;

5) 抱歉我的英语不好（好吧，我在开玩笑：这不是你的弱点之一；这是我的弱点之一）。

尝试解决 HackerRank 上的 BFS 挑战时出现错误的分配异常

bad alloc exception when trying to resolve BFS challenge on HackerRank

c++

exception

breadth-first-search

out-of-memory

bad-alloc