Обход в ширину с++ Нужно понять ошибки.

[freelifekzn]

http://pastebin.com/5hVJkqZN

Почему алгоритм обхода в ширину не верен?
(пс. на ассимпотическую сложность можете не указывать, сам знаю)

[Abstraction]

Во-первых, отладчик (или отладочная печать) - что, собственно, происходит неверного.

Во-вторых... Вы меняете обходимый объект. Выкиньте из объекта графа компонент line и всё что с ним связано в отдельный класс - это уменьшит Ваши шансы запутаться. Желательно ещё пометить методы, не меняющие объекта, как константные и вынести поиск в отдельную функцию, передав ссылку на граф константным аргументом - тогда компилятор будет страховать Вас от ошибок.

В-третьих, если я правильно понимаю смысл line, Вы храните только вершины, но не стоимость попадания в них - но в процессе поиска в ширину мы можем посетить одну вершину несколько раз. Наконец, мы вовсе не храним и не анализируем длину пути - так что получается не "поиск в ширину", а "поиск в случайном порядке".

В-четвёртых, если у нас есть ребро из вершины 1 в вершину 10, а всего вершин 5, после первой итерации tested может оказаться равно 10 и условие while будет нарушено.

[freelifekzn]

Сообщение от Abstraction

Во-первых, отладчик (или отладочная печать) - что, собственно, происходит неверного.

Во-вторых... Вы меняете обходимый объект. Выкиньте из объекта графа компонент line и всё что с ним связано в отдельный класс - это уменьшит Ваши шансы запутаться. Желательно ещё пометить методы, не меняющие объекта, как константные и вынести поиск в отдельную функцию, передав ссылку на граф константным аргументом - тогда компилятор будет страховать Вас от ошибок.

В-третьих, если я правильно понимаю смысл line, Вы храните только вершины, но не стоимость попадания в них - но в процессе поиска в ширину мы можем посетить одну вершину несколько раз. Наконец, мы вовсе не храним и не анализируем длину пути - так что получается не "поиск в ширину", а "поиск в случайном порядке".

В-четвёртых, если у нас есть ребро из вершины 1 в вершину 10, а всего вершин 5, после первой итерации tested может оказаться равно 10 и условие while будет нарушено.

1 Не понял про отладчик(
2 А как передавать аргументы функции, если граф локальный? Одним из аргументов будет граф?int function(Graph a)?
3 Лайн-очередь. Сейчас речь идёт о том, можно ли попасть из A в B, без стоимости. Я только начал учить графы. Позже запишу.
4 Вы правы условие tested<=size излишне.

[freelifekzn]

Да..и тестед никогда не будет 10, при входном ребре 1 10.
Оно принимает номер наименьшего ребра.
можете привести пример, когда 2 раза посещаем 1 вершину?
Почему случайны поиск? Смеша tested строго определена следующим членом очереди, которые в свою очередь попадают туда в порядке обхода от наименьшей вершины.

[Abstraction]

1 Не понял про отладчик(

Или отладчик Вашей среды разработки (пункт меню "Отладка", "Debug"), или просто в разных местах кода делаете вывод текста вида "делаю то-то и то-то" ("помещаю в line вершину номер 7").

2 А как передавать аргументы функции, если граф локальный? Одним из аргументов будет граф?int function(Graph a)?

Да. Только лучше int function(Graph& a); А ещё лучше, как сказано - int function(const Graph& a);

3 Лайн-очередь. Сейчас речь идёт о том, можно ли попасть из A в B, без стоимости. Я только начал учить графы. Позже запишу.

Ну, ИМХО, к некоторым вещам лучше привыкать сразу, но как знаете. Такое смешение двух сущностей в одном классе делает код хуже читаемым и провоцирует ошибки.

можете привести пример, когда 2 раза посещаем 1 вершину?

Возможно, этого и не может случиться. Не то чтобы я в совершенстве понял, что у Вас происходит. Вы говорите, что что-то не работает. В отсутствие подробностей об этом "что-то" я высказываю догадки. Вот и всё.

[freelifekzn]

Не работало...уже исправил. Я просто хочу критики первый раз пишу с классами. Так..а в в самой функции при передаче ей указателя, как к объекту обращаться? &gr.блаблабла?

[Abstraction]

&gr.блаблабла?

Нет. И это не указатель, это ссылка. Синоним имени, в некотором смысле:

struct S {
  int a, b;
};

int function1(S s){
  s.a += 3;//Создана локальная копия аргумента, в неё внесены изменения.
  //На выходе из функции изменённая локальная копия будет уничтожена.
  return s.a; //Но вернётся изменённое значение
}

int function2(S& s){
  s.a += 3;//s - синоним для переданного аргумента, аргумент изменён.
  return s.a;
}

int function3(const S& s){
  //s.a += 3; //s - синоним переданного аргумента, но его изменения запрещены
  //Строка выше породит ошибку компиляции.
  return s.a;
}

int function4(S* s){
  s->a += 3; //Это указатель. Он отличается от ссылки тем, что к объекту надо
  //обращаться через оператор разыменования *; к полям объекта можно
  //также обращаться через оператор доступа по указателю ->
  return (*s).a;
}

int function5(S* s){
  S local; //Это локальная переменная функции. Она будет уничтожена на выходе.
  s = &local; //Указатель (в отличие от ссылки!) может сменить объект, 
  //на который он указывает
  s->a += 3; //Изменено то, на что СЕЙЧАС указывает s - т.е. объект local
  return s->a;
}

int function6(const S* s){
  //s->a += 3; //Как и в случае с константной ссылкой, указатель на константный
  //объект не может менять этот объект. Ошибка компиляции.
  return (*s).a;
}

int function7(const S* s){
  S local;
  s = &local; //А вот это, внезапно, возможно: изменить САМ s, не меняя
  //переданного объекта.
  //(*s).a += 3; //Однако s, как переменная, по-прежнему несёт
  //"клеймо постоянства": через него нельзя менять указуемый объект. Ошибка.
  return s->a;
}

//Теперь вызовы:
S object;
object.a=0; object.b=2;
std::cout << function1(object);//Выведено 3, object.a по-прежнему 0
std::cout << function2(object);//Выведено 3, object.a стало равно 3
//Обратите внимание - вызовы ничем не отличаются.
std::cout << function3(object);//Выведено 3, object не изменился
//Что бы ни содержала function3, заголовок гарантирует, что object не 
//изменится в результате вызова
std::cout << function4(&object);//Выведено 6, object.a равно 6
//Но сейчас мы этого ожидали, ведь при вызове пришлось дописать &
std::cout << function5(&object);//Выведено 9, object не изменился
std::cout << function6(&object);//Выведено 6, object не изменился
//Опять же, в этот раз нам гарантировали неизменность object
std::cout << function7(&object);//Выведено 6, object не изменился