【正文】 //完成后置u為黑色end。procedure DFS(G)。這一過程一直進行到回到源點為止。 build_adList(g, n, a)。n)。 for(w = 1。 //當前節(jié)點的代價值 d[j] = r。 min = pvalue+cost[padjvex]。 int d[100]。 for(i = 1。 //轉(zhuǎn)到下一個結(jié)點 if(!Gvertices[i].firstArc) //終點 Gvertices[i].firstArc = p。t,amp。 m n。 //圖的當前頂點數(shù)和弧數(shù)}*ALGraph。 //該弧所指向的頂點的位置 int value。2. 圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。2. 理解分段決策Bellman方程。}1. 背包問題貪心算法2. Prim算法實驗三 動態(tài)規(guī)劃1. 理解最優(yōu)子結(jié)構(gòu)的問題。 while(close[j1].adjvex != 39。 for (j=0。 for (i = 1。 j 。 [k][j].adj = weigh。 i 。 for(i=0。 cin。 } MiniSpanTree_PRIM(G, 39。 CreateGraph(G)。}closedge[MAX_VERTEX_NUM]。 InfoType *info。 bag(goods,M,n)。i++) { goods[i].flag=i。 cinn。 coutgoods[i].Xendl。 i=j1。in。 } goods[i+1]=goods[0]。 //物品編號}。 //求圖G的以r為根的MST，結(jié)果放在T=(U，TE)中procedure GREEDY(A，n) /*貪心法一般控制流程*/ //A(1：n)包含n個輸入// solutions←φ //將解向量solution初始化為空／ for i←1 to n do x←SELECT(A) if FEASIBLE(solution，x) then solutions←UNION(solution，x) endif repeat return(solution)end GREEDY4. 實現(xiàn)典型的貪心算法的編程與上機實驗，驗證算法的時間復(fù)雜性函數(shù)。那些使目標函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。 kuaisu px(a1,n)。}。 output()。amp。 quicksort(i+1,t)。 }。 (j,k,n,b)。 for(i=0。 k++。 } else { r2[k]=r[j]。 int i,j,k。jn。in。struct rec{ KeyType key。// int p,q。 endifend DanC3．實現(xiàn)典型的分治算法的編程與上機實驗，驗證算法的時間復(fù)雜性函數(shù)。 integer m,p,q。DanC(p,q) global n，A[1:n]。mq return Combine(DanC(p,m),DanC(m+1,q))。 , A[q]按不降次序排列， 并假定A[n+1]是一個確定的、且大于 A[1:n]中所有的數(shù)。typedef int ElemType。 } void output(sqlist r,int n) { for(int i=0。 for(j=i。 output(r,M)。 i++。 i++。 srand(time(0))。 cout數(shù)組排序過程演示:\n。 ElemType data。 quicksort(s,i1)。 while(ij) { while(ijamp。 } b[i]=p。 int n。i++) a1[i].key=rand()%80?？尚薪庖话銇碚f是不唯一的。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。 //w通過1與T建立聯(lián)系 dist[w] ←weight(1,w) //w到T的距離 repeatwhile status[t]≠ “tree node” do pick a fringe u with min dist[w] // 選取到T最近的節(jié)點 status[u]←“tree node” for each edge(u,w) do 修改w和T的關(guān)系 repeatrepeat2. Prim算法PrimMST(G，T，r){ //物品該放的數(shù)量 int flag。 i。 //背包剩余容量 for(i=1。j++) { goods[0]=goods[j]。i++) { cout第i件物品要放:。//定義一個指針 while(j) { cout請輸入物品的總數(shù)量：。i=n。 } Insertionsort(goods,n)。typedef struct ArcCell{ VRType adj。 VRType lowcost。 MGraph G。 } coutendl。 coutinput the number for vexnum and arum:。 coutinputchar for vexs:。 for(i=0。 [j][k].adj = weigh。 for ( j = 0。 close[k].adjvex = u。 close[k].lowcost = 0。}int minimum(closedge close){ int j1=0, client = 88, j2。 } return j2。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素。1. 編程實現(xiàn)多段圖的最短路徑問題的動態(tài)規(guī)劃算法。E且使c(j，r)+COST(r)取最小值 　COST(j)←c(j，r)+COST(r) D(j)←r repeat //向前對j1進行決策// P(1)←1；P(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。 int vexnum,arum。 //圖的弧數(shù) for(m = 0。 scanf(%d,%d,%d,amp。 while(Gvertices[i].data != t) i++。 int i。 }}void fgraph(ALGraph G ,int k,int n){ //多段圖ALGraph G，n為結(jié)點數(shù)，k為圖的段數(shù) //輸入是按段的順序給結(jié)點編號 int cost[100]。 j) //向前處理結(jié)點 { p = Gvertices[j].firstArc。 } cost[j] = value + cost[r]。 printf(最小成本路徑為: )。 scanf(%d, amp。 printf(輸入多段圖的弧的信息（弧頭，弧尾，權(quán)值）\n)。當所有的邊(v,w)都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點v的頂點。4． 修改算法使之可以判斷圖是否存在一個環(huán)。 repeat color[u]←Black。G39。 if(color[k]==39。 cout請輸入總邊數(shù)：\n。W39。 //有邊的賦值為1 } for(i=1。jn。 }}實驗五 回溯法1. 理解可用回溯法求解的問題問題P通常要能表達為對已知的、由n元組(x1，…，xn)組成的狀態(tài)空間E={(x1，…，xn)| xi206?；厮莘ǖ男问矫枋觯簆rocedure BACAKTRACE(n) k =1 。 } return true。 //不滿足條件,繼續(xù)搜索下一列位置 if(X[k] = n) //存在滿足條件的列 { if(k == n) //是最后一個皇后,完成搜索 { for(int i = 1。 //回溯到前一列 } }}void main(){ int n, i。 X = new int