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