С Новым годом! Форум программистов, компьютерный форум, киберфорум
C++ Builder
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.87/15: Рейтинг темы: голосов - 15, средняя оценка - 4.87
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110

Поиск гамильтоновых циклов в графе

05.12.2012, 17:03. Показов 3149. Ответов 12

Студворк — интернет-сервис помощи студентам
Имеется программа. если нажимать СЛЕДУЮЩИЙ ШАГ то программа работает правильно и ищет гамильтоновый цикл. если же нажать на ДОБАВИТЬ ВЕРШИНУ\РЕБРО то либо выдает ответ неправильно при нажатии на кнопку ОК либо возникает ошибка и высвечивает 165 строку:
C++
1
matrix[i][line]=1;
весь файл
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
//---------------------------------------------------------------------------
 
#include <vcl.h>
#include <stdio.h>
#pragma hdrstop
 
#include "Unit1.h"
#include "about.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
 
int numev=0;    //счетчик, необходимый для смены состояний построения графа
int xy[2][50];  //массив для хранения координат вершин на экране
int kv = 0;     //количество вершин
int line;       //переменная, необходимая для формирования матрицы смежности
bool select=false;    // отметка что вершину нашли
char **matrix;          //выделение памяти для будущей матрицы смежности
AnsiString way; //строка для вывода результатов в файл и на экран
int *buf;       //указатель на буфер
bool mark=false;     // удаление вершины
int kvdel=0;
 
 
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
 Status->Caption="Статус:\n\n...отмечаем вершины...";      //начальный статус
}
//---------------------------------------------------------------------------
 
// Функция проверки на повторы вершин в цепи
int __fastcall Repeat(int i, int num)
{
        for (int j=0; j<num; j++)       //цикл поиска такой же вершины
        {
        if (buf[j]==i) return 1;        //если  такая найдена, то повтор есть
        }
    return 0;   //нет повтора
}
// Функция для поиска новых вершин в цепи
 
void __fastcall Ways(int ver, int num)
{       select=false;
    if (mark==true) //если вершины уже удалялись
    {
        kvdel=buf[num]; //начинать отсчет вершин с
    }
    else kvdel=0; //иначе обнулить этот счетчик
    mark=false;
    for (int i=kvdel; i<kv; i++)        //цикл поиска возможных вершин
    {
        if (matrix[ver][i]==0) continue; //если нет ребра, следующий
        if (Repeat(i,num)) continue;    //если вершина уже была, следующий
        if (i==buf[num]) continue;
        ver=i;
        select=true; //отметка, что вершину нашли
        break;
    }
 
    if (select==true)   //если вершина найдена
    {
        buf[num]=ver;   //добавить ее в цепь
                num++;  //увеличить счетчик
                Ways(ver, num); //рекурсивно вызвать с новыми параметрами
     }
    else        //если вершина не найдена
    {
        if (num==kv)    //если длина цепи равна количеству вершин
        {
                way=buf[0]+1;
            for (int i=1; i<kv; i++)
            {
                way+=',';
                        way+=buf[i]+1;
            }
            if (matrix[buf[kv-1]][0]!=0) {way+=",1";
            Form1->Results->Items->Add(way); }  //вывод результата на экран
 
 
        }
       way=buf[0]+1;
        for (int i=1; i<num; i++)
            {
                way+=',';
                way+=buf[i]+1;
 
            }
            way+='\n';
        num--;  //уменьшаем счетчик
        mark=false;
        if (num!=0)     //если счетчик вершины не равен 0
        {
if (num!=kv-1) buf[num+1]=NULL; //и не равен количеству вершин, то обнулить
// следующую ячейку буфера
            mark=true;  //отметка о удалении вершины
            Ways(buf[num-1], num);      //поиск следующей вершины
        }
 
    }
 
}
 
 //----------------------------------------------------------------------------
//Функция поиска гамильтоновых циклов
void __fastcall Gamilton(void)
{
    buf=new int[kv]; //создание буфера
    buf[0]=0;
    for (int i=0; i<kv; i++) //обнуление буфера
    {
        buf[i]=NULL;
    }
    Ways(0, 1); //вызов функции для поиска новых вершин в цепи
 
}
//---------------------------------------------------------------------------
 
//---------------------------------------------------------------------------
 
//---------------------------------------------------------------------------
void __fastcall TForm1::DeskMouseDown(TObject *Sender, TMouseButton Button,
      TShiftState Shift, int X, int Y)
{               Label2->Visible=false;
        if (numev==0)   //если нажатий на кнопку «Далее» не производилось, то ставятся вершины
        {
 
                Desk->Canvas->Pen->Color=clGreen;       //цвет вершины = зеленный
                Desk->Canvas->Pen->Width=10;    //толщина пера=10 пикселей
                Desk->Canvas->MoveTo(X,Y);      //ставится точка
                Desk->Canvas->LineTo(X,Y);
                xy[0][kv]=X; //координаты вершины заносятся в массив
                xy[1][kv]=Y;
                Desk->Canvas->TextOutA(X+10, Y+10, AnsiString(kv=kv+1));
                //рядом выводится номер вершины
        }
        if (numev==1) //построение ребер
        {
                for (int i=0; i<kv; i++)
            {
                if ((X>(xy[0][i]-5))&&(X<(xy[0][i]+5)))
                {
                        if ((Y>(xy[1][i]-5))&&(Y<(xy[1][i]+5)))
                    {
                        if (select==false) //если вершина отмечена первой
                        {
                            Desk->Canvas->Pen->Color=clRed; //отметить ее красным цветом
                            Desk->Canvas->Pen->Width=7;
                            Desk->Canvas->MoveTo(xy[0][i],xy[1][i]);
                            Desk->Canvas->LineTo(xy[0][i],xy[1][i]);
                            line=i; //занести в переменную номер вершины
                            select=true; //поставить отметку, что одна вершина уже выделена
                        }
                        else //иначе
                        {
                            Desk->Canvas->Pen->Color=clBlack;
                            Desk->Canvas->Pen->Width=10;
                            Desk->Canvas->MoveTo(xy[0][line],xy[1][line]);
                            Desk->Canvas->LineTo(xy[0][line],xy[1][line]);
                            Desk->Canvas->Pen->Width=3;
                            Desk->Canvas->LineTo(xy[0][i],xy[1][i]); //провести линию
  /*постоянно тут ошибка*/    matrix[line][i]=1; //поставить отметку о ребре в матрице смежности
                            matrix[i][line]=1;
                            select=false; //ребро построено, выделенных вершин нет
                        }
                        break;
                    }
                }
            }
        }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BNextClick(TObject *Sender)
{
if (numev==0) //если нажатие производится в первый раз
{
    matrix=new char* [kv];      //создать массив для матрицы смежности
    for (int i=0; i<kv; i++) //обнулить этот массив
    {
        matrix[i]=new char [kv];
        for (int j=0; j<kv; j++)
        {
                matrix[i][j]=0;
        }
    }
        Status->Caption="Статус:\n\n...отмечаем ребра..."; //сменить статус
 
}
if (numev==1) //повторное нажатие на кнопку
{
    Status->Caption="Статус:\n\n Готово!"; //смена статуса
    BNext->Enabled=false;
    Gamilton(); //вывов функции Gamilton
            //если нет циклов
      if (Form1->Results->Items->Count == 0)   Form1->Results->Items->Add(" циклов нет");
}
numev++; //увеличение счетчика событий на единицу
 
 
}
//---------------------------------------------------------------------------
// новый граф
void __fastcall TForm1::Button1Click(TObject *Sender)
{     //очистка компонента
 Desk->Picture->Bitmap->FreeImage();
 Desk->Picture->Bitmap = NULL;
 Label2->Visible=true;
 // нулевые значения
 numev=0; // кол нажатий кнопки нехт
 BNext->Enabled=true; // видимость кнопки
 Status->Caption="Статус:\n\n...отмечаем вершины...";      //начальный статус
kv=0;
select=false;
char **matrix;          //выделение памяти для будущей матрицы смежности
AnsiString way; //строка для вывода результатов в файл и на экран
int *buf;       //указатель на буфер
mark=false;
kvdel=0;
Results->Items->Clear();
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button2Click(TObject *Sender)
{
// окно о программе
Form2->Show();
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button3Click(TObject *Sender)
{
// кнопка ДОБАВИТЬ ВЕРШИНУ
numev=0;
        Status->Caption="Статус:\n\n...отмечаем вершины..."; //сменить статус
 
        matrix=new char* [kv];      //создать массив для матрицы смежности
    for (int i=0; i<kv; i++) //обнулить этот массив
    {
        matrix[i]=new char [kv];
        for (int j=0; j<kv; j++)
        {
                matrix[i][j]=0;
        }
    }
 
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button5Click(TObject *Sender)
{
// кнопка ДОБАВИТЬ РЕБРО
numev=1;
Status->Caption="Статус:\n\n ...отмечаем ребра...!"; //смена статуса
 
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button7Click(TObject *Sender)
{
// кнопка ОК
    Status->Caption="Статус:\n\n Готово!"; //смена статуса
     Results->Items->Clear();// очищаем старый список
    Gamilton(); //вывов функции Gamilton
     if (Form1->Results->Items->Count == 0)   Form1->Results->Items->Add(" циклов нет");
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
05.12.2012, 17:03
Ответы с готовыми решениями:

Поиск Гамильтоновых циклов по матрице смежности
Здравствуйте! Помогите, пожалуйста, с написанием программы, которая бы искала гамильтоновы циклы по матрице смежности. Искала решение в...

Поиск циклов в графе. Поиск центра взвешенного графа
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

12
 Аватар для Antiplayer
129 / 112 / 39
Регистрация: 27.09.2012
Сообщений: 305
05.12.2012, 17:08
иван_пропал

Текст ошибки напиши пожалуйста
1
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110
05.12.2012, 17:16  [ТС]
Если нажать ДОБАВИТЬ РЕБРО после того как два раза нажал СЛЕД ШАГ и ДОБАВИТЬ ВЕРШИНУ и ответ уже не правильный
0
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110
05.12.2012, 17:29  [ТС]
либо такая ошибка
C++
1
First chance exception at $7742B727. Exception class EAccessViolation with message 'Access violation at address 00402B85 in module 'Project1.exe'. Write of address 01010100'. Process Project1.exe (15080)
эта ошибка указывает на строку
C++
1
matrix[i][line]=1;
0
 Аватар для Antiplayer
129 / 112 / 39
Регистрация: 27.09.2012
Сообщений: 305
05.12.2012, 17:31
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void __fastcall TForm1::BNextClick(TObject *Sender)
{
if (numev==0) //если нажатие производится в первый раз
{
    matrix=new char* [kv];      //создать массив для матрицы смежности
    for (int i=0; i<kv; i++) //обнулить этот массив
    {
        matrix[i]=new char [kv];
        for (int j=0; j<kv; j++)
        {
                matrix[i][j]=0;
        }
    }
        Status->Caption="Статус:\n\n...отмечаем ребра..."; //сменить статус
 
}
if (numev==1) //повторное нажатие на кнопку
{
    Status->Caption="Статус:\n\n Готово!"; //смена статуса
    BNext->Enabled=false;
    Gamilton(); //вывов функции Gamilton
            //если нет циклов
      if (Form1->Results->Items->Count == 0)   Form1->Results->Items->Add(" циклов нет");
}
numev++; //увеличение счетчика событий на единицу
У тебя здесь два условия. if numev==0 и numev==1; А numev++ ты делаешь при каждом нажатии, потом у тебя просто будет не срабатывать, потому что переменная станет равна 2,3...и тд. Есть смысл заменить if (numev!=0).
Но не думаю, что ошибка в этом.
1
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110
05.12.2012, 17:34  [ТС]
Но когда происходит нажатие кнопки добавть ребро/вершигу то numev присваиваю 0 и 1 соответственно
0
 Аватар для Antiplayer
129 / 112 / 39
Регистрация: 27.09.2012
Сообщений: 305
05.12.2012, 17:43
Цитата Сообщение от иван_пропал Посмотреть сообщение
Но когда происходит нажатие кнопки добавть ребро/вершигу то numev присваиваю 0 и 1 соответственно
Да и ладно, это все равно уже вряд ли относится к теме.
У тебя какой то явный прикол с матрицей, я и сам то новичек, и мне не понятно зачем вот такая запись, с выделением памяти:
char **matrix;

Объяви её просто:
char matrix;

Ты же все равно потом циклом её перезаполняешь.
1
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110
05.12.2012, 17:54  [ТС]
так вообще не запускается и ссылается на строку:
C++
1
    if (matrix[ver][i]==0) continue; //если нет ребра, следующий
0
 Аватар для Antiplayer
129 / 112 / 39
Регистрация: 27.09.2012
Сообщений: 305
05.12.2012, 18:03
хм, а если объявлять так:
C++
1
char matrix[1000][1000]; //заранее известный размер
0
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110
05.12.2012, 18:21  [ТС]
тоже не работает
0
return (true);
 Аватар для mimicria
1977 / 1112 / 221
Регистрация: 19.04.2011
Сообщений: 2,346
06.12.2012, 08:21
matrix задаётся 2 раза, глобально и внутри TForm1::Button1Click, это так и задумано?

Добавлено через 12 часов 50 минут
И так, на всякий случай:
C++
1
char **matrix;          //выделение памяти для будущей матрицы смежности
Это не выделение памяти, это объявление указателя. Выделение памяти осуществляется оператором new
Освобождение выделенной таким образом памяти в куче осуществляется оператором delete. Которые у вас почему-то не используются

Добавлено через 11 минут
Ну и собственно чему равно kv в момент выделения памяти?
C++
1
matrix=new char* [kv];
0
36 / 0 / 1
Регистрация: 05.10.2012
Сообщений: 110
06.12.2012, 16:10  [ТС]
Цитата Сообщение от mimicria Посмотреть сообщение
matrix задаётся 2 раза, глобально и внутри TForm1::Button1Click, это так и задумано?
Если честно эту прогу писал не я. Я просто хочу её изменить, добавить возможность добавления/удаления ребер/вершин
0
Почетный модератор
 Аватар для Памирыч
23248 / 9160 / 1084
Регистрация: 11.04.2010
Сообщений: 11,014
06.12.2012, 17:47
Тема закрыта из-за https://www.cyberforum.ru/orde... 21678.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
06.12.2012, 17:47
Помогаю со студенческими работами здесь

Поиск циклов в графе
Как узнать что граф имеет цикл?

Поиск Ф-циклов в графе
Нужно вывести на печать все фундаментальные циклы графа. Мой код выводит правильно(судя по данному примеру),но помоему он не разделяет сами...

Поиск циклов в ориентированном графе
Доброго времени суток. Может кому-нибудь из вас не составит особого труда, или возможно кто-то писал похожую программу. В общем, я написал...

Поиск отрицательных циклов в графе
Добрый день. Имеется код производящий обход графа. Мне надо &quot;Определить, имеются ли //у него циклы отрицательного веса. . Я...

Поиск отрицательых циклов в графе
подскажите пожалуйста, как определить, есть ли в графе отрицательные циклы....граф задаётся матрицей смежности P.S очень срочно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Закрытая тема Создать тему
Новые блоги и статьи
Первый деплой
lagorue 16.01.2026
Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru