阅读下列说明和?C?代码,回答问题?1?至问题?2,将解答写在答题纸的对应栏内。
【说明】
一个无向连通图?G?点上的哈密尔顿(Hamiltion)回路是指从图?G?上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路劲。一种求解无向图上哈密尔顿回
路算法的基础私下如下:假设图?G?存在一个从顶点?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?表示已访问
⑵C?程序
【问题?1】(10?分)
根据题干说明。填充?C?代码中的空(1)~(5)。
【问题?2】(5?分)
根据题干说明和?C?代码,算法采用的设计策略为(),该方法在遍历图的顶点时,采用的
是(?)方法(深度优先或广度优先)。
【问题 1】(10 分)
【问题 2】(5 分)
回溯法、深度优先。