哈密尔顿图遍历
发布网友
发布时间：2022-04-23 02:16
共1个回答
热心网友
时间：2023-10-11 09:39
解释比较麻烦，我这有个参考程序你看下，肯定对你有帮助的
/*校园导游程序:
用无向网表示学校的校园景点平面图.
图中顶点表示主要景点,存放景点的编号,名称,简介等信息.
图中的边表示景点间的道路,存放路径长度等信息.
要求:(1)查询各景点的相关信息.
(2)查询图中任意两个景点间的最短路径.
(3)查询图中任意两个景点间的所有路径.*/
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#define MAXV 20/*最多顶点个数*/
#define MAXSIZE 20/*字符串成员name的最大长度*/
#define MAXLEN 500/*字符串成员content的最大长度*/
#define INF 32767/*用32767表示∞*/
int a=0;/*全局变量，用来记录每对顶点之间的所有路径的条数*/
typedef struct
{int num;/*顶点编号*/
char name[MAXSIZE];/*顶点名称*/
char content[MAXLEN];/*顶点信息*/
}VertexType;/*顶点的结构定义*/
typedef struct
{int edges[MAXV][MAXV];/*网的邻接矩阵存储*/
int vexnum,arcnum;/*网中的顶点数和边数*/
VertexType vexs[MAXV];/*顶点向量*/
}MGraph;/*网的结构定义*/
int visited[MAXV];/*全局数组，用来记录各顶点被访问的情况*/
int p[MAXV];/*全局数组，用来存放路径上的各顶点*/
void path(MGraph g,int i,int j,int k)
/*确定路径上第k+1个顶点的序号*/
{int s;
if(p[k]==j)/*找到一条路径*/
{
a++;/*路径的条数值加1*/
printf("第%d条:",a);
for(s=0;s<=k-1;s++)/*输出一条路径*/
cout<<g.vexs[p[s]].name<<"->";
cout<<g.vexs[p[s]].name;
cout<<endl;
}
s=0;
while(s<g.vexnum)
{if(s!=i)/*保证找到的是简单路径*/
{if(g.edges[p[k]][s]!=INF&&visited[s]==0)
/*当vk与vs之间有边存在且vs未被访问过*/
{visited[s]=1;/*置访问标志位为1,即已访问的*/
p[k+1]=s;/*将顶点s加入到p数组中*/
path(g,i,j,k+1);/*递归调用之*/
visited[s]=0;/*重置访问标志位为0，即未访问的，以便该顶点能被重新使用*/
}}
s++;
}
}
void disppath(MGraph g,int i,int j)
{int k;
p[0]=i;
for(k=0;k<g.vexnum;k++)
visited[i]=0;/*初始化各顶点的访问标志位，即都为未访问过的*/
a=0;/*初始化路径的条数*/
path(g,i,j,0);/*通过调用path函数，找到从vi到vj的所有路径并输出*/
}
void ppath(MGraph g,int path1[],int i,int v0)
/*输出最短路径*/
{int k;
k=path1[i];
if(k==v0)/*找到最短路径，则返回*/
return;
ppath(g,path1,k,v0);/*否则，递归调用之*/
printf("%s->",g.vexs[k].name);/*依次输出路径中的景点名称*/
}
void dispath(MGraph g,int dist[],int path1[],int s[],int n,int v0,int i)
/*由path1计算从v0到i的最短路径*/
{
if(s[i]==1&&i!=v0)
/*当v0不等于i，且i∈s*/
{printf("从%s到%s的最短游览路径是:\n",g.vexs[v0].name,g.vexs[i].name);
printf("%s->",g.vexs[v0].name);
ppath(g,path1,i,v0);/*调用ppath函数，输出路径中的顶点*/
printf("%s ",g.vexs[i].name);
printf("路径长度：%d米\n",dist[i]);
}
}
void Dijkstra(MGraph g,int v0,int p)
/*采用狄克斯特拉算法求从顶点v0到顶点p的最短路径*/
{
/*s为已找到最短路径的终点集合,若s[i]=1,则i∈s;
path1[i]中存放顶点i的当前最短路径上该点的前趋顶点;
dist[i]中存放顶点i的当前最短路径长度*/
int dist[MAXV],path1[MAXV];
int s[MAXV];
int mindis,i,j,u,n=g.vexnum;
for(i=0;i<n;i++)
{dist[i]=g.edges[v0][i];/*距离初始化*/
s[i]=0;/*s[]置空*/
if(g.edges[v0][i]<INF)/*路径初始化*/
path1[i]=v0;
else
path1[i]=-1;
}
s[v0]=1;path1[v0]=0;/*源点编号v0放入s中*/
for(i=0;i<n;i++)
{mindis=INF;
u=-1;
for(j=0;j<n;j++)/*选取不在s中具有最小距离的顶点u*/
if(s[j]==0&&dist[j]<mindis)
{u=j;
mindis=dist[j];
}
s[u]=1;/*顶点u加入s中*/
for(j=0;j<n;j++)/*修改不在s中的顶点的距离*/
if(s[j]==0)
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])
/*修正dist[i],path1[i]*/
{dist[j]=dist[u]+g.edges[u][j];
path1[j]=u;
}
}
dispath(g,dist,path1,s,n,v0,p);/*输出最短路径*/
}
void Searchname(MGraph g)/*查询景点的信息*/
{printf("景点：\n1:体育馆\n2:生科楼\n3:主教楼\n4:校门\n5:广场\n6:二教楼\n7:一教楼\n8:网络中心\n9:实验楼\n10:艺术楼\n11:图书馆\n");
int i;
char s;
while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/
{printf("选择：");
cin>>i;
for(int j=0;j<g.vexnum;j++)/*g.vexnum表示网中的顶点个数*/
if(i==g.vexs[j].num)/*在网中找到其编号与输入的顶点编号相同的顶点*/
{printf("%s简介：\n",g.vexs[j].name);/*输出顶点的名称*/
printf("%s",g.vexs[j].content);/*输出顶点的简介信息*/
printf("\n");}
printf("继续查询?(y|n):");
cin>>s;
if(s=='N'||s=='n')
break;
}
}
void Searchpath1(MGraph g)/*查询两个景点间的所有路径*/
{printf("景点：\n1:体育馆\n2:生科楼\n3:主教楼\n4:校门\n5:广场\n6:二教楼\n7:一教楼\n8:网络中心\n9:实验楼\n10:艺术楼\n11:图书馆\n");
int i,j;
char s;
while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/
{printf("选择出发景点：");
cin>>i;
printf("选择目地景点：");
cin>>j;
for(int k=0;k<g.vexnum;k++)/*g.vexnum表示网中的顶点个数*/
if(i==g.vexs[k].num) i=k;/*在网中找到其编号与输入的出发景点的编号相同的顶点*/
for(int l=0;l<g.vexnum;l++)
if(j==g.vexs[l].num) j=l;/*在网中找到其编号与输入的目地景点的编号相同的顶点*/
printf("从%s到%s的所有游览路径有:\n",g.vexs[i].name,g.vexs[j].name);/*输出出发景点和目地景点的名称*/
disppath(g,i,j);/*调用disppath函数,用来输出两个景点间的所有路径*/
printf("继续查询?(y|n):");
cin>>s;
if(s=='N'||s=='n')
break;
}
}
void Searchpath2(MGraph g)/*查询两个景点间的最短路径*/
{printf("景点：\n1:体育馆\n2:生科楼\n3:主教楼\n4:校门\n5:广场\n6:二教楼\n7:一教楼\n8:网络中心\n9:实验楼\n10:艺术楼\n11:图书馆\n");
int i,j;
char s;
while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/
{printf("选择出发景点：");
cin>>i;
printf("选择目地景点：");
cin>>j;
for(int k=0;k<g.vexnum;k++)/*g.vexnum表示网中的顶点个数*/
if(i==g.vexs[k].num) i=k;/*在网中找到其编号与输入的出发景点的编号相同的顶点*/
for(int l=0;l<g.vexnum;l++)
if(j==g.vexs[l].num) j=l;/*在网中找到其编号与输入的目地景点的编号相同的顶点*/
Dijkstra(g,i,j);/*调用Dijkstra函数,用来输出两个景点间的最短路径*/
printf("继续查询?(y|n):");
cin>>s;
if(s=='N'||s=='n')
break;
}
}
void main()//*主函数*/
{int i,j;
int b[11]={1,2,3,4,5,6,7,8,9,10,11};/*整型数组,用来给每个顶点的编号进行赋值*/
char *c[11]={"体育馆","生科楼","主教楼","校门","广场","二教楼","一教楼","网络中心","实验楼","艺术楼","图书馆"};/*字符串指针数组,用来给每个顶点的名称进行赋值*/
char *d[11]={
/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/
"体育馆建筑面积23993M2，座席数：固定坐席4068个、观众临时坐席3956个。",
"生科楼配有多个实验室，如化学实验室，物理实验室，生物实验室。",
"主教楼有13层,配有6个电梯,总建设面积12167平方米，可同时容纳2000人上课。",
"校门整体设计中的浮雕设计由四幅组成，浮雕主题思想明确、富有时代气息。",
"中心广场设计的简约实用，运用较为丰富的景观元素营造舒适休闲环境。",
"这座新教学楼为公共教学楼，约有100个教室，供10000学生上课。",
"整个教学楼结构合理，设施先进。每个学生教室都配备了多媒体计算机、高亮度多媒体投影机，极大地方便了教师在课堂上利用现代教育技术。",
"网络中心目前拥有较先进的计算机设备，设备使用的完好率一直保持在95%以上,能充分满足教学实验的要求。",
"实验楼建成与2002年，建筑面积25000平方米，为物理院、化工院、生命科学院、信息科学与工程学院、经济学院、管理学院等学院学生提供实验设备与场所。",
"艺术楼的建筑精美别致、结构合理、功能齐备，内部配备了反映国内最先进的现代教育技术设备、实验设备、音乐美术器材等。",
"图书馆藏书丰富、建筑宏伟、环境幽雅。馆内服务功能完备，拥有多种现代化的服务手段。"};
MGraph g;/*定义一个MGraph类型的变量g,用来创建一个无向网*/
/*建立一个无向网，并用无向网表示校园景点的平面图*/
int A[11][11]={
/*用INF表示对应顶点间没有直达的道路，用其它整型变量表示对应顶点间有直达的道路，且路径的长度就是该整型变量的值*/
{INF,30,INF,INF,INF,INF,INF,INF,INF,INF,35},
{30,INF,5,INF,INF,15,INF,INF,12,INF,INF},
{INF,5,INF,15,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,15,INF,10,INF,INF,INF,INF,INF,INF},
{INF,INF,INF,10,INF,10,8,INF,INF,INF,INF},
{INF,15,INF,INF,10,INF,INF,20,INF,INF,INF},
{INF,INF,INF,INF,8,INF,INF,18,INF,INF,INF},
{INF,INF,INF,INF,INF,20,18,INF,10,15,INF},
{INF,12,INF,INF,INF,INF,INF,10,INF,INF,INF},
{INF,INF,INF,INF,INF,INF,INF,15,INF,INF,20},
{35,INF,INF,INF,INF,INF,INF,INF,INF,20,INF}};
g.vexnum=11;/*网中顶点的个数为11，即校园景点的个数为11*/
g.arcnum=14;/*网中边的个数为14，即校园景点间的道路为14条*/
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
g.edges[i][j]=A[i][j];/*建立无向网的邻接矩阵*/
for(i=0;i<g.vexnum;i++)
{g.vexs[i].num=b[i];/*给每个顶点一个编号*/
strcpy(g.vexs[i].name,c[i]);/*通过字符串复制函数给每个顶点一个名称*/
strcpy(g.vexs[i].content,d[i]);/*通过字符串复制函数给每个顶点加上信息，即作为景点的简介信息*/
}
int select;/*定义一个整型变量,用来输入不同的选择*/
cout<<"------------------------------校园导游程序--------------------------------------"<<endl;
cout<<"本程序能够："<<endl;
do/*可提供循环输入选择,当输入的选择为4时,退出循环*/
{printf("1:查询景点的信息2:查询景点间的游览路径3:查询景点间的最短游览路径4:退出 ");
cout<<"选择:";
cin>>select;
switch(select)
/*判断select的值，根据其值跳转到相应的子模块继续执行*/
{case 1:
Searchname(g);/*查询景点的信息*/
break;
case 2:
Searchpath1(g);/*查询景点间的游览路径*/
break;
case 3:
Searchpath2(g);/*查询景点间的最短游览路径*/
break;
case 4:/*退出程序*/
break;}
}while(select!=4);/*当select的值不为4时，继续循环*/
}
