在未加权图中查找哈密顿圈的 C++ 程序

• Z时代
• 2024-01-10
• 分类：综合

哈密顿回路是一条哈密顿路径，使得从哈密顿路径的最后一个顶点到第一个顶点有一条边（在图中）。在无向图中，有一条路径只访问图的每个顶点一次。

功能和目的

Begin
   1. function isSafe() is used to check for whether it is
   adjacent to the previously added vertex and already not added.
   2. function hamiltonianCycle() solves the hamiltonian problem.
   3. function hamCycle() uses hamiltonianCycle() to solve
   the hamiltonian problem. It returns false if there is no
   Hamiltonian Cycle possible, otherwise return true and prints the path.
End

示例

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 5
using namespace std;
void displaytheSolution(int path[]);
bool isSafe(int n, bool g[N][N], int path[], int pos) {
   if (g [path[pos-1]][n] == 0)
      return false;
   for (int i = 0; i < pos; i++)
      if (path[i] == n)
         return false;
   return true;
}
bool hamiltonianCycle(bool g[N][N], int path[], int pos) {
   //如果所有顶点都包含在哈密顿循环中
   if (pos == N) {
      if (g[ path[pos-1] ][ path[0] ] == 1)
         return true;
      else
         return false;
   }
   for (int n = 1; n < N; n++) {
      if (isSafe(n, g, path, pos)) { //检查这个顶点是否可以添加到哈密顿循环
         path[pos] = n;
         //recur 以构建路径的其余部分
         if (hamiltonianCycle (g, path, pos+1) == true)
            return true;
         path[pos] = -1; //如果它不会导致解决方案，则删除顶点
      }
   }
   return false;
}
bool hamCycle(bool g[N][N]) {
   int *path = new int[N];
   for (int i = 0; i < N; i++)
   path[i] = -1;
   //将顶点 0 作为路径中的第一个顶点。如果存在哈密顿循环，则路径可以从任意点开始
   //由于图是无向图的循环
   path[0] = 0;
   if (hamiltonianCycle(g, path, 1) == false) {
      cout<<"\nCycle does not exist"<<endl;
      return false;
   }
   displaytheSolution(path);
   return true;
}
void displaytheSolution(int p[]) {
   cout<<"循环存在：";
   cout<<" Following is one Hamiltonian Cycle \n"<<endl;
   for (int i = 0; i < N; i++)
   cout<<p[i]<<" ";
   cout<< p[0]<<endl;
}
int main() {
   bool g[N][N] = {{0, 1, 0, 1, 1},
      {0, 0, 1, 1, 0},
      {0, 1, 0, 1, 1},
      {1, 1, 1, 0, 1},
      {0, 1, 1, 0, 0},
   };
   hamCycle(g);
   return 0;
}

循环存在： Following is one Hamiltonian Cycle
0 4 1 2 3 0

以上是 在未加权图中查找哈密顿圈的 C++ 程序 的全部内容， 来源链接： utcz.com/z/311389.html