【正文】 操作也較復(fù)雜。G)。、實(shí)現(xiàn)過(guò)程鍵盤(pán)輸入圖的頂點(diǎn)數(shù)和邊數(shù)，[i]，用同樣的方法構(gòu)造出鄰接矩陣。}ALGraph。 ArcNode *firstarc。 //邊或狐上的權(quán) struct ArcNode *next。若無(wú)向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。其中，頭結(jié)點(diǎn)由兩個(gè)域組成：存儲(chǔ)頂點(diǎn)信息的data域和指向鏈表中第一個(gè)結(jié)點(diǎn)的指針域firstarc。鄰接表表示法類(lèi)似于樹(shù)的孩子鏈表表示法。 /*鄰接矩陣*/ int vexnum,arum。、設(shè)計(jì)方案無(wú)向圖可以用鄰接矩陣、鄰接表兩種存儲(chǔ)結(jié)構(gòu)來(lái)表示，用一維數(shù)組存儲(chǔ)圖的頂點(diǎn)的信息，用二維數(shù)組存儲(chǔ)圖中邊或弧的信息，該二維數(shù)組稱(chēng)為鄰接矩陣。無(wú)論采用爰方法建立圖的存儲(chǔ)結(jié)構(gòu)，都要完整、準(zhǔn)確地反映這兩方面的信息。頂點(diǎn)是一些具體對(duì)象的抽象，而邊是對(duì)象間關(guān)系的抽象。 break。 break。 cinn。 default: if (n!=6) cout錯(cuò)誤，重新輸入\n。 } break。 case 4: { CreatDNG_M(MG)。 } break。 switch(n) { case 1: CreatDNG_M(MG)。 cout * 5 每對(duì)頂點(diǎn)最短路徑問(wèn)題 *\n。 cout * 1 創(chuàng)建有向網(wǎng)的鄰接矩陣 *\n。 ALGraph ALG。 } break。 dispgraph(ALG)。 cinn。 cout * 2 創(chuàng)建有向圖的鄰接表 *\n。 int n。 default: if (n!=5) cout錯(cuò)誤，重新輸入\n。 } break。 case 3: { CreatUNG_M(MG)。 break。 cout * 5 退出 *\n。 cout * 1 創(chuàng)建無(wú)向網(wǎng)的鄰接矩陣 *\n。 ALGraph ALG。 } break。 case 4: { CreatUDG_ALG(ALG)。 cout您打算從第幾個(gè)頂點(diǎn)開(kāi)始訪問(wèn)?endl。 case 2: { CreatUDG_ALG(ALG)。 cout *************************************************\n。 cout * 2 創(chuàng)建無(wú)向圖的鄰接表 *\n。 int n。 cout * 5 退出 *\n。 cout * 1 無(wú)向圖的基本操作及應(yīng)用 *\n。typedef char VertexType。算法與數(shù)據(jù)結(jié)構(gòu)課程項(xiàng)目設(shè)計(jì)方案一、課設(shè)目的與要求本次課設(shè)主要是圖的基本操作與應(yīng)用，共包括四個(gè)部分：有向圖的基本操作與應(yīng)用、無(wú)向圖的基本操作與應(yīng)用、有向網(wǎng)的基本操作與應(yīng)用、無(wú)向網(wǎng)的基本操作與應(yīng)用。typedef int Elemtpye。 cout * 2 無(wú)向網(wǎng)的基本操作及應(yīng)用 *\n。 cout ***************************************************\n。 do { cout\n。 cout * 3 無(wú)向圖的深度優(yōu)先遍歷 *\n。 cinn。 dispgraph(ALG)。 cinn。 cout您打算從第幾個(gè)頂點(diǎn)開(kāi)始訪問(wèn)?endl。 default: if (n!=5) cout錯(cuò)誤，重新輸入\n。 int n。 cout * 2 創(chuàng)建無(wú)向網(wǎng)的鄰接表 *\n。 cout ****************************************************\n。 case 2: { CreatUNG_ALG(ALG)。 cout起始出發(fā)頂點(diǎn)為：。 case 4: { CreatUNG_M(MG)。 } }while(n!=5)。 do { cout\n。 cout * 3 拓?fù)渑判? *\n。 switch(n){ case 1: CreatDG_M(MG)。 } break。 default: if (n!=4) cout錯(cuò)誤，重新輸入\n。 int n。 cout * 2 創(chuàng)建有向網(wǎng)的鄰接表 *\n。 cout * 6 退出 *\n。 break。 case 3: { CreatDNG_ALG(ALG)。 cout起始出發(fā)頂點(diǎn)為：。 case 5: { CreatDNG_M(MG)。 } }while(n!=6)。 switch(n){ case 1: UDG()。 case 3: DG()。 default: if (n!=5) cout錯(cuò)誤，重新輸入\n。在具體應(yīng)用中，頂點(diǎn)和邊被賦予具體的含義。一般情況下圖有四種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣存儲(chǔ)、鄰接表存儲(chǔ)、十字鏈表存儲(chǔ)、鄰接多重表存儲(chǔ)。設(shè)G=（V，E）為具有n個(gè)頂點(diǎn)的圖，若用二維數(shù)組A表示圖的鄰接矩陣，則A是一個(gè)n階的方陣，其中：A［i］［j］=鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下：define MAXVEX 30 /*最大頂點(diǎn)數(shù)設(shè)為20*/typedef char VertexType。 /*圖中頂點(diǎn)數(shù)和邊數(shù)*/}MGraph。它對(duì)圖中的每個(gè)頂點(diǎn)vi建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用于存儲(chǔ)圖中與vi相鄰接的邊或信息。表結(jié)點(diǎn)由三個(gè)域組成：鄰接點(diǎn)域dajvex、指向下一條邊或弧的指針域nextarc和存儲(chǔ)邊或弧上相關(guān)信息（如權(quán)值等）的域info。頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)。}ArcNode。 //指向下一個(gè)邊結(jié)點(diǎn)}Vnode,AdjList[MAXVEX]。鄰接表存儲(chǔ)圖很容易找到任一頂點(diǎn)的鄰接點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)(vi和vj)之間是否有邊或弧相連，則需搜索第i個(gè)或第j個(gè)鏈表，不及鄰接矩陣方便。兩點(diǎn)這有邊的賦值為1，否則為0。給定一個(gè)圖G，我們希望從圖中的某個(gè)頂點(diǎn)出發(fā)，經(jīng)過(guò)一定的路線訪問(wèn)圖中所有可訪問(wèn)的頂點(diǎn)，使每個(gè)可訪問(wèn)到的頂點(diǎn)都被 訪問(wèn)且只被訪問(wèn)一次。在圖結(jié)構(gòu)中，如果有回路存在，那么一個(gè)頂點(diǎn)被訪問(wèn)之后，有可能沿回路又回到該頂點(diǎn)上。其具體思想是：從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到。void DFS(ALGraph G,int v){ ArcNode *p。 while(p) { if(!visited[padjvex]) DFS(G,padjvex)。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。其基本思想是：從圖中某頂點(diǎn)v出發(fā)，在訪問(wèn)了v之后依次訪問(wèn)v的各個(gè)未曾訪問(wèn)未被訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直到圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。 ArcNode *p。 EnQueue(Q,v)。 printf([%d,%c],padjvex,[padjvex].data)。G){ int i,j,c。 for(i=1。i=。 printf(請(qǐng)輸入邊:\n)。 [i][j]=1。i=。 coutendl。 ArcNode *p,*q。i=。 } for (i=1。 p=(ArcNode *)malloc(sizeof(ArcNode))。 pnext=[s].firstarc。 } }算法運(yùn)行結(jié)果如下圖所示：void dispgraph(ALGraph G){ int i。i=。 p=pnext。 visited[v]=1。 p=pnext。 InitQueue(Q)。 while(!QueueEmpty(Q)) { DeQueue(Q,vi)。 EnQueue(Q,padjvex)。無(wú)向網(wǎng)的鄰接矩陣可定義為：A［i］［j］=其中，Wij表示邊(vi,vj)或弧vi,vj上的權(quán)值；∞表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。 /*鄰接矩陣*/ int vexnum,arum。 //鄰接點(diǎn)序號(hào) int w。 //頂點(diǎn)信息 int indegree。int vexnum,arum。G)，用鄰接表創(chuàng)建無(wú)向網(wǎng)的函數(shù)為CreatUNG_ALG(ALGraph amp。普里姆算法的基本思想是：首先從集合V中任取一頂點(diǎn)(假設(shè)為u0)加入集合U中，這時(shí)U={u0}，TE={}，然后所有u∈U，v∈VU的邊(u,v)∈E中，選取具有最小權(quán)值的邊(u0,v0)加入集合TE，同時(shí)將頂點(diǎn)v0并入集合U中。對(duì)每個(gè)頂點(diǎn)vi∈VU，在輔助數(shù)組中存在一個(gè)相應(yīng)分量closedge［i1］，它包括兩個(gè)域：adjvex和lowcost，其中adjvex存儲(chǔ)該邊依附于集合U中的頂點(diǎn)，lowcost存儲(chǔ)該邊的權(quán)值。算法中將第i個(gè)頂點(diǎn)(設(shè)為vi+1)并入集合U中通過(guò)設(shè)置closedge[i].lowcost=0實(shí)現(xiàn)(即用closedge[i].lowcost=0表示頂點(diǎn)vi+1在U集合中, closedge[i].lowcost不為0表示vi+1在VU集合中)；選取U集合到VU集合具有最小權(quán)值的邊，通過(guò)在所有closedge[i].lowcost！=0(VU集合中的頂點(diǎn))的closedge[i].lowcost 中選擇最小的值來(lái)實(shí)現(xiàn)。最后closedge中即為所建立的最小生成樹(shù)。 int i,j,k,min。 closedge[i].adjvex=v。i++) { min=MAXCOST。amp。 closedge[k].lowcost=0。amp。克魯斯卡爾算法是一種按照網(wǎng)中邊權(quán)值不減的順序構(gòu)造最小生成樹(shù)的方法。此連通分量便為G的一棵最小生成樹(shù)。訪問(wèn)最小權(quán)值依附的兩個(gè)頂點(diǎn)，若它們不屬于同一個(gè)分量，則將這條邊作為最小生成樹(shù)的邊輸出，并合并它們所屬的兩個(gè)連通分量；若它們屬于同一分量，則選擇下一個(gè)最小權(quán)值依附的邊。i。i。 //最小權(quán)值 a=i+1。 k++。 } }}算法運(yùn)行結(jié)果如下圖所示：*******************************************************************void CreatUNG_M(MGraph amp。 printf(請(qǐng)輸入頂點(diǎn):)。 for(i=1。j++) [i][j]=MAXCOST。c++) { cinijw。 for(i=1。j++) cout[i][j] 。G){ int i,s,d,w。 cin。 cin[i].data。i++) { printf(第%d條邊=起點(diǎn)序號(hào),終點(diǎn)序號(hào)，權(quán)值:,i)。 padjvex=d。 pnext=[s].firstarc。 } }算法運(yùn)行結(jié)果如下圖所示：void Prim(MGraph G,int v){ struct { int adjvex。 for(i=1。 } closedge[v].lowcost=0。 for(j=1。closedge[j].lowcostmin) { min=closedge[j].lowcost。 for(j=1。[k][j]closedge[j].lowcost) { close