Рис. 5 Тест № 1. Расчет гамильтоновой цепи.

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

      Рис. 6 Другой граф с 6-ю вершинами 

Рис. 7 Тест № 2

 

Литература.

1. В.С. Гапанович, И. В. Гапанович «Дискретная математика», уч. пособие для студентов ИВТ, ТГНГУ, Тюмень, 2002.
2. http://programmersclub.ru/
3. 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;

                             }