【正文】 都在S中為止。G)。用鄰接表創(chuàng)建有向圖時僅創(chuàng)建一個結點，其前驅為弧尾頂點，后記為弧頭頂點。 return 1。 if(![k].indegree) Push(s,k)。 for(p=[v].firstarc。i++) if(![i].indegree) Push(s,i)。 p=pnext。 for(i=1。 ArcNode *p。 pnext=[s].firstarc。i++) { printf(第%d條邊=起點序號,終點序號:,i)。 cin[i].data。 cin。}算法運行結果如下圖所示：void CreatDG_ALG(ALGraph amp。j=。 } cout創(chuàng)建的鄰接矩陣為：endl。 for(c=1。i++) for(j=1。i=。 cout請輸入頂點數,邊數:。 return 1。 if(![k].indegree) Push(s,k)。 for(p=[v].firstarc。i++) if(![i].indegree) Push(s,i)。 p=pnext。 for(i=1。 ArcNode *p。網中沒有前驅的頂點即是鄰接表中入度為0的頂點，而每當輸出一個頂點后，刪除以該頂點為尾的所有弧的操作通過將相應弧頭頂點的入度值減1實現。(2)從圖中刪除該頂點和所有以它為尾的弧。、有向圖應用的實現給定一個AOE網，將其全部頂點按照活動的先后關系排成一個線性序列，使得若活動vi是活動vj的前驅，則序列中vi應在vj的前面。、設計方案有向圖可用鄰接矩陣和鄰接表來創(chuàng)建，它與無向圖相比，其鄰接矩陣的定義為：A［i］［j］=用鄰接表創(chuàng)建有向圖時僅創(chuàng)建一個結點，其前驅為弧尾頂點，后記為弧頭頂點。 for(i=0。 b=j+1。i++) for(j=i+1。i++) set[i]=i。 } }}void Kruskal(MGraph G){ int set[MAXVEX],i,j。j++) if(closedge[j].lowcost!=0amp。 } printf((%c,%c,%d),[closedge[k].adjvex],[k],min)。j++) if(closedge[j].lowcost!=0amp。i。i++) { closedge[i].lowcost=[v][i]。 }closedge[MAXVEX]。 qnext=[d].firstarc。 pw=w。 p=(ArcNode *)malloc(sizeof(ArcNode))。 } for (i=1。i=。 ArcNode *q。 } cout鄰接矩陣創(chuàng)建完畢endl。i++) { for(j=1。 [j][i]=w。 for(c=1。i++) for(j=1。i=。 cout請輸入頂點數,邊數:。i。 } min=[a][b]=MAXCOST。j。 cout最小生成樹的各條邊為：endl。 int k=0,a=1,b=1,min=[a][b]。為了判斷某條邊加入到T集合是否構成回路，可以定義一個一維數組set[n]，存放T中每個頂點所在的連通分量的標號。在E中選擇權值最小的邊，若該邊依附的兩個頂點落在T中不同的連通分量上，則將該邊加入到T中，否則舍去此邊，選擇下一條權值最小的邊。 closedge[j].adjvex=k。j=。 k=j。j=。 for(i=1。i=。 int lowcost。初始狀態(tài)時，U=｛u1｝(u1為出發(fā)的頂點)，初始closedge[0].lowcost=0，數組的其他各分量的lowcost域是頂點u1到其余各頂點所構成的邊的權值，(ui,uj)(ui∈U,uj∈VU)，每選取一條邊，設置closedge[k1].lowcost=0表示頂點uk已加入集合U中。 /*該邊依附于集合U中的頂點*/ int lowcost。此時TE中必有n1條邊，T=(U,TE)為N的最小生成樹。構造最小生成樹可以有多種算法，以下是普里姆算法，克魯斯卡爾算法的說明。、實現過程其實現過程同無向圖的實現過程類似，其邊的輸入由由邊的兩個頂點和邊上的權組成。 //指向下一個邊結點}Vnode,AdjList[MAXVEX]。}ArcNode。 /*鄰接矩陣存儲的圖類型*/無向網的鄰接表構造方法與無向圖的構造方法相似，只需要在表結點中加入權值w即可。 /*頂點類型設為字符型*/typedef struct{ VertexType vexs[MAXVEX]。 } }}三、無向網的基本操作與應用無向圖的基本操作與應用包括用鄰接矩陣和鄰接表創(chuàng)建無向網以及以鄰接矩陣為存儲結構的兩種算法求最小生成樹(Prim算法和Kruskal算法)。 while(p) { if(visited[padjvex]!=1) { visited[padjvex]=1。 printf([%d,%c],v,[v].data)。 int vi。 p=[v].firstarc。 }}int visited[MAXVEX]={0}。 p=[i].firstarc。 printf(圖的鄰接表表示如下:\n)。 qnext=[d].firstarc。 padjvex=d。i++) { printf(第%d條邊=起點序號,終點序號:,i)。 cin[i].data。 cin。}算法運行結果如下圖所示：void CreatUDG_ALG(ALGraph amp。j=。 } cout創(chuàng)建的鄰接矩陣為：endl。c=。j=。i++) cin[i]。 cin。 } p=pnext。 p=[vi].firstarc。 visited[v]=1。以鄰接表作為圖的存儲結構的廣度優(yōu)先遍歷算法如下：void BFS(ALGraph G,int v){ LinkQueue Q。而當以鄰接表作其存儲結構時，深度優(yōu)先遍歷圖的時間復雜度為O(n+e)。 }}算法運行結果如下圖所示：在遍歷時，對圖中每個頂點至多訪問一次DFS函數，因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。 printf([%d,%c],v,[v].data)。這是一個遞歸的過程。圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式。圖的遍歷是圖的一種基本操作，圖的許多其他操作都是建立在遍歷的基礎上的。G)，用鄰接表創(chuàng)建無向圖的函數為CreatUDG_ALG(ALGraph amp。若圖G是無向圖，圖的鄰接表表示的空間代價是O(n+2e)；若圖G是有向圖，圖的鄰接表表示的空間代價是O(n+e)。int vexnum,arum。 //頂點信息 int indegree。 //鄰接點序號 int w。因此，每條邊在鏈表中存儲兩次。所有頭結點用一個順序表存放。有向圖的鄰接矩陣的第i行非零元素的個數正好為第i個頂點的出度OD（vi）,第i列非零元素的個數為第i個頂點的入度ID（vi）。 /*頂點表*/ int arcs[MAXVEX][MAXVEX]。二、無向圖的基本操作與應用無向圖的基本操作與應用包括用鄰接矩陣和鄰接表構造無向圖以及以鄰接表為存儲結構的無向圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。其形式化定義為：G=（V，E）V=｛vi|vi∈data object｝E={(vi,vj)|vi,vj∈V∧P(vi,vj)}圖是一種結構復雜的數據結構，其信息包括兩部分：圖中數據元素即頂點的信息，元素間的關系（頂點之間的關系）——邊或者弧的信息。}圖是由若干個頂點和若干條邊構成的結構，每個頂點具有任意多個前驅和后繼。 case 4: DN()。 case 2: UDN()。 do{ ShowMainMenu()。 } break。 SinMiniPathD(MG,n)。 } break。 dispgraph(ALG)。 cinn。 cout * 4 單源頂點最短路徑問題 *\n。 cout ***************有向網的基本操作及應用***************\n。}void DN(){ MGraph MG。 TopoSort(ALG)。 case 2: { CreatDG_ALG(ALG)。 cout ****************************************************\n。 cout * 1 創(chuàng)建有向圖的鄰接矩陣 *\n。 ALGraph ALG。 } break。 Prim(MG,n)。 } break。 switch(n){ case 1: CreatUNG_M(MG)。 cout * 4 kraskal算法求最小生成樹 *\n。 cout ***************無向網的基本操作及應用***************\n。}void UDN(){ MGraph MG。 BFS(ALG,n)。 } break。 case 3: { CreatUDG_ALG(ALG)。 break。 cout * 5 退出 *\n。 cout * 1 創(chuàng)建無向圖的鄰接矩陣 *\n。 ALGraph ALG。 cout * 4 有向網的基本操作及應用 *\n。 cout ***************圖的基本操作及應用******************\n。*******************************************************************include iostreamusing namespace std。測試文件()已給出。include include include include include void ShowMainMenu(){ cout\n。 cout * 3 有向圖的基本操作及應用 *\n。}void UDG(){ MGraph MG。 cout ***************無向圖的基本操作及應用***************\n。 cout * 4 無向圖的廣度優(yōu)先遍歷 *\n。 switch(n){ case 1: CreatUDG_M(MG)。 } break。 DFS(ALG,n)。 cinn。 } }while(n!=5)。 do{ cout\n。 cout * 3 prim算法求最小生成樹 *\n。 cinn。 dispgraph(ALG)。 cinn。 Kruskal(MG)。 }void DG(){ MGraph MG。 cout ***************有向圖的基本操作及應用***************\n。 cout * 4 退出 *\n。 break。 case 3: { CreatDG_ALG(ALG)。 } }while(n!=4)。 do{ cout\n。 cout * 3 關鍵路徑 *\n。 cout ****************************************************\n。 case 2: { CreatDNG_ALG(ALG)。