【文章內容簡介】 AL(G3)。 cout無向網(wǎng)G4的鄰接表為:\n。 DisplyAL(G4)。}程序運行演示結果為：建立一個有向圖的鄰接表G1:輸入頂點數(shù)和邊(弧)數(shù)vexnum arum:6 8↙按某種順序輸入6個頂點的值:1 2 3 4 5 6↙輸入圖中8條邊(弧)的信息u v:1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5↙建立一個無向圖的鄰接表G2:輸入頂點數(shù)和邊(弧)數(shù)vexnum arum:6 7↙按某種順序輸入6個頂點的值:1 2 3 4 5 6↙輸入圖中7條邊(弧)的信息u v:1 2 1 4 2 3 2 6 5 3 5 6 5 4↙有向圖G1的鄰接表為:0 (1): [3] [1]1 (2):2 (3): [5] [0]3 (4): [2]4 (5): [3]5 (6): [4] [0]無向圖G2的鄰接表為:0 (1): [3] [1]1 (2): [5] [2] [0]2 (3): [4] [1]3 (4): [4] [0]4 (5): [3] [5] [2]5 (6): [4] [1]***************************************建立一個有向網(wǎng)的鄰接表G3:輸入頂點數(shù)和邊(弧)數(shù)vexnum arum:4 4↙按某種順序輸入4個頂點的值:1 2 3 4↙輸入圖中4條邊(弧)和權的信息u v w:1 2 7 1 3 1 3 4 5 4 1 9↙建立一個無向網(wǎng)的鄰接表G4:輸入頂點數(shù)和邊(弧)數(shù)vexnum arum:5 5↙按某種順序輸入5個頂點的值:1 2 3 4 5↙輸入圖中5條邊(弧)和權的信息u v w:1 2 9 4 1 8 4 2 3 4 5 1 3 5 12↙有向網(wǎng)G3的鄰接表為:0 (1): [2,1] [1,7]1 (2):2 (3): [3,5]3 (4): [0,9]無向網(wǎng)G4的鄰接表為:0 (1): [3,8] [1,9]1 (2): [3,3] [0,9]2 (3): [4,12]3 (4): [4,1] [1,3] [0,8]4 (5): [2,12] [3,1]說明：（1）、：、。（2）在程序顯示的結果中，第一列為頂點的下標，第二列為圖中所有頂點的值。對于圖，單鏈表中的每一項表示該頂點的鄰接點的下標；對于網(wǎng)，單鏈表中的每一項表示該頂點的鄰接點的下標值和相應邊（?。┑臋嘀怠＃?）在建立鄰接表時，由于輸入的是頂點信息，所以要先通過查找求得該頂點在圖中的位置，再將相應結點插入到對應單鏈表的首部，所以，該操作的時間復雜度為O(n*e)。十字鏈表是有向圖的另一種鏈式存儲結構，該方法是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。1．十字鏈表的定義類似鄰接表，在十字鏈表中包含鏈表的頭結點和弧結點兩種類型的結點。其中，頭結點包含頂點信息域(data)、指向以該頂點為弧頭的第一個弧結點的指針域(firstin)、指向以該頂點為弧尾的第一個弧結點的指針域(firstout)，表的所有頭結點以順序存儲。弧結點包含表示弧尾頂點下標的尾域(tailvex)、表示弧頭頂點下標的頭域(headvex)、指向弧頭相同的下一條弧的指針域(hlink)、指向弧尾相同的下一條弧的指針域(tlink)、弧的信息（如權值）域(info)。例如。如果將有向圖的鄰接矩陣看成是稀疏矩陣的話，則十字鏈表也可以看成是鄰接矩陣的十字鏈表存儲結構。在有向圖的十字鏈表表示中，鏈表的頭結點之間是順序存儲結構，弧結點所在的鏈表是非循環(huán)鏈表，結點之間的相對位置自然形成，不一定按頂點序列號有序。由此可見，有向圖的十字鏈表表示方式是不唯一的。2．十字鏈表的存儲表示與實現(xiàn)(1)十字鏈表存儲結構的類型定義下面分別給出十字鏈弧結點(ArcBox)、頂點結點(OLVexNode)、十字鏈表(OLGraph)的類型定義。struct ArcBox{ //弧結點的結構定義 int tailvex,headvex。 //定義弧尾和弧頭頂點的位置 ArcBox *hlink,*tlink。 //弧頭相同、弧尾相同的弧的鏈域 int weight。 //定義有向網(wǎng)中弧的權值}。struct OLVexNode{ //頂點結點結構定義 VType data。 //頂點信息 ArcBox *firstin,*firstout。 //分別指向頂點的第一條入弧和出弧}。struct OLGraph{ //定義十字鏈表類型 OLVexNode *xlist。 //鏈表頭結點數(shù)組指針 int vexnum,arum。 //有向圖的頂點數(shù)和弧數(shù) GKind kind。}。(2)十字鏈表的查找操作函數(shù)int LocateVex_OLG(OLGraph G,VType u) 返回頂點u在圖G中的位置，如果查找失敗則返回0值。int LocateVex_OLG(OLGraph G,VType u) { int i。 for(i=0。i。i++) if([i].data==u)break。 if(i)return(i+1)。 else return(0)。}(3)建立十字鏈表的算法實現(xiàn)函數(shù)void CreateGraph_OLG(OLGraphamp。 G,GKind kind)根據(jù)圖的類型kind建立一個有向圖或有向網(wǎng)的十字鏈表G。void CreateGraph_OLG(OLGraphamp。 G,GKind kind){ int i,j,k。 VType u,v。 ArcBox* pr。 =kind。 cout輸入頂點數(shù)和邊(弧)數(shù)vexnum arum:。 cin。 =new OLVexNode[]。 //為頂點數(shù)組分配內存空間 cout按某種順序輸入個頂點的值:\n。 for(i=0。i。i++) { cin[i].data。 //輸入所有頂點的信息到data中 [i].firstin=[i].firstout=NULL。 //設定初始的單鏈表為空 } if(==DG)cout輸入圖中條弧的信息u v:\n。 else cout輸入圖中條弧和權的信息u v w:\n。 for(k=0。k。k++) { do{ cinuv。 } while(!((i=LocateVex_OLG(G,u))amp。amp。(j=LocateVex_OLG(G,v))))。 pr=new ArcBox。 //動態(tài)分配弧存儲空間 prtailvex=i。 //i從位置值轉換為下標值 prheadvex=j。 //j從位置值轉換為下標值 if(==DN)cinprweight。 prhlink=[j].firstin。 //將輸入的弧插入到相應鏈表的首部 [j].firstin=pr。 prtlink=[i].firstout。 [i].firstout=pr。 }//end for}(4)顯示十字鏈表信息的操作函數(shù)void DisplyOLG(OLGraph G)分別按鄰接表和逆鄰接表方式顯示當前十字鏈表G的信息。void DisplyOLG(OLGraph G){ int i。 ArcBox* p。 cout按鄰接表顯示結果為：\n。 for(i=0。i。i++) { p=[i].firstout。 couti ([i].data): 。 while(p) { cout39。[39。ptailvex39。 39。pheadvex。 if(==DN)cout39。 39。pweight。 cout] 。 p=ptlink。 } coutendl。 }//end for cout按逆鄰接表顯示結果為：\n。 for(i=0。i。i++) { p=[i].firstin。 couti ([i].data): 。 while(p) { cout39。[39。ptailvex39。 39。pheadvex。 if(==DN)cout39。 39。pweight。 cout] 。 p=phlink。 } coutendl。 }//end for}(5)程序演示主程序代碼程序中分別建立一個有向圖G1和一個有向網(wǎng)G2的十字鏈表，并按鄰接表和逆鄰接表兩種形式顯示所建立的的十字鏈表的內容。void main(){ OLGraph G1,G2。 GKind gk1=DG,gk2=DN。 cout建立一個有向圖的十字鏈表G1:\n。 CreateGraph_OLG(G1,gk1)。 cout建立一個有向網(wǎng)的十字鏈表G2:\n。 CreateGraph_OLG(G2,gk2)。 cout有向圖G1的信息為:\n。 DisplyOLG(G1)。 cout有向網(wǎng)G2的信息為:\n。 DisplyOLG(G2)。}程序運行演示結構為：建立一個有向圖的十字鏈表G1:輸入頂點數(shù)和邊(弧)數(shù)vexnum arum:4 7↙按某種順序輸入4個頂點的值:1 2 3 4↙輸入圖中7條弧的信息u v:1 2 1 3 3 1 3 4 4 1 4 2 4 3↙建立一個有向網(wǎng)的十字鏈表G2:輸入頂點數(shù)和邊(弧)數(shù)vexnum arum:4 7↙按某種順序輸入4個頂點的值:1 2 3 4↙輸入圖中7條弧和權的信息u v w:1 2 8 1 3 5 3 1 2 3 4 4 4 1 6 4 2 7 4 3 3↙有向圖G1的信息為:按鄰接表顯示結果為：0 (1): [0 2] [0 1]1 (2):2 (3): [2 3] [2 0]3 (4): [3 2] [3 1] [3 0]按逆鄰接表顯示結果為：0 (1): [3 0] [2 0]1 (2): [3 1] [0 1]2 (3): [3 2] [0 2]3 (4): [2 3]有向網(wǎng)G2的信息為:按鄰接表顯示結果為：0 (1): [0 2 5] [0 1 8]1 (2):2 (3): [2 3 4] [2 0 2]3 (4): [3 2 3] [3 1 7] [3 0 6]按逆鄰接表顯示結果為：0 (1): [3 0 6] [2 0 2]1 (2): [3 1 7] [0 1 8]2 (3): [3 2 3] [0 2 5]3 (4): [2 3 4]說明：（1）在程序顯示的結果中，第一列、第二列分別為頂點位置的下標和頂點的值。對于圖，單鏈表中的每一項表示該頂點及其鄰接點的下標；對于網(wǎng)，還要顯示相應弧的權值。（2）(a)和有向網(wǎng)(b)的十字鏈表的一種表示。（3）從存儲結構可以看出，在十字鏈表中很容易算出一個頂點的出度和入度，并且建立十字鏈表的時間復雜度與建立鄰接表的時間復雜度相同，均為O(n*e)。所以在有向圖的應用中，十字鏈表是一個很有用的工具。在無向圖的鄰接表表示中，每一條邊(v,w)均出現(xiàn)兩次，即在頂點v的單鏈表中有頂點v、w構成的邊結點，同時在頂點w的單鏈表中有頂點w、v構成的邊結點。這樣，在對邊進行搜索的有關問題中，同一條邊出現(xiàn)兩次顯然會帶來一些不便；同時，當圖中的邊數(shù)較大時明顯增加了內存空間的占用量。為此，下面給出無向圖的鄰接多重鏈表表示法。1．鄰接多重表的定義在鄰接多重表中包含鏈表的頭結點和鏈表中的邊結點兩種類型的結點。其中，頭結點包含頂點信息域(data)、指向依附于該頂點的第一條邊結點的指針域(firstedge)。邊結點包含判斷該邊是否被掃描過的標志域(mark)、該邊依附的第一個頂點位置域(ivex)、邊依附的第二個頂點位置域(jvex)、指向下一條依附于ivex的邊的指針域(ilink)、指向下一條依附于jvex的邊的指針域(jlink)、邊的信息（比如權值）域(info)。例如。在鄰接多重表中，所有依附于同一頂點的邊鏈接在一個鏈表中，由于一條邊依附于兩個頂點，所以每個邊結點同時出現(xiàn)在兩個鏈表中。所以，無向圖的鄰接多重表中邊結點的個數(shù)是其鄰接表表示中邊結點個數(shù)的一半。鄰接多重鏈表中，表的頭結點之間是順序存儲結構，邊結點所在的鏈表是非循環(huán)鏈表，結點之間的相對位置也是自然形成的，不一定按頂點序列號有序。所以，無向圖的鄰接多重表表示方式是不唯一的。2．鄰接多重表的存儲表