Внедрение BFS в C++

Question

Я попытался реализовать алгоритм BFS с таблицей смежности, которая реализована с помощью массива векторов. Я начинаю хранить ввод от 1, а не от 0.

EDIT: Я обновил код: http://ideone.com/GZwPP, и теперь он компилируется и запускается, но когда я пытаюсь найти узел, которого нет в графике, я получаю эту ошибку:

terminate called after throwing an instance of 'std::out_of_range' 
    what(): vector::_M_range_check 
Aborted 

Answer 1

Ошибка на самом деле тонкая. У вас есть в вашем коде:

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

Какой тип size()? Это неподписанный тип. Поэтому, когда size() == 0 затем size() - 1 > 0 из-за arithmetic overflow. Вы должны изменить линию на:

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