Нужны исходники программы по нахождению гамильтонов циклов

[антонха]

Нужны исходники программы по нахождению гамильтонов циклов

[stragner]

антонха, насколько мне известно, не существует эффективного алгоритма по нахождению гамильтоновых циклов, так что надо решать в лоб - полным перебором. Исходники под рукой нет, да к тому же неизвестно, на каком языке вам они нужны, может на FORTRAN'e :twisted:

[антонха]

stragner, Мне нужны они на С++, можете мне помочь?

[stragner]

вот примерная программа, для построения гамильтонова цикла:

#define MAXN 1000

int matrix[MAXN][MAXN]; //Матрица смежности - должна быть симметричная
bool flag[MAXN];      //Использованные вершины
int stack[MAXN];
int n;

void Solve(int ver, int num)
{
   if (num == n && matrix[ver][stack[0]] == 1) {
      //Печать цикла. Например так...
      for (int i = 0; i < n; i++)
         cout << stack+1 << ' ';
      cout << endl;
   }

   for (int i = 0; i < n; i++)
      if (i != ver && !flag && matrix[ver])
      {
         stack[num] = i;
         flag = true;
         Solve(i, num + 1);
         flag = false;
      }
}

int main()
{
   //ввод матрицы
   EnterToMatrix();
//Строем цикл для первой вершины
   flag[0] = true;
   stack[0] = 1;
   Solve(1, 1);
}

[антонха]

Спасибо за код , буду разбираться