【正文】 //完成后置u為黑色end。procedure DFS(G)。這一過程一直進(jìn)行到回到源點(diǎn)為止。 build_adList(g, n, a)。n)。 for(w = 1。 //當(dāng)前節(jié)點(diǎn)的代價(jià)值 d[j] = r。 min = pvalue+cost[padjvex]。 int d[100]。 for(i = 1。 //轉(zhuǎn)到下一個(gè)結(jié)點(diǎn) if(!Gvertices[i].firstArc) //終點(diǎn) Gvertices[i].firstArc = p。t,amp。 m n。 //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}*ALGraph。 //該弧所指向的頂點(diǎn)的位置 int value。2. 圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。2. 理解分段決策Bellman方程。}1. 背包問題貪心算法2. Prim算法實(shí)驗(yàn)三 動(dòng)態(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]。 //物品編號(hào)}。 //求圖G的以r為根的MST，結(jié)果放在T=(U，TE)中procedure GREEDY(A，n) /*貪心法一般控制流程*/ //A(1：n)包含n個(gè)輸入// 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. 實(shí)現(xiàn)典型的貪心算法的編程與上機(jī)實(shí)驗(yàn)，驗(yàn)證算法的時(shí)間復(fù)雜性函數(shù)。那些使目標(biāo)函數(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．實(shí)現(xiàn)典型的分治算法的編程與上機(jī)實(shí)驗(yàn)，驗(yàn)證算法的時(shí)間復(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]是一個(gè)確定的、且大于 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是不唯一的。如果當(dāng)前這個(gè)輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。 //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é)點(diǎn) 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件物品要放:。//定義一個(gè)指針 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ì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。1. 編程實(shí)現(xiàn)多段圖的最短路徑問題的動(dòng)態(tài)規(guī)劃算法。E且使c(j，r)+COST(r)取最小值 　COST(j)←c(j，r)+COST(r) D(j)←r repeat //向前對j1進(jìn)行決策// P(1)←1；P(k)←n； for j←2 to k1 do //找路徑上的第j個(gè)節(jié)點(diǎn)// 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é)點(diǎn)數(shù)，k為圖的段數(shù) //輸入是按段的順序給結(jié)點(diǎn)編號(hào) int cost[100]。 j) //向前處理結(jié)點(diǎn) { p = Gvertices[j].firstArc。 } cost[j] = value + cost[r]。 printf(最小成本路徑為: )。 scanf(%d, amp。 printf(輸入多段圖的弧的信息（弧頭，弧尾，權(quán)值）\n)。當(dāng)所有的邊(v,w)都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v的頂點(diǎn)。4． 修改算法使之可以判斷圖是否存在一個(gè)環(huán)。 repeat color[u]←Black。G39。 if(color[k]==39。 cout請輸入總邊數(shù)：\n。W39。 //有邊的賦值為1 } for(i=1。jn。 }}實(shí)驗(yàn)五 回溯法1. 理解可用回溯法求解的問題問題P通常要能表達(dá)為對已知的、由n元組(x1，…，xn)組成的狀態(tài)空間E={(x1，…，xn)| xi206?；厮莘ǖ男问矫枋觯簆rocedure BACAKTRACE(n) k =1 。 } return true。 //不滿足條件,繼續(xù)搜索下一列位置 if(X[k] = n) //存在滿足條件的列 { if(k == n) //是最后一個(gè)皇后,完成搜索 { for(int i = 1。 //回溯到前一列 } }}void main(){ int n, i。 X = new int