|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include <iostream>
using namespace std;
void Hamiton(int x[],int n,int **arc)//x[k]表示顶点
{
int i,k;
int visited[10];//visited[]标记数组
for (i=0;i<n;i++)
{
x[i]=0;
visited[i]=0;
}
x[0]=0;visited[0]=1;//开始从顶点0出发
k=1;
while(k>=1)
{
x[k]=x[k]+1;//搜索下一顶点
while(x[k]<n)
{
if(visited[x[k]]==0 &&arc[x[k-1]][x[k]]==1)
break;//未经过x[k]这个城市,且城市x[k-1]到城市x[k]有路径
else
x[k]=x[k]+1;
}
if(x[k]<n && k==n-1 && arc[x[k]][0]==1)
{//数组x[n]已经形成哈密顿回路,输出数组
cout<<"路径为:";
for(k=0;k<n;k++)
cout<<x[k]+1<<" ";//输出顶点编号,从一开始
return;
}
/*else
{
cout<<"哈密顿回路不存在!"<<endl;
return;
}*/
if(x[k]<n && k<n-1)//数组构成哈密顿回路的部分解
{
visited[x[k]]=1;
k=k+1;
}
else //回溯
{
visited[x[k]]=0;
x[k]=0;
k=k-1;
}
}
}
int main()
{
int n;
cout<<"请输入城市数 ";
cin>>n;
int *x=new int[n];//定义数组x[n]存储哈密图回路上的顶点
cout<<"输入代价矩阵:"<<endl;
//建立图的代价矩阵
int **arc=new int*[n];
for(int i=0;i<n;i++)
arc[i]=new int[n];
//赋值
for(i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>arc[i][j];
}
Hamiton(x,n,arc);
return 0;
} |
|