【正文】 //i,j從位置值轉(zhuǎn)換為下標(biāo)值 [i*+j]=1。 } //根據(jù)頂點(diǎn)信息找到所在位置 while(!((i=LocateVex_MG(G,u))amp。 else cout輸入圖中條邊(弧)和權(quán)的信息u v w:\n。i++) // for(j=0。i++) { [i].flag=0。 // =new VType[*]。 cout輸入頂點(diǎn)數(shù)vexnum和弧數(shù)arum:。}(3)鄰接矩陣的建立操作函數(shù)的功能是，根據(jù)圖G的種類標(biāo)志kind建立圖G的所有信息。i。 //圖的種類標(biāo)志kind }。 //頂點(diǎn)與訪問情況類型VNode{訪問次數(shù),頂點(diǎn)信息}struct MGraph{ //定義圖的鄰接矩陣類型MGraph VNode* vexs。 //圖的類型GKind{有向圖,有向網(wǎng),無向圖,無向網(wǎng)}typedef int VType。如果G是無權(quán)圖，則A的定義為：如果G是有權(quán)圖，則A的定義為：【】、。鄰接矩陣表示法是圖的一種順序存儲(chǔ)表示法。G,v,w) 函數(shù)功能是，在圖G中增加邊(v,w)或弧v,w；（10）刪除弧DeleteArc(amp。G,v,value) 函數(shù)功能是，修改圖G中頂點(diǎn)v的信息為value；（5）鄰接點(diǎn)FirstAdjVex(G,v) 函數(shù)功能是，返回圖G中頂點(diǎn)v的第一個(gè)鄰接點(diǎn)在G中的位置，操作不成功時(shí)返回0；（6）下一個(gè)鄰接點(diǎn)NextAdjVex(G,v,w) 函數(shù)中v,w是圖G的頂點(diǎn)，且w是v的一個(gè)鄰接點(diǎn)。所以，“頂點(diǎn)在圖中的位置”是指該頂點(diǎn)在這個(gè)人為的隨意排列中的位置（或序號(hào)）。顯然，一個(gè)有向圖生成的有向樹或生成森林都不是唯一的。但是有n個(gè)頂點(diǎn)和n1條邊的無向圖不一定是生成樹。說明：在連通分量和強(qiáng)連通分量定義中的“極大”應(yīng)理解為包含依附于該連通子圖或強(qiáng)連通子圖中頂點(diǎn)的所有邊或弧。（18）連通分量(Connected ponent) 無向圖G中的極大連通子圖稱為G的連通分量。例如，(a)所示的有向圖中，頂點(diǎn)序列(v1,v3,v4,v1,v2)表示一條有向路徑，由于其中存在重復(fù)點(diǎn)v1所以不是簡(jiǎn)單路徑，該路徑的長(zhǎng)度為4；頂點(diǎn)序列(v1,v3,v4)表示一條有向路徑，并且是長(zhǎng)度為2的簡(jiǎn)單路徑；頂點(diǎn)序列(v1,v3,v4,v1)表示一條有向路徑并且是長(zhǎng)度為3的簡(jiǎn)單回路（或環(huán)）。路徑長(zhǎng)度是指路徑上的邊或弧的數(shù)目。（13）度(Degree) 在無向圖中，頂點(diǎn)v的度是指和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)。（11）子圖(Subgraph) 假設(shè)有兩個(gè)圖G=(V,E)和G’=(V’,E’)，若V’V并且E’E，則稱G’是G的子圖。(a)所示為由4個(gè)頂點(diǎn)組成的無向完全圖，(b)則是由3個(gè)頂點(diǎn)組成的有向完全圖。比如，(b)表示一個(gè)無向圖。比如，(a)表示一個(gè)有向圖。（3）弧尾(Tail) 弧的起始點(diǎn)。（1）頂點(diǎn)(Vertex) 圖中的數(shù)據(jù)元素。圖G(graph) 是由兩個(gè)集合V和VR組成，記為G=(V,VR)。比如，可以用線性表來表示數(shù)據(jù)對(duì)象之間的線性關(guān)系，用樹結(jié)構(gòu)來表示數(shù)據(jù)對(duì)象之間的某種層次關(guān)系。但是，還有許多問題（比如信息通信網(wǎng)絡(luò)）中的數(shù)據(jù)對(duì)象是不能用以上兩種關(guān)系來明確表示的，這就需要一種更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)—圖結(jié)構(gòu)。V是頂點(diǎn)的有窮非空集合；VR是定義在V上的所有關(guān)系（兩個(gè)不同頂點(diǎn)之間的弧或邊）的集合。比如，：v1,v2,v3,v4,v5,v6。（4）弧頭(Head) 弧的終端點(diǎn)。（6）邊(Edge) 設(shè)VR是圖中所有頂點(diǎn)之間的關(guān)系集，若v,w∈VR必有w,v∈VR，則以無序?qū)Ψ?hào)(v,w)或(w,v)來代替v,w和w,v，表示頂點(diǎn)v與頂點(diǎn)w之間的一條邊。（8）完全圖(Completed graph) 用n表示圖中的頂點(diǎn)數(shù)，則具有n(n1)/2條邊的無向圖稱為無向完全圖；具有n(n1)條弧的有向圖稱為有向完全圖。（9）權(quán)(Weight) 與圖的邊或弧相關(guān)的數(shù)（比如長(zhǎng)度）稱為權(quán)。例如，(a)為有向圖及其部分子圖，(b)為無向圖及其部分子圖。（14）出度(Out degree)和入度(In degree) 在有向圖中，頂點(diǎn)v的出度是指以v為弧尾的弧的數(shù)目，記為OD(v)；頂點(diǎn)v的入度是指以v為弧頭的弧的數(shù)目，記為ID(v)；頂點(diǎn)v的度是指v的出度、入度的和，記為TD(v)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。(b)所示的無向圖中，頂點(diǎn)序列(v1,v3,v5,v4,v3,v5,v2)表示一條路徑，由于其中存在重復(fù)點(diǎn)vv5所以不是簡(jiǎn)單路徑；頂點(diǎn)序列(v1,v3,v4,v5,v2,v1)是長(zhǎng)度為5的簡(jiǎn)單回路。（19）強(qiáng)連通圖 在有向圖G=(V,VR)中，如果對(duì)于任意兩個(gè)頂點(diǎn)v,w∈V，都存在一條v到w的路徑，則稱G是強(qiáng)連通圖；如果對(duì)于任意兩個(gè)頂點(diǎn)v,w∈V，都存在一個(gè)頂點(diǎn)序列：v=v0,v1,v2,…,vk=w滿足vi,vi+1或vi+1,vi∈VR，則稱G是弱連通圖。（21）生成樹 一個(gè)無向連通圖的生成樹是一個(gè)極小連通子圖，即它包含圖中的所有（假設(shè)n個(gè)）頂點(diǎn)，但是只有足以構(gòu)成一棵樹的n1條邊。例如，((a))和它的3棵生成樹((b))的示例。關(guān)于“頂點(diǎn)位置”的說明：在圖的基本操作定義中，其“頂點(diǎn)位置”和“鄰接點(diǎn)位置”僅是一個(gè)相對(duì)的概念。同理，可以對(duì)某個(gè)頂點(diǎn)的所有鄰接點(diǎn)按照某個(gè)任意選定的順序進(jìn)行排列。函數(shù)功能是，返回頂點(diǎn)v相對(duì)于w的下一個(gè)鄰接點(diǎn)所在的位置，如果w是v的最后一個(gè)鄰接點(diǎn)則返回0；（7）插入頂點(diǎn)InsertVex(amp。G,v,w) 函數(shù)功能是，在圖G中刪除邊(v,w)或弧v,w；（11）深度優(yōu)先遍歷DSFTraverse(G,v,Visit()) 函數(shù)功能是，從頂點(diǎn)v開始按深度優(yōu)先遍歷圖G，其中Visit()是關(guān)于頂點(diǎn)的操作函數(shù)；（12）廣度優(yōu)先遍歷BSFTraverse(G,v,Visit()) 函數(shù)功能是，從頂點(diǎn)v開始按廣度優(yōu)先遍歷圖G，其中Visit()是關(guān)于頂點(diǎn)的操作函數(shù)。用兩個(gè)數(shù)組分別存儲(chǔ)數(shù)據(jù)元素（頂點(diǎn)）的信息和元素之間所存在的關(guān)系(邊或弧)的信息。(a)、(b)中，(a)、(b)所示；(a)、(b)中，(c)、(d)所示。 //為便于操作，定義頂點(diǎn)類型VType為int 型struct VNode{int flag。 //描述頂點(diǎn)的數(shù)組指針vexs VType* arcs。(2)查找圖中頂點(diǎn)位置的操作函數(shù)的功能是，返回頂點(diǎn)u在圖G中的位置，查找失敗返回0值。i++) if([i].vex==u) break。includevoid CreateGraph_MG(MGraphamp。 cin。 // cout按某種順序輸入個(gè)頂點(diǎn)的值:\n。 //flag=0表示該頂點(diǎn)未被訪問 cin[i].vex。j。 for(k=0。amp。 if(==DN||==UDN) cin[i*+j]。 for(i=0。j++) cout[i*+j]39。void main(){ MGraph G1,G2,G3,G4。 cout建立一個(gè)無向圖的鄰接矩陣G2:\n。 cout無向圖G2的鄰接矩陣為:\n。 CreateGraph_MG(G3,gk3)。 DisplyMG(G3)。（2）在圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)上也容易實(shí)現(xiàn)其它基本操作，比如，對(duì)于無向圖G中返回頂點(diǎn)v的第一個(gè)鄰接點(diǎn)位置的基本操作函數(shù)：int FirstAdjVex_MG(MGraph G,VType v)。由于鄰接矩陣的存儲(chǔ)空間僅與頂點(diǎn)數(shù)n有關(guān)，而與邊無關(guān)，因此，當(dāng)圖G的頂點(diǎn)較多而邊數(shù)又很少時(shí)，其邊的查找效率會(huì)很低。鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)域值：一個(gè)是頂點(diǎn)位置（下標(biāo)）域，用于表示該鄰接點(diǎn)的序號(hào)；另一個(gè)是指針域，用于指向下一個(gè)鄰接點(diǎn)。每個(gè)頭結(jié)點(diǎn)由3個(gè)域組成：結(jié)點(diǎn)信息域(data)、結(jié)點(diǎn)訪問次數(shù)域(flag)和指向鏈表中第一個(gè)結(jié)點(diǎn)的指針域(nextarc)。由于圖中頂點(diǎn)的排列次序可以不同，每個(gè)頂點(diǎn)的鄰接點(diǎn)的排列順序也可以不同，所以，一個(gè)圖的鄰接表表示不唯一。2．逆鄰接表在圖G的鄰接表中，頂點(diǎn)v的相鄰元素可以通過遍歷該頂點(diǎn)對(duì)應(yīng)的單鏈表求得，設(shè)該鏈表中結(jié)點(diǎn)的個(gè)數(shù)為k那么，G為無向圖時(shí)k表示v的度，G為有向圖時(shí)k表示v的出度。3．鄰接表的存儲(chǔ)表示與實(shí)現(xiàn)(1)鄰接表存儲(chǔ)結(jié)構(gòu)的類型定義定義單鏈表結(jié)點(diǎn)類型ArcNode：struct ArcNode{ int adjvex,weight。int flag。 //定義頭結(jié)點(diǎn)數(shù)組指針vertices int vexnum,arum。int LocateVex_AL(ALGraph G,VType u){ int i。 if(i)return(i+1)。 G,GKind kind){ int i,j,k。 cout輸入頂點(diǎn)數(shù)和邊(弧)數(shù)vexnum arum:。 for(i=0。 //輸入所有頂點(diǎn)的信息到vex中 [i].nextarc=NULL。k。(j=LocateVex_AL(G,v))))。 prweight=0。 if(==UDG||==UDN) //對(duì)于無向圖(或網(wǎng))將結(jié)點(diǎn)pr1插入到第j個(gè)鏈表的首部 { pr1=new ArcNode。 [j].nextarc=pr1。 for(i=0。 while(p) { if(==DG||==UDG) //對(duì)于圖僅輸出頂點(diǎn)的下標(biāo)值 cout39。[39。 p=pnextarc。 GKind gk1=DG,gk2=UDG,gk3=DN,gk4=UDN。 CreateGraph_AL(G2,gk2)。 DisplyAL(G2)。 cout建立一個(gè)無向網(wǎng)的鄰接表G4:\n。 cout無向網(wǎng)G4的鄰接表為:\n。對(duì)于圖，單鏈表中的每一項(xiàng)表示該頂點(diǎn)的鄰接點(diǎn)的下標(biāo)；對(duì)于網(wǎng)，單鏈表中的每一項(xiàng)表示該頂點(diǎn)的鄰接點(diǎn)的下標(biāo)值和相應(yīng)邊（弧）的權(quán)值。其中，頭結(jié)點(diǎn)包含頂點(diǎn)信息域(data)、指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)的指針域(firstin)、指向以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)的指針域(firstout)，表的所有頭結(jié)點(diǎn)以順序存儲(chǔ)。在有向圖的十字鏈表表示中，鏈表的頭結(jié)點(diǎn)之間是順序存儲(chǔ)結(jié)構(gòu)，弧結(jié)點(diǎn)所在的鏈表是非循環(huán)鏈表，結(jié)點(diǎn)之間的相對(duì)位置自然形成，不一定按頂點(diǎn)序列號(hào)有序。 //定義弧尾和弧頭頂點(diǎn)的位置 ArcBox *hlink,*tlink。 //頂點(diǎn)信息 ArcBox *firstin,*firstout。 //有向圖的頂點(diǎn)數(shù)和弧數(shù) GKind kind。 for(i=0。 else return(0)。 G,GKind kind){ int i,j,k。 cout輸入頂點(diǎn)數(shù)和邊(弧)數(shù)vexnum arum:。 for(i=0。 //設(shè)定初始的單鏈表為空 } if(==DG)cout輸入圖中條弧的信息u v:\n。k++) { do{ cinuv。 pr=new ArcBox。 prhlink=[j].firstin。 }//end for}(4)顯示十字鏈表信息的操作函數(shù)void DisplyOLG(OLGraph G)分別按鄰接表和逆鄰接表方式顯示當(dāng)前十字鏈表G的信息。 for(i=0。 while(p) { cout39。pheadvex。 cout] 。 for(i=0。 while(p) { cout39。pheadvex。 cout] 。void main(){ OLGraph G1,G2。 cout建立一個(gè)有向網(wǎng)的十字鏈表G2:\n。 cout有向網(wǎng)G2的信息為:\n。（2）(a)和有向網(wǎng)(b)的十字鏈表的一種表示。這樣，在對(duì)邊進(jìn)行搜索的有關(guān)問題中，同一條邊出現(xiàn)兩次顯然會(huì)帶來一些不便；同時(shí)，當(dāng)圖中的邊數(shù)較大時(shí)明顯增加了內(nèi)存空間的占用量。邊結(jié)點(diǎn)包含判斷該邊是否被掃描過的標(biāo)志域(mark)、該邊依附的第一個(gè)頂點(diǎn)位置域(ivex)、邊依附的第二個(gè)頂點(diǎn)位置域(jvex)、指向下一條依附于ivex的邊的指針域(ilink)、指向下一條依附于jvex的邊的指針域(jlink)、邊的信息（比如權(quán)值）域(info)。鄰接多重鏈表中，表的頭結(jié)點(diǎn)之間是順序存儲(chǔ)結(jié)構(gòu)，邊結(jié)點(diǎn)所在的鏈表是非循環(huán)鏈表，結(jié)點(diǎn)之間的相對(duì)位置也是自然形成的，不一定按頂點(diǎn)序列號(hào)有序。 //訪問標(biāo)志域 int ivex,jvex。struct VexBox{ //頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)定義 VType data。 //鏈表頭結(jié)點(diǎn)數(shù)組指針 int vexnum,edgenum。int LocateVex_AMLG(AMLGraph G,VT