【正文】 by－1do //計(jì)算COST(j)// 　設(shè)r是一個這樣的結(jié)點(diǎn)，(j，r)206。 //指向下一條弧的指針}ArcNode, *node。typedef struct Graph{ AdjList vertices。 node p, q。 Garum = a。 Gvertices[m].firstArc = NULL。 printf(輸入第%d條弧:, m)。v)。 pnextarc = NULL。 qnextarc。}void print_Graph(ALGraph G){ //打印鄰接表 ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode))。 i++) { p = Gvertices[i].firstArc。 } printf(\n)。 int j, r, i, min, w, value。 j = 1。 value = pvalue。 } p = pnextarc。 path[k] = n。 printf(最小成本為:%d\n,cost[1])。 w++) printf(%d, path[w])。 printf(請輸入多段圖節(jié)點(diǎn)數(shù)目:)。 scanf(%d, amp。k)。 print_Graph(g)。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的頂點(diǎn)v，如果邊(v,w)是還未探測的邊，則沿(v,w)繼續(xù)搜索下去。2． 理解深度優(yōu)先搜索過程中頂點(diǎn)的三種狀態(tài)：還未到達(dá)的頂點(diǎn)，當(dāng)前路徑上經(jīng)過的頂點(diǎn)，深度優(yōu)先在搜索過程中也為結(jié)點(diǎn)著色以表示結(jié)點(diǎn)的狀態(tài)。3． 修改算法使之可以判斷圖是否為一棵樹。 repeat for每個頂點(diǎn)u∈G do if color[u]=White then DFS_Visit(G,u)。 for (u,w)∈E do //探尋邊(u,w) if color[w]=White then DFS_Visit(w)。 //保存每個點(diǎn)的顏色標(biāo)記int n,A[MAX][MAX]。 color[i]=39。k++) { if(A[i][k]==1) { if(color[k]==39。) //當(dāng)該點(diǎn)的鄰接點(diǎn)中有已被訪問的點(diǎn)時存在環(huán) loop++。 //訪問鄰接點(diǎn)中一個沒有被訪問的點(diǎn) } } color[i]=39。 cinn。i=n。 //將矩陣初始化為0 color[i]=39。k++) { cout請輸入其始點(diǎn):。 A[i][j]=1。W39。i++) for(j=1。A[j][i])) tree++。 cout該圖不是一棵樹!endl。2. 理解回溯法的基本思想回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。3. 在程序中添加統(tǒng)計(jì)擴(kuò)展節(jié)點(diǎn)數(shù)，估計(jì)算法的復(fù)雜性。 i++。 k = 1。(!place(k, X))) //當(dāng)前列位置是否滿足條件 X[k] = X[k] + 1。 printf(\n)。 //當(dāng)前行復(fù)位為0 k = k 1。 printf(| edited by Jill Chih |\n)。n)。 printf(Press 1 to run again\n)。 }}33。 scanf(%d, amp。 printf(The solutions are:\n)。 while(i) { printf(Please input the sum of Queens:\n)。 int *X。 //不是最后一個,則處理下一個皇后 X[k] = 0。i = n。 //從當(dāng)前列加1的位置開始搜索 while((X[k] = n)amp。}void Nqueens(int n, int *X){//k表示所處理的是第k行的皇后，X[k]表示第k行皇后的列位置 int k。 i = 1。 while (k0) do if Tk (x1，x2，…， x k1)的值還未取遍 then {xk←Tk (x1，x2，…， x k1)中未取遍過的值；if Bk (x1，x2，…， x k) then{(x1，x2，…， x k)被激活；if k ==n then 輸出(x1，x2，…， x n)；else k =k+1； // 深度擴(kuò)展搜索 } } else k = k 1 // 試探完了所有的x k，回溯 end BACAKTRACE1. 編程實(shí)現(xiàn)n皇后算法。算法搜索至解空間樹的任一結(jié)點(diǎn)時，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。Si,i=1,2,…n}，給定關(guān)于n元組中的分量的一個約束集D，求滿足D的全部約束條件的所有n元組。 if(m==n1) cout該圖為一棵樹!endl。j++) { if(!(A[i][j]amp。 } for(i=1。i=n。 cout請輸入指向的點(diǎn):。 //所有頂點(diǎn)顏色初始化為白色 } } for(k=1。j=n。 cinm。 //當(dāng)點(diǎn)為死結(jié)點(diǎn)時記為黑色}void main(){ int i,j,k,m。W39。||color[k]==39。 //已訪問頂點(diǎn)記為灰色 for(k=1。 //標(biāo)記環(huán)并記錄其個數(shù)int tree=0。 //完成后置u為黑色end。 procedure DFS_Visit(u)。procedure DFS(G)。1． 編程實(shí)現(xiàn)深度優(yōu)先搜索算法。這一過程一直進(jìn)行到回到源點(diǎn)為止。 getch()。 build_adList(g, n, a)。 printf(請輸入多段圖的段數(shù):)。n)。 int n,a,k。 for(w = 1。 i = k 1。 //當(dāng)前節(jié)點(diǎn)的代價值 d[j] = r。 //pvalue=c(j,r) r = padjvex。 min = pvalue+cost[padjvex]。 cost[n] = 0。 int d[100]。 while(p) { printf(%d,%d,padjvex,pvalue)。 for(i = 1。 qnextarc = p。 //轉(zhuǎn)到下一個結(jié)點(diǎn) if(!Gvertices[i].firstArc) //終點(diǎn) Gvertices[i].firstArc = p。 padjvex = h。t,amp。 m = a。 m n。 Gvexnum = n。 //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}*ALGraph。 //頂點(diǎn)信息 ArcNode *firstArc。 //該弧所指向的頂點(diǎn)的位置 int value。E是邊集，c(i，j)是邊i,j的成本。2. 圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。3. 一般方法1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2） 遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3） 以自底向上的方式計(jì)算出最優(yōu)值；4） 根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。2. 理解分段決策Bellman方程。對于一個多階段過程問題，是否可以分段實(shí)現(xiàn)最優(yōu)決策，依賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。}1. 背包問題貪心算法2. Prim算法實(shí)驗(yàn)三 動態(tài)規(guī)劃1. 理解最優(yōu)子結(jié)構(gòu)的問題。 close[j1].lowcost != 0) { client = close[j1].lowcost。 while(close[j1].adjvex != 39。 } } }}int LocateVex(MGraph G, VerTexType u){ int k = 0。 for (j=0。 cout。 for (i = 1。 close[j].adjvex = 39。 j 。 }}void MiniSpanTree_PRIM(MGraph G,VerTexType u){ int i, j, k = 0。 [k][j].adj = weigh。 cinweigh。 i 。 coutinputarc(char,char,weigh):endl。 for(i=0。 j 。 cin。G){ int weigh。 } MiniSpanTree_PRIM(G, 39。 j 。 CreateGraph(G)。int LocateVex(MGraph G, VerTexType u)。}c