【正文】 rum。 //邊或狐上的權 struct ArcNode *next。G)。 p=[v].firstarc。 printf([%d,%c],v,[v].data)。 for(i=1。j++) cout[i][j] 。 cinsd。 while (p!=NULL) { printf([%d→],padjvex)。 EnQueue(Q,v)。其代碼如下：typedef struct ArcNode{ int adjvex。假設N=(V,E)是連通網(wǎng)，T=(U,TE)為N的最小生成樹，U是T的頂點集合，TE是T的邊集合。 }closedge[MAXVEX]。 } printf((%c,%c,%d),[closedge[k].adjvex],[k],min)。其初值為set[i]=i(i=0,1,2,…,n1)，表示各個頂點在不同的連通分量上。 //刪除該邊，下次不再查找 if(set[a]!=set[b]) { cout[a][b]endl。j=。}算法運行結果如下圖所示：void CreatUNG_ALG(ALGraph amp。 q=(ArcNode *)malloc(sizeof(ArcNode))。 closedge[i].adjvex=v。amp。 } min=[a][b]=MAXCOST。重復上述兩步，直到全部頂點已輸出，或者當前圖中不存在無前驅的頂點為止。 } } InitStack(s)。 }}算法運行結果如下圖所示：拓撲序列用來檢測AOE網(wǎng)中是否存在環(huán)以確定在一個流程圖中是否有有死循環(huán)從而減少工程的出錯率。c=。 for (i=1。 for(i=1。p。、有向網(wǎng)應用的實現(xiàn)從一個頂點到其余各頂點的最短路徑從某個源點到其余各頂點的最短路徑又稱為單源最短路徑。如果dist[j].length+[j][k]dist[k].length，則修改dist[k].length=dist[j].length+[j][k],dist[j].pre=j。 for(i=1。 } else break。然后在路徑上再增加一個頂點，設(vi,…,v1)和(v1,…,vj)分別是當前找到的從vi到v1和v1到vj中間頂點序號不大于0的最短路徑，比較(vi,…,v0，…,vj)和(vi,…,v1) +(v1,…,vj)的路徑長，取較短者作為從vi到vj且中間頂點的序號不大于1的最短路徑。j++) { D[i][j]=[i][j]。 ppath(G,path,k,j)。這個時間決定了所有以vj為尾的弧表示的活動的最早開始時間。用頭結點中增加一個存儲相應頂點的入度值域的特殊鄰接表作AOE網(wǎng)的存儲結構，求關鍵路徑的算法如下：int ve[MAXVEX],vl[MAXVEX]。 if(![i].indegree) Push(s,i)。T)!=) cout該網(wǎng)有回路！。 ee=ve[j]。j=。G){ int i,s,d,w。 pnext=[s].firstarc。 for(i=1。 } else break。i=。 if(k==1)return。 int i,v,k,count=0。 count++。 InitStack(T)。i=。 printf(%c\n,[j])。 path[i][j]=k。 }}void displaypath(MGraph,int[][MAXVEX],int[][MAXVEX])。j++) if(!final[j]amp。 if(dist[i].lengthMAXCOST) dist[i].pre=v。 cinsdw。j++) cout[i][j] 。i++) cin[i]。j++) for(p=[j].firstarc。 ArcNode *p。 p=pnext。(2)從源點v0出發(fā)，令ve[0]=0,按拓撲有序求其余各頂點的最早發(fā)生時間ve[i](1≤i≤n1)。由于AOE網(wǎng)中有些活動可以并行進行，故完成工程的最短時間是從源點到匯點的最長路徑長度(這里的路徑長度指路徑上的各活動持續(xù)時間之和)。 k=path[i][j]。 for(i=1。 }}算法運行結果如下圖所示： 每對頂點之間的最短路徑假設求從頂點vi到vj的最短路徑，弗洛伊德算法的基本思想是：如果從vi到vj有弧，則從vi到vj存在一條長度為cost[i][j]的路徑，該路徑不一定是最短路徑，因為可能存在從vi到vj且包含其他頂點為中間頂點的較短路徑。j++) if(!final[j]amp。 if(dist[i].lengthMAXCOST) dist[i].pre=v。因此，一般情況下，下一條長度次短的最短路徑的長度必是dist[j].length=min{dist[i].length|vi∈T}另引入一個數(shù)組final，用來標識頂點是否已經確定最短路徑。輸入時還應加上弧上的權w。 while(!StackEmpty(s)) { Pop(s,v)。 /*p插入頂點s的鄰接表中*/ [s].firstarc=p。G){ int i,s,d。j=。 } } if(count) { cout此有向圖有回路!endl。i=。具有這樣特性序列稱為拓撲有序序列。j。 closedge[k].lowcost=0。 int i,j,k,min。i=。j=。i++) cin[i]。j++) if([i+1][j+1]min) { min=[i+1][j+1]。依次類推，直到T中所有頂點都在同一連通分量上為止。j++) if(closedge[j].lowcost!=0amp。由于頂點uk從集合VU進入集合U后，這兩個集合的內容發(fā)生了變化，就需依據(jù)具體情況更新數(shù)組closedge中部分分量的內容。用鄰接矩陣創(chuàng)建無向網(wǎng)的函數(shù)為CreatUNG_M(MGraph amp。 /*頂點表*/ int arcs[MAXVEX][MAXVEX]。 ArcNode *p。 for (i=1。 [i].firstarc=NULL。 for(i=1。 printf(請輸入頂點:)。 int vi。以鄰接表為圖的存儲結構的深度優(yōu)先遍歷算法如下：int visited[MAXVEX]={0}。、實現(xiàn)過程鍵盤輸入圖的頂點數(shù)和邊數(shù)，[i]，用同樣的方法構造出鄰接矩陣。若無向圖中有n個頂點、e條邊，則它的鄰接表需n個頭結點和2e個表結點。、設計方案無向圖可以用鄰接矩陣、鄰接表兩種存儲結構來表示，用一維數(shù)組存儲圖的頂點的信息，用二維數(shù)組存儲圖中邊或弧的信息，該二維數(shù)組稱為鄰接矩陣。 break。 case 4: { CreatDNG_M(MG)。 cout * 1 創(chuàng)建有向網(wǎng)的鄰接矩陣 *\n。 cinn。 } break。 cout * 1 創(chuàng)建無向網(wǎng)的鄰接矩陣 *\n。 cout您打算從第幾個頂點開始訪問?endl。 int n。算法與數(shù)據(jù)結構課程項目設計方案一、課設目的與要求本次課設主要是圖的基本操作與應用，共包括四個部分：有向圖的基本操作與應用、無向圖的基本操作與應用、有向網(wǎng)的基本操作與應用、無向網(wǎng)的基本操作與應用。 do { cout\n。 cinn。 cout * 2 創(chuàng)建無向網(wǎng)的鄰接表 *\n。 case 4: { CreatUNG_M(MG)。 switch(n){ case 1: CreatDG_M(MG)。 cout * 2 創(chuàng)建有向網(wǎng)的鄰接表 *\n。 cout起始出發(fā)頂點為：。 case 3: DG()。設G=（V，E）為具有n個頂點的圖，若用二維數(shù)組A表示圖的鄰接矩陣，則A是一個n階的方陣，其中：A［i］［j］=鄰接矩陣的存儲結構定義如下：define MAXVEX 30 /*最大頂點數(shù)設為20*/typedef char VertexType。頂點vi的度恰為第i個鏈表中的結點數(shù)。兩點這有邊的賦值為1，否則為0。void DFS(ALGraph G,int v){ ArcNode *p。 ArcNode *p。 for(i=1。i=。 } for (i=1。i=。 InitQueue(Q)。 /*鄰接矩陣*/ int vexnum,arum。G)，用鄰接表創(chuàng)建無向網(wǎng)的函數(shù)為CreatUNG_ALG(ALGraph amp。最后closedge中即為所建立的最小生成樹。amp。此連通分量便為G的一棵最小生成樹。 //最小權值 a=i+1。 for(i=1。j++) cout[i][j] 。i++) { printf(第%d條邊=起點序號,終點序號，權值:,i)。 for(i=1。 for(j=1。j++) if([i+1][j+1]min) { min=[i+1][j+1]。構造拓撲序列的過程稱為拓撲排序。i++) { p=[i].firstarc。 return 0。j++) [i][j]=0。 ArcNode *p。 } }算法運行結果如下圖所示：int TopoSort(ALGraph G){ int i,k,v,count=0。 cout[v].data 。用鄰接矩陣創(chuàng)建有向網(wǎng)的函數(shù)為CreatDNG_M(MGraph amp。Final[i]=1,表明vi的最短路徑已經確定，即vi∈S。 else dist[i].pre=1。amp。尚需進行n次試探。i=。 if(k==1)return。路徑長度最長的路徑稱為關鍵路徑。如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關鍵路徑，算法終止：否則執(zhí)行步驟(3).(3)從匯點vn出發(fā)，令vl[n1]=ve[n1],按逆拓撲有序求其余各頂點的最遲發(fā)生時間vl[i](n2≥i≥2)。 } } for(i=1。 SqStack T。p。 for(i=1。 coutendl。 p=(ArcNode *)malloc(sizeof(ArcNode))。 else dist[i].pre=1。amp。void DouMiniPathF(MGraph G){ int path[MAXVEX][MAXVEX],D[MAXVEX][MAXVEX]。 } displaypath(G,D,path)。 printf(最短路徑為長度為：%d\n,D[i][j])。i++) { ve[i]=0。 if(tporder(G,。 } while(!StackEmpty(s)) { Pop(s,v)。int tporder(ALGraph G,SqStack *T) { SqStack s。 k=path[i][j]。 for(i=1。 dist[j].pre=k。 final[v]=1。 pw=w。}算法運行結果如下圖所示：void CreatDNG_ALG(ALGraph amp。i++) for(j=1。 dut=pw。 if(tporder(G,amp。i++) { ve[i]=0。若某條弧滿足條件ee(s)=el(s),則為關鍵活動。[j]從源點v1到vj的最長路徑長度叫做事件vj的最早發(fā)生時間。 cout[k]。j=。如果存在，則比較(vi,vj)和(vi,v0,vj)的路徑長度，取其中較短者為從vi到vj且中間頂點的序號不大于0的最短路徑。 dist[j].pre=k。 final[v]=1。當從集合T中選取頂點vj加入到集合S中，需要更新頂點v0到集合T中任一頂點vk的最短路徑長度值。G)。 for(p=[v].firstarc。 ArcNode *p。 cin。 for(c=1。 return 1。 p=pnext。(2)從圖中刪除該頂點和所