一个无向连通图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+1
x［k］:第k个访问的顶点编号，从0开始
visited［x［k］］：第k个顶点的访问标志，0表示未访问，1表示已访问
（2）C程序
#include＜stido.h>
#include＜stidb.h>
#define MAX 100
void 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）方法（深度优先或广度优先）。
正确答案及解析
正确答案
解析
【问题1】
1、visited[0]=1
2、visited[x[k]]==0
3、c[x[k]][0]==1
4、visited[x[k]]=1
5、k=k-1
【问题2】
6、回溯法
7、深度优先
哈密顿图是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径。
回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法题历来都被认为是比较难的题，一个程序开发人员都不喜欢看别人的代码。但是要得分也不是太难。
问题2比较容易得分，而且第二空就是个二选一的填空。只要了解到回溯法的相关原理，基本可以得满分。对于问题1就需要花一些心思，去读懂题干和代码，但是这里的第1空和第5空也是比较容易发挖出来的空。第一空是初始化第一个结点，第五空是此路不通，得回走，所以得退回。
包含此试题的试卷
你可能感兴趣的试题
Advancements in （ ）have contributed to the growth of the automotive industry through the creation and evolution of self-driving vehicles.
-
- A.Artificial Intelligence
- B.Cloud Computing
- C.Internet of Things
- D.Big Data
- 查看答案
In project human resource management , （ ）is not a source of power for the project manager.
-
- A.referent power
- B.expert power
- C.reward power
- D.audit power
- 查看答案
At the project establishment stage , the feasibility study mainly includes techinical feasibility analysis , （ ）, operation environment feasibility analysis and other aspects of feasibility analysis.
-
- A.detail feasibility analysis
- B.opportunity analysis
- C.economic feasibility analysis
- D.risk analysis
- 查看答案
（ ）is a grid that shows the project resources assigned to each work package.
-
- A.Stakeholder engagement assessment matrix
- B.Requirements traceability matrix
- C.Probability and impact matrix
- D.Responsibility assignment matrix
- 查看答案
Xinhua News Agency reported in January 2022，Chian will further promote the developmet of a digital economy during the 14th Five-Year Plan eriod（2021-2025）. The plan also emphasized industrial （ ）transformation.
-
- A.digital
- B.networking
- C.intelligentize
- D.informatization
- 查看答案