【正文】 1。p。 if(!visited[w]) DFS1(G,w)。 //在第一次遍歷中建立 finished數(shù)組 }//DFS1 void DFS2(OLGraph G,int v)//第二次逆向的深度優(yōu)先遍歷的算法 { visited[v]=1。 //在第二次遍歷中輸出結(jié)點(diǎn)序號(hào) for(p=[v].firstin。p=phlink) { w=ptailvex。 }//for }//DFS2 分析 :求有向圖的強(qiáng)連通分量的算法的時(shí)間復(fù)雜度和深度優(yōu)先遍歷相同 ,也為O(n+e). void Forest_Prim(ALGraph G,int k,CSTree amp。j。 for(p=[j].firstarc。p=pnextarc) if(padjvex==k) closedge[j].lowcost=pcost。 for(i=1。i++) { k=minimum(closedge)。 //把這條邊加入生成森林中 closedge[k].lowcost=0。p。 }//if else Forest_Prim(G,k)。T,int i,int j)//把邊 (i,j)添加到孩子兄弟鏈表表示的樹(shù) T中 { p=Locate(T,i)。 qdata=j。 pdata=i。rnextsib。 rnextsib=p。 } //作為新樹(shù)插入到最右側(cè) else if(!pfirstchild) //雙親還沒(méi)有孩子 pfirstchild=q。rnextsib。 rnextsib=q。 //建立樹(shù)根 Tdata=1。 ... }//main 分析 :這個(gè)算法是在 Prim算法的基礎(chǔ)上添加了非連通圖支持和孩子兄弟鏈表構(gòu)建模塊而得到的 ,其時(shí)間復(fù)雜度為 O(n^2). typedef struct { int vex。 //結(jié)點(diǎn)所屬的連通分量號(hào) } VexInfo。 //記錄結(jié)點(diǎn)所屬連通分量號(hào)的數(shù)組 void Init_VexInfo(VexInfo amp。ivexnum。 //初始狀態(tài) :每一個(gè)結(jié)點(diǎn)都屬于不同的連通分量 }//Init_VexInfo int is_ec(VexInfo vexs[ ],int i,int j)//判斷頂點(diǎn) i 和頂點(diǎn) j 是否屬于同一個(gè)連通分量 { if(vexs[i].eo==vexs[j].eo) return 1。 }//is_ec void merge_ec(VexInfo amp。vexs[i].vex。 }//merge_ec void MinSpanTree_Kruscal(Graph G,EdgeSetType amp。T)//求圖的最小生成樹(shù)的克魯斯卡爾算法 { Init_VexInfo(vexs,)。 //連通分量個(gè)數(shù) while(eum1) { GetMinEdge(EdgeSet,u,v)。 //加入到生成樹(shù)中 merge_ec(vexs,vexs[u].eo,vexs[v].eo)。 } DelMinEdge(EdgeSet,u,v)。T,int i,int j)//把邊 (i,j)添加到孩子兄弟鏈表表示的樹(shù)T中 { p=Locate(T,i)。 qdata=j。 //作為雙親的第一個(gè)孩子 else //雙親已經(jīng)有了孩子 { for(r=pfirstchild。r=rnextsib)。 //作為雙親最后一個(gè)孩子的兄弟 } }//Addto_CSTree 分析 :本算法使用一維結(jié)構(gòu)體變量數(shù)組來(lái)表示等價(jià)類 ,每個(gè)連通分量所包含的所有結(jié)點(diǎn)屬于一個(gè)等價(jià)類 .在這個(gè)結(jié)構(gòu)上實(shí)現(xiàn)了初始化 ,判斷元素是否等價(jià) (兩個(gè)結(jié)點(diǎn)是否屬于同一個(gè)連通分量 ),合并等價(jià)類 (連通分量 )的操作 . Status TopoSeq(ALGraph G,int new[ ])//按照題目要求給有向無(wú) 環(huán)圖的結(jié)點(diǎn)重新編號(hào) ,并存入數(shù)組 new 中 { int indegree[MAXSIZE]。 Initstack(S)。i。 count=0。new[i]=++count。p。 if(!(indegree[k])) Push(S,k)。 return OK。 void Get_Root(ALGraph G)//求有向無(wú)環(huán)圖的根 ,如果有的話 { for(v=0。v++) { for(w=0。w++) visited[w]=0。 //從頂點(diǎn) v出發(fā)進(jìn)行深度優(yōu)先遍歷 for(flag=1,w=0。w++) if(!visited[w]) flag=0。 }//for }//Get_Root,這個(gè)算法要求圖中不能有環(huán) ,否則會(huì)發(fā)生誤判 void DFS(ALGraph G,int v) { visited[v]=1。p。 if(!visited[w]) DFS(G,w)。G)//為有向無(wú)環(huán)圖 G添加 MPL域 { FindIndegree(G,indegree)。i。//從每一個(gè)零入度頂點(diǎn)出發(fā)構(gòu)建 MPL域 }//Fill_MPL int Get_MPL(ALGraph amp。 return 0。 for(p=[i].firstarc。p=pnextarc) { j=padjvex。 if(kmax) max=k。//再加一 ,就是當(dāng)前頂點(diǎn)的 MPL return max+1。 //數(shù)組 path用于存儲(chǔ)當(dāng)前路徑 int mlp[MAXSIZE]。 FindIndegree(G,indegree)。i。j。 if(!indegree[i]) DFS(G,i,0)。 for(i=0。i++) printf(%d,mlp[i])。 path[len]=i。amp。j=len。 //保存下來(lái) maxlen=len。p。 if(!visited[j]) DFS(G,j,len+1)。 visited[i]=0。 for(i=0。i++) if(!indegree[i]) r=i。 }//NiBoLan_DAG void PrintNiBoLan_DAG(ALGraph G,int i)//打印輸出以頂點(diǎn) i 為根的表達(dá)式 的逆波蘭式 { c=[i].data。 else //子表達(dá)式 { p=[i].firstarc。 PrintNiBoLan_DAG(G,pnexarcadjvex)。 } }//PrintNiBoLan_DAG void PrintNiBoLan_Bitree(Bitree T)//在二叉鏈表存儲(chǔ)結(jié)構(gòu)上重做上一題 { if(Tlchild) PrintNiBoLan_Bitree(Tlchild)。 printf(%c,Tdata)。 for(i=0。i++) if(!indegree[i]) r=i。 }//NiBoLan_DAG int Evaluate_imp(ALGraph G,int i)//求子表達(dá)式的值 { if([i].tag=NUM) return [i].value。 v1=Evaluate_imp(G,padjvex)。 return calculate(v1,[i].optr,v2)。 union { int value。 }。 } Elemtype。 for(i=0。i++) if(!indegree[i]) DFS1(G,i)。i。 //第二次深度優(yōu)先遍歷 :建立 vl for(i=0。i++) if(vl[i]==ve[i]) printf(%d,i)。 for(p=[i].firstarc。p=pnextarc) { dut=*pinfo。 DFS1(G,padjvex)。 else { for(p=[i].firstarc。p=pnextarc) { DFS2(G,padjvex)。 if(vl[padjvex]dutvl[i]) vl[i]=vl[padjvex]dut。P,ShortestPathTable amp。v。 for(p=[v0].firstarc。p=pnextarc) D[padjvex]=*pinfo。v。 for(w=0。w++) P[v][w]=0。 P[v][v]=1。final[v0]=1。i。 for(w=0。w++) if(!final[w]) if(D[w]min) //尚未求出到該頂點(diǎn)的最短路徑 { v=w。 } final[v]=1。p。 if(!final[w]amp。(min+(*pinfo)D[w])) //符合迪杰斯特拉條件 { D[w]=min+edgelen(G,v,w)。 P[w][