閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題2，將解答寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)

【說(shuō)明】

一個(gè)無(wú)向連通圖G上的哈密爾頓(Hamilton)回路是指從圖G上的某個(gè)頂點(diǎn)出發(fā)，經(jīng)過(guò)圖上所有其他頂點(diǎn)一次且僅一次，最后回到該頂點(diǎn)的路徑。一種求解無(wú)向圖上的哈密爾頓回路算法的基本思想如下：

假設(shè)圖G存在一個(gè)從頂點(diǎn)u0出發(fā)的哈密爾頓回路u0—u1—u2—u3—...—u0—un-1—u0。算法從頂點(diǎn)u0出發(fā)，訪(fǎng)問(wèn)該頂點(diǎn)的一個(gè)未被訪(fǎng)問(wèn)的領(lǐng)接頂點(diǎn)u1 ，接著從頂點(diǎn)u1出發(fā)，訪(fǎng)問(wèn)u1的一個(gè)未被訪(fǎng)問(wèn)的領(lǐng)接頂點(diǎn)u2，...。對(duì)頂點(diǎn)ui，重復(fù)進(jìn)行以下操作：訪(fǎng)問(wèn)ui的一個(gè)為被訪(fǎng)問(wèn)的領(lǐng)接頂點(diǎn)ui+1;若ui的所有領(lǐng)接頂點(diǎn)均已被訪(fǎng)問(wèn)，則返回到頂點(diǎn)ui-1，考慮ui-1的下一個(gè)未被訪(fǎng)問(wèn)的領(lǐng)接頂點(diǎn)，仍記為ui;直到找到一個(gè)哈密爾頓回路或者找不到哈密爾頓回路，算法結(jié)束。

【C代碼】

下面是算法的C語(yǔ)言實(shí)現(xiàn)。

(1)常量和變量說(shuō)明

n：圖G中的頂點(diǎn)數(shù)

c[][]：圖G的領(lǐng)接矩陣

k：統(tǒng)計(jì)變量，當(dāng)前已經(jīng)訪(fǎng)問(wèn)的頂點(diǎn)數(shù)為k+1

x[k]：第k個(gè)訪(fǎng)問(wèn)的頂點(diǎn)編號(hào)，從0開(kāi)始

visited[x[k]]:第k個(gè)頂點(diǎn)的訪(fǎng)問(wèn)標(biāo)志，0表示未訪(fǎng)問(wèn)，1表示已訪(fǎng)問(wèn)

(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數(shù)組和visited數(shù)組*/

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

Visited[i]=0;

}

/*訪(fǎng)問(wèn)起初頂點(diǎn)*/

K=0;

(1) ;

x[0]=0;

k=k+1;

/*訪(fǎng)問(wèn)其它頂點(diǎn)*/

while(k>0){

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

while(x[k] if( (2) &&c[x[k-1]][x[k]]==1){/*領(lǐng)接頂點(diǎn)x[k]未被訪(fǎng)問(wèn)過(guò)*/

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 {/*沒(méi)有未被訪(fǎng)問(wèn)過(guò)的領(lǐng)接頂點(diǎn)，回退到上一個(gè)頂點(diǎn)*/

x[k]=0;

visited[x[k]]=0;

(5) ;

}

}

}

【問(wèn)題1】(10分)

根據(jù)題干說(shuō)明，填充C代碼中的空(1)~(5)。

【問(wèn)題2】(5分)

根據(jù)題干說(shuō)明和C代碼，算法采用的設(shè)計(jì)策略是(6)，該方法在遍歷圖的頂點(diǎn)時(shí)，采用的是(7)方法(深度優(yōu)先或廣度優(yōu)先)。

信管網(wǎng)參考答案：

（1）visited[0]=1

（2）visited[x[k]]==0

（3）c[x[k]][0]==1

（4）visited[x[k]]=1

（5）k=k-1 或等價(jià)交換

（6）回溯法

（7）深度優(yōu)先

查看解析：m.xiexiliangjiufa.com/st/395684405.html