【正文】 KeyPath(ALG)。 cinn。 DouMiniPathF(MG)。 }void main(){ int n。 break。 break。 } }while(n!=5)。如一個交通圖中，用頂點(diǎn)代表城市，邊表示城市之間的交通聯(lián)系。此次僅討論前兩種存儲結(jié)構(gòu)。 /*頂點(diǎn)類型設(shè)為字符型*/typedef struct{ VertexType vexs[MAXVEX]。 /*鄰接矩陣存儲的圖類型*/無向圖的鄰接矩陣是一個對稱矩陣，其第i行（或第i列）非零元素的個數(shù)為第i個頂點(diǎn)的度TD（vi）。頭結(jié)點(diǎn)中存放該頂點(diǎn)的信息。鄰接表表示遠(yuǎn)射圖，每條邊（vi,vj）在兩個頂點(diǎn)vi,vj的鏈表中各占一個表節(jié)點(diǎn)。鄰接表存儲結(jié)構(gòu)的定義如下：typedef struct ArcNode{ int adjvex。typedef struct vnode{ VertexType data。typedef struct{ AdjList vertices。設(shè)圖G有n個頂點(diǎn)，e條邊，圖的鄰接矩陣表示的空間代價是O(n2),只與圖的頂點(diǎn)數(shù)有關(guān)。用鄰接矩陣創(chuàng)建無向圖的函數(shù)為CreatUDG_M(MGraph amp。這一過程稱為圖的遍歷。為了避免同一頂點(diǎn)被訪問多次，當(dāng)頂點(diǎn)vi被訪問時，對應(yīng)的數(shù)組元素置1，否則置0。若此時圖中還有頂點(diǎn)未被訪問，另選圖中一個未曾被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。 visited[v]=1。 p=pnext。對于n個頂點(diǎn)，e條邊或弧的圖，當(dāng)用鄰接矩陣作其存儲結(jié)構(gòu)時，深度遍歷圖的時間復(fù)雜度為O(n2)。若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。 InitQueue(Q)。 while(!QueueEmpty(Q)) { EnQueue(Q,vi)。 EnQueue(Q,padjvex)。 cout請輸入頂點(diǎn)數(shù),邊數(shù):。i=。i++) for(j=1。 for(c=1。 [j][i]=1。i++) { for(j=1。 } cout鄰接矩陣創(chuàng)建完畢endl。 cout請輸入頂點(diǎn)數(shù),邊數(shù)：。i++) { printf(第%d個結(jié)點(diǎn)信息:,i)。i=。 q=(ArcNode *)malloc(sizeof(ArcNode))。 /*p插入頂點(diǎn)s的鄰接表中*/ [s].firstarc=p。 ArcNode *p。i++) { printf( [%d,%c]=,i,[i].data)。 } printf(∧\n)。 printf([%d,%c],v,[v].data)。 }}void BFS(ALGraph G,int v){ LinkQueue Q。 visited[v]=1。 p=[vi].firstarc。 } p=pnext。鄰接矩陣存儲結(jié)構(gòu)定義如下：define MAXVEX 30 /*最大頂點(diǎn)數(shù)設(shè)為20*/typedef char VertexType。 /*圖中頂點(diǎn)數(shù)和邊數(shù)*/}MGraph。 //邊或狐上的權(quán) struct ArcNode *next。 ArcNode *firstarc。}ALGraph。G)。重復(fù)上述操作，直到U=V為止。Closedge的結(jié)構(gòu)定義為：struct { int adjvex。不妨設(shè)無向網(wǎng)采用鄰接矩陣存儲(Mgraph G)，若存在分量closedge[i].lowcost =0，closedge[i].adjvex=i，[j]已并入U集合，([i], [j])是最小生成樹中的一條邊。當(dāng)無向網(wǎng)采用鄰接矩陣存儲時，Prim算法如下：void Prim(MGraph G,int v){ struct { int adjvex。 for(i=1。 } closedge[v].lowcost=0。 for(j=1。closedge[j].lowcostmin) { min=closedge[j].lowcost。 for(j=1。[k][j]closedge[j].lowcost) { closedge[j].lowcost=[k][j]。其基本思想是：設(shè)無向網(wǎng)為N=(V,E)，令N的最小生成樹的初態(tài)為只含有n個頂點(diǎn)而無邊的非連通圖T=(V,{})，圖中每個頂點(diǎn)自成一個連通分量。在訪問各頂點(diǎn)的同時，用循環(huán)語句計算出權(quán)值最小的兩個頂點(diǎn)，并用a、b記錄其弧頭和弧尾的頂點(diǎn)。其實(shí)現(xiàn)代碼如下：void Kruskal(MGraph G){ int set[MAXVEX],i,j。i++) set[i]=i。i++) for(j=i+1。 b=j+1。 for(i=0。G){ int i,j,c,w。 for(i=1。i=。 printf(請輸入邊和權(quán)值:\n)。 [i][j]=w。i=。 coutendl。 ArcNode *p。 for (i=1。 [i].firstarc=NULL。 cinsdw。 qadjvex=s。 /*p插入頂點(diǎn)s的鄰接表中*/ [s].firstarc=p。 int lowcost。i=。 for(i=1。j=。 k=j。j=。 closedge[j].adjvex=k。i。i。 //最小權(quán)值 a=i+1。 k++。 } }}四、有向圖的基本操作與應(yīng)用有向圖的基本操作與應(yīng)用包括用鄰接矩陣和鄰接表創(chuàng)建有向圖以及以鄰接表為存儲結(jié)構(gòu)的拓?fù)渑判虻乃惴?。G)。求拓?fù)溆行蛐蛄械牟襟E為：(1)在AOE網(wǎng)中選一個沒有前驅(qū)的頂點(diǎn)，并輸出之。為了實(shí)現(xiàn)拓?fù)渑判颍捎靡环N特殊的鄰接表作AOE網(wǎng)的存儲結(jié)構(gòu)，即在頭節(jié)點(diǎn)中增加一個存儲相應(yīng)頂點(diǎn)的入度值域。 SqStack s。i++) [i].indegree=0。 while(p) { [padjvex].indegree++。i=。 count++。 [k].indegree。 } else { coutendl為一個拓?fù)湫蛄?endl。G){ int i,j,c。 for(i=1。i=。 printf(請輸入邊:\n)。 [i][j]=1。i++) { for(j=1。 } cout鄰接矩陣創(chuàng)建完畢endl。 cout請輸入頂點(diǎn)數(shù),邊數(shù)：。i++) { printf(第%d個結(jié)點(diǎn)信息:,i)。i=。 padjvex=d。 SqStack s。i++) [i].indegree=0。 while(p) { [padjvex].indegree++。i=。 count++。 [k].indegree。 } else { coutendl為一個拓?fù)湫蛄?endl。無向網(wǎng)的鄰接矩陣可定義為：A［i］［j］=其中，Wij表示邊(vi,vj)或弧vi,vj上的權(quán)值；∞表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。G)，用鄰接表創(chuàng)建有向網(wǎng)的函數(shù)為CreatDNG_ALG(ALGraph amp。算法的基本思想是：把圖中的頂點(diǎn)分成兩個集合S和T，集合S中存放已確定最短路徑的頂點(diǎn)，集合T中存放尚未確定最短路徑的頂點(diǎn)。Dis的初值為：若從v0到vi有弧，則dist[i].length為弧上的權(quán)值；否則為∞。假設(shè)下一條最短路徑的終點(diǎn)為vk，那么該路徑或者是弧(v0,vk),或者是中間只經(jīng)過集合S中的頂點(diǎn)而到達(dá)頂點(diǎn)vk的路徑。final[i]=0，表明vi∈T。以鄰接矩陣作為網(wǎng)的存儲結(jié)構(gòu)的迪杰斯特算法如下：void SinMiniPathD(MGraph G,int v){ struct { int length。 int i,j,k,min。i++) { final[i]=0。 } dist[v].pre=1。i++) { min=MAXCOST。amp。 for(j=1。(min+[k][j]dist[j].length)) { dist[j].length=min+[k][j]。i=。 j=dist[i].pre。 cout[k]。首先考慮路徑(vi,v0,vj)是否存在(即判別弧(vi,v0)和(v0,vj)是否存在)。若(vi,…,vk)和(vk,…,vj)分別是從vi到vk和從vk到vj的中間頂點(diǎn)的序號不大于k1的最短路徑，則將(vi,…,vk，…,vj)和已經(jīng)得到的從vi到vj且中間頂點(diǎn)序號不大于k1的最短路徑相比較，取其長度較短者作為從vi到vj的中間頂點(diǎn)的序號不大于k的最短路徑。而產(chǎn)生D(1),D(0),D(1),…，D(k),D(n1)的過程就是逐步允許越來越多的頂點(diǎn)作為路徑的中間頂點(diǎn)，直到所有可能的頂點(diǎn)均作為中間頂點(diǎn)。采用鄰接矩陣存儲時，求任意兩頂點(diǎn)間的最短路徑的弗洛伊德算法如下：void DouMiniPathF(MGraph G){ int path[MAXVEX][MAXVEX],D[MAXVEX][MAXVEX]。i++) for(j=1。 } for(k=1。i++) for(j=1。 } displaypath(G,D,path)。 ppath(G,path,i,k)。 for(i=1。j++) if(D[i][j]==MAXCOST) printf(%c到%c沒有路徑可達(dá),[i],[j])。 printf(最短路徑為長度為：%d\n,D[i][j])。為了確定AOE網(wǎng)的關(guān)鍵路徑，首先定義下列幾個參數(shù)。[i]vl[i]是指在不推遲整個工期的前提下(即保證事件vn在ve(n)時刻發(fā)生的前提下),事件vi允許的最晚發(fā)生時間。所以，活動ak的最早開始時間應(yīng)等于事件vi的最早發(fā)生時間。el[i]ee[i]表示完成活動ak的時間余量，即在不延遲工期的前提下活動ak可以延遲的時間。(4)根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開始時間ee(s)和最遲開始時間el(s)。 int i,v,k,count=0。i=。i++) { p=[i].firstarc。i=。 count++。p=pnext) { k=padjvex。 } } return count。 InitStack(T)。v=。p。 } } for(j=1。p=pnext) { k=padjvex。 if(ee==el) printf(%d,%d,%d,%d,%d\n,j,k,dut,ee,el)。G){ int i,j,c,w。 for(i=1。i=。 printf(請輸入邊和權(quán)值:\n)。 [i][j]=w。i++) { for(j=1。 } cout鄰接矩陣創(chuàng)建完畢endl。 cout請輸入頂點(diǎn)數(shù),邊數(shù)：。i++) { printf(第%d個結(jié)點(diǎn)信息:,i)。i=。 padjvex=d。 } }算法運(yùn)行結(jié)果如下圖所示：void SinMiniPathD(MGraph G,int v){ struct { int length。 int i,j,k,min。i++) { final[i]=0。 } dist[v].pre=1。i++) { min=MAXCOST。amp。 for(j=1。(min+[k][j]dist[j].length)) { dist[j].length=min+[k][j]。i=。 j=dist[i].pre。 cout[k]。 int i,j,k。j=。k=。j=。}void ppath(MGraph G,int path[][MAXVEX],int i,int j){ int k。 cout[k]。i=。 else { printf(%c到%c的最短路徑為:%c,[i],[j],[i])。 }}int ve[MAXVEX],vl[MAXVEX]。 InitStack(s)。 for(i=1。 p=pnext。 if(![i].indegree) Push(s,i)。 for(p=[v].firstarc。 if(![k].indegree) Push(s,k)。 ArcNode