BFS Implementation in C++

0
votes

I have tried to implement the BFS algorithm with an adjasency table which is implemented with an array of vectors. I start storing input from 1 and not from 0.

EDIT: I have updated the code: http://ideone.com/GZwPP and now it compiles and runs but when I try to search for a node which is not in the graph I get this error:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check
Aborted
1
c++breadth-first-search
The error looks like a problem in your build environment. It's missing symbols that should be provided by the compiler's utility library for supporting exceptions. – Ben Jackson
I can confirm, code works fine for me – Alex
The code compiles - ideone.com/dT2fD ignore the runtime error. – Luchian Grigore
@GeorgeStamatiou What line triggers the out_of_range exception? Do you have the call stack? Did you try to debug that? – Eitan T
I have tried to backtrace in GDP but it gave me the same error. – user804371

1 Answers

1
votes

The bug is really subtle. You have in your code:

for(i = 1; i <= adj[front].size() - 1 && adj[front].at(0) != 0; i++)

What type is size()? It is an unsigned type. So when size() == 0 then size() - 1 > 0 because of arithmetic overflow. You should change the line to:

for(i = 1; i < adj[front].size() && adj[front].at(0) != 0; i++)