Переделал рекурсивную реализацию ПВГ, написанную на pascal'е, на c++. Тестирую реализацию на графе, приведенном на рисунке. Вместо ожидаемого вывода 1 3 2 6 7 5 4 8 9 (корректный обход, приведенный на втором рисунке), я получаю 1 3 4 2 5 6 7 8 9 . Где ошибка в алгоритме?
volvo
10.05.2009 18:52
Цитата
Где ошибка в алгоритме?
Ошибка - не в алгоритме, а в реализации... И тебе, кстати, на эту ошибку указывает компилятор, внимательно смотри на все Warning-и, и увидишь, в чем дело.
Rocket
10.05.2009 19:10
Цитата(volvo @ 10.05.2009 15:52)
Ошибка - не в алгоритме, а в реализации... И тебе, кстати, на эту ошибку указывает компилятор, внимательно смотри на все Warning-и, и увидишь, в чем дело.
хм, мой компилятор никаких Warning-ов не выдаёт... А Ваш что показывает?
volvo
10.05.2009 19:17
Вот это:
Rocket
10.05.2009 19:27
Мой изначальный вариант был :
if ((a[v,i] != 0) && (Nnew[i])) Pg(i);
В a[v,i] почему-то оказывался адрес, а не значение из матрицы - решил использовать *(...). И о чём этот Warning? Как исправить?
volvo
10.05.2009 19:55
Цитата
Как исправить?
Очень просто: вспомнить, что в С есть "операция-запятая", которую ты пытаешься здесь использовать, но оно тебе не надо. А надо тебе обращаться к элементам многомерных массивов, и это делается так:
if (((a[v][i]) != 0) && (Nnew[i])) Pg(i);
Видишь разницу между тем, что ты пытался сделать, и тем, что написано у меня?
Rocket
10.05.2009 20:18
Цитата(volvo @ 10.05.2009 16:55)
Очень просто: вспомнить, что в С есть "операция-запятая", которую ты пытаешься здесь использовать, но оно тебе не надо. А надо тебе обращаться к элементам многомерных массивов, и это делается так:
if (((a[v][i]) != 0) && (Nnew[i])) Pg(i);
Видишь разницу между тем, что ты пытался сделать, и тем, что написано у меня?
Спасибо, volvo! В который раз подводит меня невнимательность... Ещё вопрос. Мне по заданию нужно отрисовывать граф и дерево, у меня написана программа на Delphi, которая рисует граф по матрице смежности, которую я пишу в файл в основной программе на c++, где реализован основной алгоритм (ПВШ, а теперь и ПВГ). Вобщем, как в данном случае матрицу смежности получить?
Rocket
11.05.2009 3:12
В принципе во всем разобрался сам и доработал программу. Вот окончательный вариант:
bool Nnew[15]; int n; int a[15][15]; // = {{0,0,1,1,0,0,0,0,0},{0,0,1,0,0,0,0,0,0},{1,1,0,0,0,1,0,0,0,},{1,0,0,0,1,0,0,0,0 },{0,0,0,1,0,0,1,1,0,},{0,0,1,0,0,0,1,0,0,},{0,0,0,0,1,1,0,1,1},{0,0,0,0,1,0,1,0 ,0},{0,0,0,0,0,0,1,0,0}}; int tree[15][15]; char esc;