【正文】 //構(gòu)造最短路徑 } }//for }//for }//ALGraph_DIJ 分析 :本算法對迪杰斯特拉算法中直接取任意邊長度的語句作了修改 .由于在原算法中 ,每次循環(huán)都是對尾相同的邊進(jìn)行處理 ,所以可以用遍歷鄰接表中的一條鏈來代替 . 。 P[w]=P[v]。amp。p=pnextarc) { w=padjvex。 for(p=[v].firstarc。 min=D[w]。w。i++) { min=INFINITY。 //初始化 for(i=1。 } }//for D[v0]=0。 //設(shè)空路徑 if(D[v]INFINITY) { P[v][v0]=1。w。v++) { final[v]=0。 //給 D數(shù)組賦初值 for(v=0。p。v++) D[v]=INFINITY。D)//在鄰接表存儲結(jié)構(gòu)上實現(xiàn)迪杰斯特拉算法 { for(v=0。 } }//else }//DFS2 void ALGraph_DIJ(ALGraph G,int v0,Pathmatrix amp。 dut=*pinfo。p。 } }//DFS1 void DFS2(ALGraph G,int i) { if(![i].firstarc) vl[i]=ve[i]。 if(ve[i]+dutve[padjvex]) ve[padjvex]=ve[i]+dut。p。 //打印輸出關(guān)鍵路徑 }//Critical_Path void DFS1(ALGraph G,int i) { if(!indegree[i]) ve[i]=0。i=。i++) if(!indegree[i]) DFS2(G,i)。 //第一次深度優(yōu)先遍歷 :建立 ve for(i=0。i。 void Critical_Path(ALGraph G)//利用深度優(yōu)先遍歷求網(wǎng)的關(guān)鍵路徑 { FindIndegree(G,indegree)。 ArcNode * firstarc。 char optr。 } }//Evaluate_imp 分析 :本題中 ,鄰接表的 vertices 向量的元素類型修改如下 : struct { enum tag{NUM,OPTR}。 v2=Evaluate_imp(G,pnextarcadjvex)。 else { p=[i].firstarc。 //找到有向無環(huán)圖的根 return Evaluate_imp(G,i)。i。 }//PrintNiBoLan_Bitree int Evaluate_DAG(ALGraph G)//給有向無環(huán)圖表示的表達(dá)式求 值 { FindIndegree(G,indegree)。 if(Trchild) PrintNiBoLan_Bitree(Trchild)。 printf(%c,c)。 PrintNiBoLan_DAG(G,padjvex)。 if(![i].firstarc) //c 是原子 printf(%c,c)。 //找到有向無環(huán)圖的根 PrintNiBoLan_DAG(G,i)。i。 }//DFS void NiBoLan_DAG(ALGraph G)//輸出有向無環(huán)圖形式表示的表達(dá)式的逆波蘭式 { FindIndegree(G,indegree)。 } }//else path[i]=0。p=pnextarc) { j=padjvex。 } else { for(p=[i].firstarc。j++) mlp[j]=path[j]。![i].firstarc) //新的最長路徑 { for(j=0。 if(lenmaxlenamp。 //輸出最長路徑 }//Get_Longest_Path void DFS(ALGraph G,int i,int len) { visited[i]=1。mlp[i]。//從每一個零入度結(jié)點(diǎn)開始深度優(yōu)先遍歷 } printf(Longest Path:)。j++) visited[j]=0。i++) { for(j=0。 for(i=0。 //數(shù)組 mlp用于存儲已發(fā)現(xiàn)的最長路徑 void Get_Longest_Path(ALGraph G)//求一個有向無環(huán)圖中最長的路徑 { maxlen=0。 }//else }//Get_MPL int maxlen,path[MAXSIZE]。 //求其直接后繼頂點(diǎn) MPL的最大者 } [i]=max+1。 if([j].MPL==0) k=Get_MPL(G,j)。p。 //零出度頂點(diǎn) } else { max=0。G,int i)//從一個頂點(diǎn)出發(fā)構(gòu)建 MPL域并返回其 MPL值 { if(![i].firstarc) { [i].MPL=0。i++) if(!indegree[i]) Get_MPL(G,i)。 for(i=0。 } }//DFS void Fill_MPL(ALGraph amp。p=pnextarc) { w=padjvex。 for(p=[v].firstarc。 //如果 v是根 ,則深度優(yōu)先遍歷可以訪問到所有結(jié)點(diǎn) if(flag) printf(Found a root vertex:%d\n,v)。w。//每次都要將訪問數(shù)組清零 DFS(G,v)。w。v。 }//TopoSeq int visited[MAXSIZE]。 } }//while if(count) return ERROR。p=pnextarc) { k=padjvex。 //把拓?fù)漤樞虼嫒霐?shù)組的對應(yīng)分量中 for(p=[i].firstarc。 while(!stackempty(S)) { Pop(S,i)。i++) if(!indegree[i]) Push(S,i)。 for(i=0。 //本算法就是拓?fù)渑判? FindIndegree(G,indegree)。 rnextsib=q。rnextsib。 if(!pfirstchild) //雙親還沒有孩子 pfirstchild=q。 //找到結(jié)點(diǎn) i 對應(yīng)的指針 p,過程略 q=(CSTNode*)malloc(sizeof(CSTNode))。 //從邊集中刪除 }//while }//MinSpanTree_Kruscal void Addto_CSTree(CSTree amp。 //合并連通分量 eum。 //選出最短邊 if(!is_ec(vexs,u,v)) //u和 v屬于不同連通分量 { Addto_CSTree(T,u,v)。 eum=。EdgeSet,CSTree amp。i++) if(vexs[i].eo==ec2) vexs[i].eo==ec1。vexs[ ],int ec1,int ec2)//合并連通分量 ec1和 ec2 { for(i=0。 else return 0。i++) vexs[i]={i,i}。vexs[ ],int vexnum)//初始化 { for(i=0。 VexInfo vexs[MAXSIZE]。 //結(jié)點(diǎn)序號 int eo。 Forest_Prim(G,1,T)。 //作為雙親最后一個孩子的兄弟 } }//Addto_Forest main() { ... T=(CSTNode*)malloc(sizeof(CSTNode))。r=rnextsib)。 //作為雙親的第一個孩子 else //雙親已經(jīng)有了孩子 { for(r=pfirstchild。 pfirstchild=q。r=rnextsib)。 for(r=T。 if(!p) //起始頂點(diǎn)不屬于森林中已有的任何一棵樹 { p=(CSTNode*)malloc(sizeof(CSTNode))。 //找到結(jié)點(diǎn) i 對應(yīng)的指針 p,過程略 q=(CSTNode*)malloc(sizeof(CSTNode))。 //對另外一個連通分量執(zhí)行算法 }//for }//Forest_Prim void Addto_Forest(CSTree amp。p=pnextarc) if(pcostclosedge[padjvex].lowcost) closedge[padjvex]={k,pcost}。 for(p=[k].firstarc。 if(closedge[k].lowcostMax_int) { Addto_Fores