【正文】 (k)←n； for j←2 to k1 do //找路徑上的第j個節(jié)點// P(j)←D ( P(j1) ) repeat end FGRAPH多段圖問題includeincludeincludedefine MAX_VERTEX_NUM 50typedef struct ArcNode{ int adjvex。 //該結(jié)點與鄰接結(jié)點間的代價 struct ArcNode *nextarc。typedef struct VNode{ int data。 //指向第一條依附該頂點的弧的指針}VNode, AdjList[MAX_VERTEX_NUM]。 int vexnum,arum。int build_adList(ALGraph G,int n,int a){ //建立鄰接表 int v, m, i, t, h。 if(n 0) return printf(ERROR)。 //圖的頂點數(shù) if(a 0) return printf(ERROR)。 //圖的弧數(shù) for(m = 0。 m++) { Gvertices[m].data = m。 } for(m = 1。 m++) { i = 1。 scanf(%d,%d,%d,amp。h,amp。 p = (ArcNode*)malloc(sizeof(ArcNode))。 pvalue = v。 while(Gvertices[i].data != t) i++。 else { //若當(dāng)前結(jié)點有后繼節(jié)點則后移 for(q = Gvertices[i].firstArc。 q = qnextarc)。 //新開辟結(jié)點 } } return v。 int i。 i Gvexnum。 printf([%d],i)。//第i個結(jié)點的鄰接結(jié)點信息 p = pnextarc。 }}void fgraph(ALGraph G ,int k,int n){ //多段圖ALGraph G，n為結(jié)點數(shù)，k為圖的段數(shù) //輸入是按段的順序給結(jié)點編號 int cost[100]。 int path[100]。 node p。 for(j = n 1。 j) //向前處理結(jié)點 { p = Gvertices[j].firstArc。 //初始化路徑最小代價 r = padjvex。 while(p != NULL) { //r是一個的這樣的結(jié)點，權(quán)值c(j,r)+cost[r]取最小值 if((pvalue + cost[padjvex]) min) { min = pvalue + cost[padjvex]。 value = pvalue。 } cost[j] = value + cost[r]。 //決策階段，各結(jié)點到終點最小代價路徑上前方頂點的編號 } path[1] = 1。 for(i = 2。 i++) //找出最小代價路徑上的結(jié)點 path[i] = d[path[i 1]]。 printf(最小成本路徑為: )。 w = k。}void main(){ ALGraph g。 g = (ALGraph)malloc(sizeof(ALGraph))。 scanf(%d, amp。 printf(請輸入多段圖邊的數(shù)目:)。a)。 scanf(%d, amp。 printf(輸入多段圖的弧的信息（弧頭，弧尾，權(quán)值）\n)。 printf(多段圖的鄰接表為:\n)。 fgraph(g, k, n)。}多段圖問題實驗四 深度優(yōu)先搜索1． 理解深度優(yōu)先搜索策略：深度優(yōu)先搜索策略是盡可能“深”地搜索圖。當(dāng)所有的邊(v,w)都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點v的頂點。如果還存在未被發(fā)現(xiàn)的頂點，則選擇其中一個作為源結(jié)點并重復(fù)以上過程，整個進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點都被發(fā)現(xiàn)為止。每個頂點開始均為白色，搜索中被發(fā)現(xiàn)時置為灰色，當(dāng)其鄰接表被完全檢索之后又被置成黑色。2． 修改算法使之可以找出圖的所有樹。4． 修改算法使之可以判斷圖是否存在一個環(huán)。 for 每個頂點u∈G do color[u]← White。end。 color[u]←Gray。 repeat color[u]←Black。includedefine MAX 50 //能夠處理的最多頂點數(shù) char color[MAX]。 //頂點數(shù)和矩陣int loop=0。 //標(biāo)記樹并記錄其個數(shù)void DFS(int i){ int k。G39。k=n。G39。B39。 if(color[k]==39。) DFS(k)。B39。 cout請輸入總頂點數(shù)：\n。 cout請輸入總邊數(shù)：\n。 for(i=1。i++) { for(j=1。j++) { A[i][j]=0。W39。k=m。 cini。 cinj。 //有邊的賦值為1 } for(i=1。i++) { if(color[i]==39。) DFS(i)。i=n。jn。amp。 } if(loop==0) { cout該圖中無環(huán)!endl。 } else { cout該圖中共有l(wèi)oop個環(huán)!endl。 }}實驗五 回溯法1. 理解可用回溯法求解的問題問題P通常要能表達(dá)為對已知的、由n元組(x1，…，xn)組成的狀態(tài)空間E={(x1，…，xn)| xi206。 Si 是 xi 的定義域且Si 是有窮集，稱E中滿足D 的全部約束條件的所有n元組為問題P的一個解。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯?；厮莘ǖ男问矫枋觯簆rocedure BACAKTRACE(n) k =1 。2. 用圖形輸出中間過程。n皇后算法procedure NQUEENS(n)X(1)←0；k←1 //k是當(dāng)前行；X(k)是當(dāng)前列//While k0 do //對所有的行執(zhí)行以下語句//{ X(k)←X(k)+1 //移到下一列//While X(k)≤n and not PLACE(k) do X(k)←X(k)十l if X(k)≤n //找到一個位置// then if k=n //是一個完整的解嗎// then print(X) //是，打印這個數(shù)組// else {k←k+1；X(k)←0；} else k←k－1 //回溯//}end NQUEENSinclude include /*檢查可不可以放置一個新的皇后*/bool place(int k, int *X){ int i。 while(i k) { if((X[i] == X[k])||(abs(X[i] X[k]) == abs(i k))) //兩個皇后不在同行/列/對角線 return false。 } return true。 X[1] = 0。 while(k 0) { X[k] = X[k] + 1。amp。 //不滿足條件,繼續(xù)搜索下一列位置 if(X[k] = n) //存在滿足條件的列 { if(k == n) //是最后一個皇后,完成搜索 { for(int i = 1。i++) //輸出各行皇后的列位置 printf(%d , X[i])。 } else { k = k + 1。 //下一列的皇后所在列位置置0 } } else {//已判斷完n列，均未能滿足條件 X[k] = 0。 //回溯到前一列 } }}void main(){ int n, i。 printf(|THE N QUEENS PROBLEM|\n)。 printf(||\n\n)。 scanf(%d, amp。 X = new int[n]。 Nqueens(n, X)。 printf(Press 0 to exit\n)