1

I did some debugging and found it's the q.push_back(nbr) inside the while loop that's causing the error , I can't understand why the requested space is not being allocated. please help. Thank you .

vector<int> bfs2(int V, vector<int> adj2[])
{
    int src = 0;
    bool visited[V];

    for (int i = 0; i < V; i++)
    {
        visited[i] = false;
    }

    deque<int> q;
    q.push_back(src);
    visited[src] = true;

    vector<int> res;

    while (q.empty() != true)
    {
        int top = q.front();
        q.pop_front();

        res.push_back(top);

        vector<int> nbrsveec = adj2[top];

        for (int nbr : nbrsveec)
        {
            if (visited[nbr] != true)
            {
                // cout<<nbr<<endl;
                q.push_back(nbr);
                 visited[nbr] = true;
            }
        }
    }
     return res;
}
Eagle186f
  • 35
  • 4
  • 2
    To begin with `bool visited[V];` is a [variable-length array (VLA)](https://en.wikipedia.org/wiki/Variable-length_array) and [those are not really part of C++](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). Use `std::vector` instead. – Some programmer dude Jul 12 '21 at 08:24
  • 2
    There is no good reason to mix `std::vector` and VLAs. Some garbage websites teach this, but don't do it. – Evg Jul 12 '21 at 08:25
  • 2
    As for your problem, what is the value of `V`? What is the size of `q` when the exception happens? How many elements is there in the `adj2` array? How many elements in each vector? Do you ever go out of bounds of the array or the deque or the vectors? – Some programmer dude Jul 12 '21 at 08:25
  • 1
    All these containers contain _signed_ integers. Does any of the `adj2` vectors contain negative values? Please make a [mre] with example input and the expected output. – Ted Lyngmo Jul 12 '21 at 08:41
  • I restarted the system and somehow it's working fine now ,would still like to know what exactly happened . – Eagle186f Jul 12 '21 at 09:21
  • 1
    If a restart "fixed" it my guess would be some uninitialised values, please show a [mre] – Alan Birtles Jul 12 '21 at 09:43

1 Answers1

2

bad_alloc means that you are running out of memory. What system are you using?

Maybe you should define const vector<int> & nbrsveec to avoid the copy (or just directly use it in your for-loop).

moerker
  • 97
  • 5
  • 1
    [`std::bad_alloc`](https://en.cppreference.com/w/cpp/memory/new/bad_alloc) doesn't necessarily imply running out of memory, there are other reasons allocations could fail like trying to allocate more than is allowed in a single allocation or passing a negative number to an allocator which is then cast to a large unsigned number – Alan Birtles Jul 12 '21 at 09:41
  • I stand corrected. The idea was just to hint that somehow not more memory can be allocated. – moerker Jul 19 '21 at 10:51