9、回溯法求解哈密尔顿回路

回溯法求解一般哈密顿尔回路

附录

#include #include using namespace std; #define N 20 bool c[N][N]; int x[N]; int n;

bool flag =0;

void output(int x[]) {//输出函数

for(int i=0;i

void hamilton(int k ) {//递归算法

if(k>n-1 && c[x[k-1]][0]==1) {

output(x); flag=1; } else

for(int i=k;i

{

swap(x[k],x[i]);

if ( c[x[k-1]][x[k]]==1) hamilton(k+1); swap(x[i],x[k]); } }

void hamilton(int n, int x[N], bool c[N][N]) {//非递归算法 int i, k;

bool*visited = new bool[n]; for(i =0; i

x[i] = 0;

visited[i] = false; }

visited[0]=1;

x[0]=0;//默认以第一个城市开始

k =1; //搜索解空间树（子集树形式）直接从第二层开始 while(k >=1) {

x[k]++;

while(x[k] < n)

if(visited[x[k]]==0 && c[x[k - 1]][x[k]]==1) break; else

x[k]++;

if(x[k]

for(k=0;k

14

回溯法求解一般哈密顿尔回路

{

cout<

cout<

else if (x[k]

visited[x[k]]=1; k++; } else {

x[k]=0; k--;

visited[x[k]]=0; } } }

void Creat_M() {//建立邻接矩阵

memset(c, 0, sizeof(c)); int i=0;

cout<<\请输入图的阶数:\ cin>>n;

cout<<\请输入\阶邻接矩阵：\ for(i=0;i

for(int j=0;j

cin>>c[i][j];

} } }

void menu() {

int order,i;

cout<<\ .................................................................\

cout<<\ ....................... 菜单 ...............................\ cout<<\ .................................................................\ cout<<\ .... 1 回溯法求图的所有哈密顿回路（递归） ....\

cout<<\ .... 2 回溯法求图的所有哈密顿回路（非递归） ....\

cout<<\ .... 0 退出程

序 ....\

cout<<\ .................................................................\

cout<<\ .................................................................\ cout<<\请输入您的操作:\ cin>>order; switch(order) {

case 1:

system(\

cout<<\创建邻接矩阵.............................\

15

回溯法求解一般哈密顿尔回路

Creat_M();

cout<<\回溯法求图的所有哈密顿回路（递归）..................\

for(i = 0; i < n; i++) {

x[i] = i; }

hamilton(1); if(!flag)

cout<<\无哈密顿回路!\ system(\ system(\ menu(); break; case 2:

system(\

cout<<\创建邻接矩阵.............................\ Creat_M();

cout<<\回溯法求图的所有哈密顿回路（非递归）...............\

hamilton(n, x, c); if(!flag)

cout<<\无哈密顿回路!\ system(\ system(\ menu(); break; case 0:

system(\

cout<<\谢谢使用.............................\ default:

cout<<\输入命令有误，请重新输入；\ system(\ system(\ menu(); } }

void main() {

cout<<\欢迎进入哈密顿回路系统....................\ cout<<\ system(\ system(\ menu(); }

16