专业软件设计师网站|培训机构|服务商(加客服微信:cnitpm或QQ:800184589进软件设计师学霸群)

软题库 培训课程
当前位置:信管网 >> 软件设计师 >> 案例分析 >> 文章内容
一个无向连通图G上的哈密尔顿(Hamilton)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次
来源:信管网 2021年11月05日 【所有评论 分享到微信

阅读下列说明和C代码,回答问题1至问题2,将解答写在答题纸的对应栏内

【说明】

一个无向连通图G上的哈密尔顿(Hamilton)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。一种求解无向图上的哈密尔顿回路算法的基本思想如下:

假设图G存在一个从顶点u0出发的哈密尔顿回路u0—u1—u2—u3—...—u0—un-1—u0。算法从顶点u0出发,访问该顶点的一个未被访问的领接顶点u1 ,接着从顶点u1出发,访问u1的一个未被访问的领接顶点u2,...。对顶点ui,重复进行以下操作:访问ui的一个为被访问的领接顶点ui+1;若ui的所有领接顶点均已被访问,则返回到顶点ui-1,考虑ui-1的下一个未被访问的领接顶点,仍记为ui;直到找到一个哈密尔顿回路或者找不到哈密尔顿回路,算法结束。

【C代码】

下面是算法的C语言实现。

(1)常量和变量说明

n:图G中的顶点数

c[][]:图G的领接矩阵

k:统计变量,当前已经访问的顶点数为k+1

x[k]:第k个访问的顶点编号,从0开始

visited[x[k]]:第k个顶点的访问标志,0表示未访问,1表示已访问

(2)C程序

#include

#include

#define MAX 4Void Hamilton(int n,int x[MAX],int c[MAX][MAX]){

int i;

int visited[MAX];

int k;

/*初始化x数组和visited数组*/

for(i=o;i x[i]=0;

Visited[i]=0;

}

/*访问起初顶点*/

K=0;

(1) ;

x[0]=0;

k=k+1;

/*访问其它顶点*/

while(k>0){

x[k]=x[k]+1;

while(x[k] if( (2) &&c[x[k-1]][x[k]]==1){/*领接顶点x[k]未被访问过*/

break;

}

else{

x[k]=x[k]+1;

}

}

if(x[k]for(k=0;k printf(“%d--”,x[k]);/*输出哈密尔顿回路*/

}

printf(“%d\n”,x[0]);

return;

}

else if(x[k]&&k (4) ;

k=k+1;

}

else {/*没有未被访问过的领接顶点,回退到上一个顶点*/

x[k]=0;

visited[x[k]]=0;

(5) ;

}

}

}

【问题1】(10分)

根据题干说明,填充C代码中的空(1)~(5)。

【问题2】(5分)

根据题干说明和C代码,算法采用的设计策略是(6),该方法在遍历图的顶点时,采用的是(7)方法(深度优先或广度优先)。

信管网参考答案:

(1)visited[0]=1

(2)visited[x[k]]==0

(3)c[x[k]][0]==1

(4)visited[x[k]]=1

(5)k=k-1 或等价交换

(6)回溯法

(7)深度优先

查看解析:www.cnitpm.com/st/395684405.html

扫码关注公众号

温馨提示:因考试政策、内容不断变化与调整,信管网网站提供的以上信息仅供参考,如有异议,请以权威部门公布的内容为准!

信管网致力于为广大信管从业人员、爱好者、大学生提供专业、高质量的课程和服务,解决其考试证书、技能提升和就业的需求。

信管网软考课程由信管网依托10年专业软考教研倾力打造,官方教材参编作者和资深讲师坐镇,通过深研历年考试出题规律与考试大纲,深挖核心知识与高频考点,为学员考试保驾护航。面授、直播&录播,多种班型灵活学习,满足不同学员考证需求,降低课程学习难度,使学习效果事半功倍。

相关内容

发表评论  查看完整评论  

推荐文章