C ++程序检查给定图是否必须包含哈密顿循环
哈密顿循环是哈密顿路径，因此从哈密顿路径的最后一个顶点到第一个顶点有一条边（在图中）。它在无向图中是一条路径，该路径恰好一次访问图的每个顶点。
功能和目的
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)) //Check if this vertex can be added to Hamiltonian Cycle
{
path[pos] = n;
//重复构建其余路径
if (hamiltonianCycle (g, path, pos+1) == true)
return true;
path[pos] = -1; //remove vertex if it doesn’t lead to the solution
}
}
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
热门推荐
7 修祖屋祝福语简短
10 超市中秋祝福语简短最新
11 送给老师中秋祝福语简短
12 祝妹妹毕业祝福语简短
13 简短朋友旅行祝福语大全
14 婆婆生日祝福语短语简短
15 医政科祝福语简短
16 关于好的祝福语简短
17 三八简短祝福语给婆婆
18 给长辈祝福语简短大全