答案及解析：[问答题]一个无向连通图G点上的哈密尔顿（Hamilton）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。一种求解无向图上哈密尔顿回路算法的基本思想如下：假设图G存在一

问题：

[问答题] 一个无向连通图G点上的哈密尔顿（Hamilton）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。一种求解无向图上哈密尔顿回路算法的基本思想如下：假设图G存在一个从顶点V0出发的哈密尔顿回路V0——V1——V2——V3——...——Vn-1——V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，…；对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；直到找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。【C代码】下面是算法的C语言实现。（1）常量和变量说明n:图G中的顶点数c[][]:图G的邻接矩阵k:统计变量，当期已经访问的定点数为k+1x［k］:第k个访问的顶点编号，从0开始visited［x［k］］：第k个顶点的访问标志，0表示未访问，1表示已访问（2）C程序#include＜stido.h>#include＜stidb.h>#define MAX 100void Hamilton（int n,int x［MAX],int c[MAX][MAX]）｛int i;int visited[MAX];int k;/*初始化x数组和visited数组*/for（i=0:i＜n;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]＜n）｛if（（2）&&c[x[k-1]][x[k]]==1）｛/*邻接顶点x[k]未被访问过*/break；｝else｛x[k]=x[k]+1｝｝if（x[k]＜n&&k==n-1&&（3）)｛/*找到一条哈密尔顿回路*/for（k=0;k＜n;k++）｛printf（〝%d--〝,x[k]);/*输出哈密尔顿回路*/｝printf（〝%d\n〝,x[0]);return；｝else if(x[k]＜n&&k＜n-1）｛/*设置当前顶点的访问标志，继续下一个顶点*/（4）k=k+1;｝else｛/*没有未被访问过的邻接顶点，回退到上一个顶点*/x[k]=0；visited[x[k]]=0；（5）；｝｝｝【问题1】（10分）根据题干说明。填充C代码中的空（1）~（5）。【问题2】（5分）根据题干说明和C代码，算法采用的设计策略为（6），该方法在遍历图的顶点时，采用的是（7）方法（深度优先或广度优先）。

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题