【正文】 ArcNode *p。 for(p=[v].firstarc。 p=pnext。 InitStack(s)。 else { printf(%c到%c的最短路徑為:%c,[i],[j],[i])。 cout[k]。j=。j=。 cout[k]。i=。 for(j=1。i++) { min=MAXCOST。i++) { final[i]=0。 } }算法運行結(jié)果如下圖所示：void SinMiniPathD(MGraph G,int v){ struct { int length。i=。 cout請輸入頂點數(shù),邊數(shù)：。i++) { for(j=1。 printf(請輸入邊和權(quán)值:\n)。 for(i=1。 if(ee==el) printf(%d,%d,%d,%d,%d\n,j,k,dut,ee,el)。 } } for(j=1。v=。 } } return count。 count++。i++) { p=[i].firstarc。 int i,v,k,count=0。el[i]ee[i]表示完成活動ak的時間余量，即在不延遲工期的前提下活動ak可以延遲的時間。[i]vl[i]是指在不推遲整個工期的前提下(即保證事件vn在ve(n)時刻發(fā)生的前提下),事件vi允許的最晚發(fā)生時間。 printf(最短路徑為長度為：%d\n,D[i][j])。 for(i=1。 } displaypath(G,D,path)。 } for(k=1。采用鄰接矩陣存儲時，求任意兩頂點間的最短路徑的弗洛伊德算法如下：void DouMiniPathF(MGraph G){ int path[MAXVEX][MAXVEX],D[MAXVEX][MAXVEX]。若(vi,…,vk)和(vk,…,vj)分別是從vi到vk和從vk到vj的中間頂點的序號不大于k1的最短路徑，則將(vi,…,vk，…,vj)和已經(jīng)得到的從vi到vj且中間頂點序號不大于k1的最短路徑相比較，取其長度較短者作為從vi到vj的中間頂點的序號不大于k的最短路徑。 cout[k]。i=。 for(j=1。i++) { min=MAXCOST。i++) { final[i]=0。以鄰接矩陣作為網(wǎng)的存儲結(jié)構(gòu)的迪杰斯特算法如下：void SinMiniPathD(MGraph G,int v){ struct { int length。假設下一條最短路徑的終點為vk，那么該路徑或者是弧(v0,vk),或者是中間只經(jīng)過集合S中的頂點而到達頂點vk的路徑。算法的基本思想是：把圖中的頂點分成兩個集合S和T，集合S中存放已確定最短路徑的頂點，集合T中存放尚未確定最短路徑的頂點。無向網(wǎng)的鄰接矩陣可定義為：A［i］［j］=其中，Wij表示邊(vi,vj)或弧vi,vj上的權(quán)值；∞表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。 [k].indegree。i=。i++) [i].indegree=0。 padjvex=d。i++) { printf(第%d個結(jié)點信息:,i)。 } cout鄰接矩陣創(chuàng)建完畢endl。 [i][j]=1。i=。G){ int i,j,c。 [k].indegree。i=。i++) [i].indegree=0。為了實現(xiàn)拓撲排序，采用一種特殊的鄰接表作AOE網(wǎng)的存儲結(jié)構(gòu)，即在頭節(jié)點中增加一個存儲相應頂點的入度值域。G)。 k++。i。 closedge[j].adjvex=k。 k=j。 for(i=1。 int lowcost。 qadjvex=s。 [i].firstarc=NULL。 ArcNode *p。i=。 printf(請輸入邊和權(quán)值:\n)。 for(i=1。 for(i=0。i++) for(j=i+1。其實現(xiàn)代碼如下：void Kruskal(MGraph G){ int set[MAXVEX],i,j。其基本思想是：設無向網(wǎng)為N=(V,E)，令N的最小生成樹的初態(tài)為只含有n個頂點而無邊的非連通圖T=(V,{})，圖中每個頂點自成一個連通分量。 for(j=1。 for(j=1。 for(i=1。不妨設無向網(wǎng)采用鄰接矩陣存儲(Mgraph G)，若存在分量closedge[i].lowcost =0，closedge[i].adjvex=i，[j]已并入U集合，([i], [j])是最小生成樹中的一條邊。重復上述操作，直到U=V為止。}ALGraph。 //邊或狐上的權(quán) struct ArcNode *next。鄰接矩陣存儲結(jié)構(gòu)定義如下：define MAXVEX 30 /*最大頂點數(shù)設為20*/typedef char VertexType。 p=[vi].firstarc。 }}void BFS(ALGraph G,int v){ LinkQueue Q。 } printf(∧\n)。 ArcNode *p。 q=(ArcNode *)malloc(sizeof(ArcNode))。i++) { printf(第%d個結(jié)點信息:,i)。 } cout鄰接矩陣創(chuàng)建完畢endl。 [j][i]=1。i++) for(j=1。 cout請輸入頂點數(shù),邊數(shù):。 while(!QueueEmpty(Q)) { EnQueue(Q,vi)。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復上述過程，直到圖中所有頂點都被訪問到為止。 p=pnext。若此時圖中還有頂點未被訪問，另選圖中一個未曾被訪問的頂點作起點，重復上述過程，直到圖中所有頂點都被訪問到為止。這一過程稱為圖的遍歷。設圖G有n個頂點，e條邊，圖的鄰接矩陣表示的空間代價是O(n2),只與圖的頂點數(shù)有關。typedef struct vnode{ VertexType data。鄰接表表示遠射圖，每條邊（vi,vj）在兩個頂點vi,vj的鏈表中各占一個表節(jié)點。 /*鄰接矩陣存儲的圖類型*/無向圖的鄰接矩陣是一個對稱矩陣，其第i行（或第i列）非零元素的個數(shù)為第i個頂點的度TD（vi）。此次僅討論前兩種存儲結(jié)構(gòu)。 } }while(n!=5)。 break。 DouMiniPathF(MG)。 KeyPath(ALG)。 cout ****************************************************\n。 do{ cout\n。 case 3: { CreatDG_ALG(ALG)。 cout * 4 退出 *\n。 }void DG(){ MGraph MG。 cinn。 cinn。 do{ cout\n。 cinn。 } break。 cout * 4 無向圖的廣度優(yōu)先遍歷 *\n。}void UDG(){ MGraph MG。include include include include include void ShowMainMenu(){ cout\n。*******************************************************************include iostreamusing namespace std。 cout * 4 有向網(wǎng)的基本操作及應用 *\n。 cout * 1 創(chuàng)建無向圖的鄰接矩陣 *\n。 break。 } break。}void UDN(){ MGraph MG。 cout * 4 kraskal算法求最小生成樹 *\n。 } break。 } break。 cout * 1 創(chuàng)建有向圖的鄰接矩陣 *\n。 case 2: { CreatDG_ALG(ALG)。}void DN(){ MGraph MG。 cout * 4 單源頂點最短路徑問題 *\n。 dispgraph(ALG)。 SinMiniPathD(MG,n)。 do{ ShowMainMenu()。 case 4: DN()。其形式化定義為：G=（V，E）V=｛vi|vi∈data object｝E={(vi,vj)|vi,vj∈V∧P(vi,vj)}圖是一種結(jié)構(gòu)復雜的數(shù)據(jù)結(jié)構(gòu)，其信息包括兩部分：圖中數(shù)據(jù)元素即頂點的信息，元素間的關系（頂點之間的關系）——邊或者弧的信息。 /*頂點表*/ int arcs[MAXVEX][MAXVEX]。所有頭結(jié)點用一個順序表存放。 //鄰接點序號 int w。int vexnum,arum。G)，用鄰接表創(chuàng)建無向圖的函數(shù)為CreatUDG_ALG(ALGraph amp。圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式。 printf([%d,%c],v,[v].data)。而當以鄰接表作其存儲結(jié)構(gòu)時，深度優(yōu)先遍歷圖的時間復雜度為O(n+e)。 visited[v]=1。 } p=pnext。i++) cin[i]。c=。j=。 cin。i++) { printf(第%d條邊=起點序號,終點序號:,i)。 qnext=[d].firstarc。 p=[i].firstarc。 p=[v].firstarc。 printf([%d,%c],v,[v].data)。 } }}三、無向網(wǎng)的基本操作與應用無向圖的基本操作與應用包括用鄰接矩陣和鄰接表創(chuàng)建無向網(wǎng)以及以鄰接矩陣為存儲結(jié)構(gòu)的兩種算法求最小生成樹(Prim算法和Kruskal算法)。 /*鄰接矩陣存儲的圖類型*/無向網(wǎng)的鄰接表構(gòu)造方法與無向圖的構(gòu)造方法相似，只需要在表結(jié)點中加入權(quán)值w即可。 //指向下一個邊結(jié)點}Vnode,AdjList[MAXVEX]。構(gòu)造最小生成樹可以有多種算法，以下是普里姆算法，克魯斯卡爾算法的說明。 /*該邊依附于集合U中的頂點*/ int lowcost。 int lowcost。 for(i=1。 k=j。 closedge[j].adjvex=k。為了判斷某條邊加入到T集合是否構(gòu)成回路，可以定義一個一維數(shù)組set[n]，存放T中每個頂點所在的連通分量的標號。 cout最小生成樹的各條邊為：endl。 } min=[a][b]=MAXCOST。 cout請輸入頂點數(shù),邊數(shù):。i++) for(j=1。 [j][i]=w。 } cout鄰接矩陣創(chuàng)建完畢endl。i=。 p=(ArcNode *)malloc(sizeof(ArcNode))。 qnext=[d].firstarc。i++) { closedge[i].lowcost=[v][i]。j++) if(closedge[j].lowcost!=0amp。j++) if(closedge[j].lowcost!=0amp。i++) set[i]=i。 b=j+1。、設計方案有向圖可用鄰接矩陣和鄰接表來創(chuàng)建，它與無向圖相比，其鄰接矩陣的定義為：A［i］［j］=用鄰接表創(chuàng)建有向圖時僅創(chuàng)建一個結(jié)點，其前驅(qū)為弧尾頂點，后記為弧頭頂點。(2)從圖中刪除該頂點和所有以它為尾的弧。 ArcNode *p。 p=pnext。 for(p=[v].firstarc。 return 1。i=。 for(c=1。j=。 cin。i++) { printf(第%d條邊=起點序號,終點序號:,i)。 ArcNode *p。 p=pnext。 for(p=