Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов (стр. 2 из 2)
- Программа предусматривает действительное наличие гамильтоновой цепи в заданном графе. В случае, если цепи в графе не существует, то программа этого определить не сможет и либо произойдёт зависание программы из-за того что основной поисковый цикл войдёт в бесконечное цикл, либо программа выдаст ошибочный результат.
- В блоке 2 при ручном вводе значений, допускается ввод только 0 или 1. Другие значения, а также пустая ячейка матрицы смежности приведёт либо к ошибке программы, либо к её зависанию.
6. Тестирование программы.
Первый тест уже подробно продемонстрирован на рис. 1, 2, 3.
Далее будут продемонстрированы ещё два более сложных теста программы с рисунками графов и снимками внешнего вида программы после расчёта гамильтоновых цепей.Рис. 4 Граф с 6-ю вершинами.
Рис. 5 Тест № 1. Расчет гамильтоновой цепи.  |
Рис. 6 Другой граф с 6-ю вершинами
Рис. 7 Тест № 2Литература.
- В.С. Гапанович, И. В. Гапанович «Дискретная математика», уч. пособие для студентов ИВТ, ТГНГУ, Тюмень, 2002.
- http://programmersclub.ru/
- http://www.realcoding.net/article/rubric/CCplus
Приложение 1. Листинг программы.
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include <fstream.h>
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TFA *FA;
int v, i, j, y;
AnsiString namegraf;
int **g = new int *[v]; //массив указателей на строки
//---------------------------------------------------------------------------
__fastcall TFA::TFA(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TFA::BnewgrafClick(TObject *Sender)
{
for (int s=0; s<StringGrid1->RowCount; s++)
{
StringGrid1->Rows[s]->Clear();
}
memo1->Lines->Clear();
Eput->Clear();
v=StrToInt(Ev->Text);
namegraf=Enamegraf->Text;
namegraf=namegraf+".txt";
StringGrid1->RowCount=v+1;
StringGrid1->ColCount=v+1;
for (int i=1; i<v+1; i++)
{
StringGrid1->Cells[0][i]=IntToStr(i-1);
StringGrid1->Cells[i][0]=IntToStr(i-1);
}
StringGrid1->Cells[0][0]="";
}
//---------------------------------------------------------------------------
void __fastcall TFA::FileListBox1Click(TObject *Sender)
{
for (int s=0; s<StringGrid1->RowCount; s++)
{
StringGrid1->Rows[s]->Clear();
}
memo1->Lines->Clear();
Eput->Clear();
ifstream f(FileListBox1->FileName.c_str());
f>>v;
StringGrid1->RowCount=v+1;
StringGrid1->ColCount=v+1;
for (int i=1; i<v+1; i++)
{
StringGrid1->Cells[0][i]=IntToStr(i-1);
StringGrid1->Cells[i][0]=IntToStr(i-1);
}
StringGrid1->Cells[0][0]="";
//создаём динамический массив для таблицы смежности графа
int **g = new int *[v]; //массив указателей на строки
for (int i=0; i<v; i++) //выделение памяти под каждую строку
g[i] = new int [v];
//заполняем его из файла
for (int i=0; i<v; i++)
for (int j=0; j<v; j++)
f>>g[i][j];
f.close(); //закрываем файл
//заполняем StringGrid1
for (int i=0; i<v; i++)
for (int j=0; j<v; j++)
StringGrid1->Cells[i+1][j+1] = g[i][j];
//создаём массив маршрута гамильтоновой цепи
int *p = new int [v];
for (int i=0; i<v; i++) //обнуляеммассивпути
{p[i]=-1;};
}
//---------------------------------------------------------------------------
void __fastcall TFA::BstartClick(TObject *Sender)
{
//создаём динамический массив для таблицы смежности графа
int **g = new int *[v]; //массив указателей на строки
for (int i=0; i<v; i++) //выделение памяти под каждую строку
g[i] = new int [v];
//заполняемегоиз SrtingGrid1
for (int i=0; i<v; i++)
for (int j=0; j<v; j++)
g[i][j]=StrToInt(StringGrid1->Cells[i+1][j+1]);
//создаём массив маршрута гамильтоновой цепи
int *p = new int [v];
for (int i=0; i<v; i++) //обнуляеммассивпути
{p[i]=-1;};
memo1->Lines->Append("0");
//поиск гамильтоновой цепи
AnsiString put;
int s=0,t=0; //счетчики
int temp=0;
AnsiString tempput; //временныйпуть
int y=0;
for (int k=0; k<v; k++) //для K-той вершины пути
{
if (p[0]==-1)
{
p[0]=0; //начнём поиск с первой вершины (нулевая для матрицы)
}
if (p[k]<0) //если К-тая вершина пути пуста, то ищем эту вершину
{
for (i=p[k-1]; i<v; i++) //присвоить i последнюювершинупути
for (j=temp; j<v; j++) //i - строка, j - столбец
switch (y=g[i][j])
{
case 1: //если от вершины идёт ребро, то
for (int x=0; x<v; x++) //проверяем была ли уже такая вершина
{
if (p[x]==j) //если да
{
s++; //фиксируем это счетчиком
}
}
if (s>0) //если счетчик изменится, значит
{ //такая вершина уже есть в пути
s=0;
break; //обнуляем счетчик и выходим из цикла
}
if (s==0) //если счетчик не изменился, то
{ //записываем вершину в путь
p[k]=j; //продолжаем поиск с найденной вершины
if (j+1==v) //если это последняя j-тая вершина,
{ //а ребер больше нет, то
if (p[v-1]!=-1) //проверяем готова ли цепь
{ //если последняя вершина пути не пуста
for (int x=0; x<v; x++)
{
put=put+IntToStr(p[x]);
}
Eput->Text=put;
return;
}
}
if (p[v-1]<0) //еслицепьнеготова
{ //записать ее в tempput
for (int x=0; x<v; x++)
{ //убрав -1
if (IntToStr(p[x])!=-1)
{
tempput=tempput+IntToStr(p[x]);
}
}
//сравнить это значение пути с уже имеющимися в memo1
for (int str=0; str<memo1->Lines->Count; str++)
{
if (StrToInt(tempput)==StrToInt(memo1->Lines->Strings[str]))
{ //если найдено совпадение
t++; //фиксируем это счетчиком
}
}
if (t==0) //если счетчик не изменится
{
memo1->Lines->Append(tempput); //записатьнеполныйпутьв memo1
temp=0;
}
else if (t>0) //если счетчик изменится, т.е. совпадение есть
{
t=0;
temp=p[k-1]; //вернуться на предыдущую вершину
if (temp<v-1)
{
temp++;
}
else if (temp==v-1) //контроль temp чтобы не вышел за границы
{ //возможного кол-ва вершин
temp=0;
}
if (temp>v-1)
{
temp=0;
p[0]=0;
}
for (int x=0; x<v; x++) //стираем все вершины до той,
{ //с которой нужно вести поиск
if (x>=k-1)
{
p[x]=-1;
}
}
k=k-2;
}
tempput="";
j=v-1;
i=v-1;
}
}
break;
case 0: //если идет не ребро
if (j+1==v) //если это последняя j-тая вершина,
{ //а ребер больше нет, то
if (p[v-1]!=-1) //проверяем готова ли цепь
{ //если последняя вершина пути не пуста
for (int x=0; x<v; x++)
{
put=put+IntToStr(p[x]);
}
Eput->Text=put;
return;
}
if (p[v-1]<0) //еслицепьнеготова
{ //записать ее в tempput
for (int x=0; x<v; x++)
{ //убрав -1
if (IntToStr(p[x])!=-1)
{
tempput=tempput+IntToStr(p[x]);
}
}
//сравнить это значение пути с уже имеющимися в memo1
for (int str=0; str<memo1->Lines->Count; str++)
{
if (StrToInt(tempput)==StrToInt(memo1->Lines->Strings[str]))
{ //если найдено совпадение
t++; //фиксируем это счетчиком
}
}
if (t==0) //если счетчик не изменится
{
memo1->Lines->Append(tempput); //записать неполный путь в memo1
}
else if (t>0) //если счетчик изменится, т.е. совпадение есть
{
t=0;
}
temp=p[k-1]; //вернуться на предыдущую вершину
if (temp<v-1)
{
temp++;
p[k-1]=-1;
}
else if (temp==v-1) //контроль temp чтобы не вышел за границы
{ //возможного кол-ва вершин
temp=0;
for (int x=0; x<v; x++) //стираем все вершины до той,
{ //с которой нужно вести поиск
if (x>=k-1)
{
p[x]=-1;
}
}
}
if (temp>v-1)
{
temp=0;
p[0]=0;
}
k=k-2;
tempput="";
j=v-1;
i=v-1;
}
}
break;
}
}
}
;
}
//---------------------------------------------------------------------------
void __fastcall TFA::BsavegrafClick(TObject *Sender)
{
//создаём динамический массив для таблицы смежности графа
int **g = new int *[v]; //массив указателей на строки
for (int i=0; i<v; i++) //выделение памяти под каждую строку
g[i] = new int [v];
//заполняемегоиз StringGrid1
for (int i=0; i<v; i++)
for (int j=0; j<v; j++)
g[i][j]=StrToInt(StringGrid1->Cells[i+1][j+1]);
ofstream f(namegraf.c_str());
f<<v<<endl;
//заполняем файл графом g
for (int i=0; i<v; i++)
for (int j=0; j<v; j++)
f<<g[i][j]<<" ";
f.close(); //закрываем файл
FileListBox1->Update();
}
//---------------------------------------------------------------------------
void __fastcall TFA::BdelgrafClick(TObject *Sender)
{
DeleteFileA(FileListBox1->FileName);
FileListBox1->Update();
}
//---------------------------------------------------------------------------
void __fastcall TFA::N3Click(TObject *Sender)
{
ShowMessage("Курсовая работа по дискретной математике. Выполнил студент гр. АСОиУзс-07-01 Быстров Евгений, вариант №13");
}
//---------------------------------------------------------------------------