【正文】 rn ERROR。 next=pnext。 =p。 return OK。m=G.vexnum。 } return OK。break。 case 3: =UDG。 int visited[MAX_VERTEX_NUM]。 //隊列 typedef struct { int *base。 GraphKind kind。 int quan。 //infotype *info。如果得到的拓撲有序序列中的頂點個數小于網中的頂點數，則說明網中存在環(huán)，不能求關鍵路徑，算法終止；否則執(zhí)行第三步。當圖中所有頂點都被訪問到后，就完成了圖的廣度優(yōu)先搜索遍歷。 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。 圖的鄰接表存儲結構是圖的一種鏈式存儲結構。由于顯示菜單已給出，剩下的只是把函數寫入其中，而線性表、棧和隊列的基本操作并不復雜，很容易實現，我們只有完成圖的相關操作即可。 default:printf(ERROR!)。break。 default:printf(ERROR!)。break。 printf(* 3 關鍵路徑 *\n)。 case 5:break。 switch(n){ case 1: printf(wait)。 printf(* 2 創(chuàng)建無向網的鄰接表 *\n)。break。 printf(請選擇：)。 } void DG(){ int n。break。 printf(* 5 退出\n)。 printf(***********************************************\n)。內容如下： 1． 無向圖的基本操作及應用 ① 創(chuàng)建無向圖的鄰接矩陣 ② 創(chuàng)建無向圖的鄰接表 ③ 無向圖的深度優(yōu)先遍歷 ④ 無向圖的廣度優(yōu)先遍歷 2．有向圖的基本操作及應用 ①創(chuàng)建有向圖的鄰接矩陣 ② 創(chuàng)建有向圖的鄰接表 ③ 拓撲排序 3．無向網的基本操作及應用 ① 創(chuàng)建無向網的鄰接矩陣 ② 創(chuàng)建無向網的鄰接表 ③ 求最小生成樹 4．有向網的基本操作及應用 ① 創(chuàng)建有向網的鄰接矩陣② 創(chuàng)建有向網的鄰接表 ③ 關鍵路徑 ④ 單源最短路徑 三．設計指導 第一步：根據設計任務，設計DOS菜單。 一．設計目的 1．提高數據抽象能力。根據實際問題，能利用數據結構理論課中所學到的知識選擇合適的邏輯結構以及存儲結構，并設計出有效解決問題的算法。 第二步：設計菜單（c語言） include void ShowMainMenu(){ printf(\n)。 } void UDG(){ int n。 printf(***********************************\n)。 case 3: printf(wait)。 do{ printf(\n)。 scanf(%d,amp。 case 4:break。 printf(* 3 Prim算法求最小生成樹 *\n)。break。 default: printf(ERROR!)。 printf(* 4 單源頂點最短路徑問題 *\n)。 case 2: printf(wait)。 } }while(n!=5)。 case 2:DG()。break。 圖的操作都是以兩種存儲結構為基礎的，鄰接矩陣存儲結構和鄰接表存儲 結構，如四種圖（有向圖，有向網，無向圖，無向網）的創(chuàng)建，其他的操作都是在四種圖創(chuàng)建后才開始進行的。對圖中的每個頂點建立一個單鏈表，每個結點有三個域組成，鄰接點域adjvex（弧尾在鄰接表鏈表中的位序），鏈域nextarc（下一條?。瑪祿騣nfo(權值)。以某個頂點為起始頂點，由近至遠，依次訪問和該頂點有路徑相通的且路徑長度為1， 2， 3， 求無向網的最小生成樹問題有兩種算法：Prima算法和Kruskal算法。 從匯點vn出發(fā)，令vl[n1]=ve[n1]，按逆拓撲有序求其余各頂點的最遲發(fā)生時間vl[i]； 根據各頂點的和值，求每條弧的最早開始時間e(s)和最遲開始時間e(s)，若某條弧滿足條件e(s)=l(s)，則為關鍵活動。 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 struct ArcNode *nextarc。 }ALGraph。 int *top。 //頂點訪問標記數組 int indegree[MAX_VERTEX_NUM]。break。 case 2: =DN。 } //鄰接表類型設置 int LocateVex(MGraph G,char v){ int m。m++){ if(G.vertices[m].data==v) return m。 } //隊列創(chuàng)建 int EnQueue(LinkQueue amp。 return OK。 if(==p) =。 =。 } *++=e。 return ERROR。,amp。 scanf(%c,amp。 for(k=1。 G.arcs[i][j].adj=1。 i=LocateVex(G,x)。j++) G.arcs[i][j].adj=INT_MAX。w)。 scanf(%c%c %d,amp。 } } } return OK。 ,amp。 scanf(%c,amp。 scanf(%c%c,amp。 qnextarc=NULL。} else pnextarc=q。 m=LocateVex(G,x)。amp。j=G.arum。 p=G.vertices[m].firstarc。pnextarc){ p=pnextarc。 scanf(%c%c %d,amp。 if(!q) return ERROR。 } if(!key[m]){G.vertices[m].firstarc=q。 if(snextarc) return snextarcadjvex。 } } void DFSTraverse(ALGraph G){ int v。 } //圖的深度遍歷 void BFSTraverse(ALGraph G){ int v,w,u。v=G.vexnum。 printf(%c ,G.vertices[w])。 for(i=1。SqStack S。 while(!StackEmpty(S)){ Pop(S,i)。 else return OK。closedges closedge。i=G.vexnum。 } } } //求最小生成樹 int TopologicalOrder(ALGraph G,SqStack amp。i++) if(!indegree[i]) Push(S,i)。++count。 } int CriticalPath(ALGraph G){ int i,j,k,ee,el,dut,v1[MAX_VERTEX_NUM]。 } while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc。p。 39。 printf(請選擇對有向圖進行的操作：\n1創(chuàng)建鄰接矩陣\n2創(chuàng)建鄰接表\n3拓撲結構\n4退出\n)。i=。 for(i=1。 s=snextarc。 }printf(\n)。 printf(請選擇對有向網進行的操作：\n1創(chuàng)建鄰接矩陣\n2創(chuàng)建鄰接表\n3關鍵路徑\n4退出\n)。i=。 printf(有向網的鄰接表：\n)。i=。j=。 printf(請選擇：)。 } printf(\n\n)。 }break。i++){ printf(%c:,[i])。j=。 printf(請選擇：)。 } return OK。dut=pquan。p=pnextarc){ k=padjvex。 AList p。p。count=1。 SqStack S。 printf(%c%c ,closedge[k].adjvex,G.vexs[k])。 for(j=1。 for(i=