圖圖的定義和存儲

圖圖的定義和存儲第一頁，共二十一頁，2022年，8月28日圖的定義：

圖G是由頂點集V和頂點間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組定義為：G=（V,E）。例如，對于圖7-1所示的無向圖G1和有向圖G2，它們的數(shù)據(jù)結(jié)構(gòu)可以描述為：G1=(V1,E1),其中V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而G2=(V2,E2)，其中V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}。7.1圖的基本概念第二頁，共二十一頁，2022年，8月28日7.2圖的存貯結(jié)構(gòu)圖無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間關(guān)系，即圖沒有順序映象的存儲結(jié)構(gòu)。用多重鏈表表示圖，即以一個數(shù)據(jù)域和多個指針域組成的結(jié)點表示圖中一個頂點，其中數(shù)據(jù)域存儲該頂點的信息，指針域存儲指向其鄰接點的指針。常用的有鄰接矩陣、鄰接表和十字鏈表等。不管哪一種方式，它除了要存儲圖中各個頂點本身的信息外，同時還要存儲頂點與頂點之間的所有關(guān)系（邊的信息）。第三頁，共二十一頁，2022年，8月28日多重鏈表例G12413例15324G2V1V2^^V4^V3^

^V1

V2

V4^

V5^

V3第四頁，共二十一頁，2022年，8月28日1．圖的鄰接矩陣表示在鄰接矩陣表示中，除了存放頂點本身信息外，還用一個矩陣表示各個頂點之間的關(guān)系。若（i,j）∈E(G)或〈i,j〉∈E(G),則矩陣中第i行第j列元素值為1，否則為0。圖的鄰接矩陣定義為：

1若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=0其它情形7.2.1鄰接矩陣第五頁，共二十一頁，2022年，8月28日例如,對圖7-8所示的無向圖和有向圖的鄰接矩陣。第六頁，共二十一頁，2022年，8月28日2．從無向圖的鄰接矩陣可以得出如下結(jié)論

（1）矩陣是對稱的，可壓縮存儲（上（下）三角）;（2）第i行或第i列中1的個數(shù)為頂點i的度;（3）矩陣中1的個數(shù)的一半為圖中邊的數(shù)目;（4）很容易判斷頂點i和頂點j之間是否有邊相連(看矩陣中i行j列值是否為1)。3．從有向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣不一定是對稱的;（2）第i行中1的個數(shù)為頂點i的出度;（3）第i列中1的個數(shù)為頂點i的入度;（4）矩陣中1的個數(shù)為圖中弧的數(shù)目;（5）很容易判斷頂點i和頂點j是否有弧相連.第七頁，共二十一頁，2022年，8月28日4．網(wǎng)的鄰接矩陣表示類似地可以定義網(wǎng)的鄰接矩陣為：

wij

若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=∞其它情形網(wǎng)及網(wǎng)的鄰接矩陣見下圖。第八頁，共二十一頁，2022年，8月28日鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費空間。第九頁，共二十一頁，2022年，8月28日1．圖的鄰接表表示圖的鄰接表存儲方法是一種順序分配與鏈式分配相結(jié)合的存儲方法，它包括兩部分：一部分是單鏈表，用來存放邊的信息；另一部分是數(shù)組，主要用來存放頂點本身的數(shù)據(jù)信息。adjvexweightnext邊結(jié)點頂點結(jié)點7.2.2鄰接表第十頁，共二十一頁，2022年，8月28日左圖所示的無向圖G3和有向圖G4的鄰接表見右圖所示:第十一頁，共二十一頁，2022年，8月28日2．從無向圖的鄰接表可以得到如下結(jié)論

（1）第i個鏈表中結(jié)點數(shù)目為頂點i的度；（2）所有鏈表中結(jié)點數(shù)目的一半為圖中邊數(shù)；（3）占用的存儲單元數(shù)目為n+2e。3．從有向圖的鄰接表可以得到如下結(jié)論（1）第i個鏈表中結(jié)點數(shù)目為頂點i的出度；（2）所有鏈表中結(jié)點數(shù)目為圖中弧數(shù)；（3）占用的存儲單元數(shù)目為n+e。從有向圖的鄰接表可知，不能求出頂點的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一個頂點的入度。第十二頁，共二十一頁，2022年，8月28日例：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。8064125當鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！第十三頁，共二十一頁，2022年，8月28日鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。第十四頁，共二十一頁，2022年，8月28日4．圖的鄰接表數(shù)據(jù)類型描述圖的鄰接表數(shù)據(jù)類型描述如下：#defineMAXN50/*MAXN表示圖中最大頂點數(shù)*/typedefstructe_node//定義邊結(jié)點的結(jié)構(gòu){intadjvex;intweight;structe_node*next;}E_NODE;typedefstructv_node//定義鄰接表的表頭類型{intvertex;//頂點信息

E_NODE*link;}V_NODE;V_NODEhead[MAXN];第十五頁，共二十一頁，2022年，8月28日討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（e<<n2)第十六頁，共二十一頁，2022年，8月28日有向圖的十字鏈表表示法弧結(jié)點：typedefstructarcnode{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置structarcnode*hlink；//指向弧頭相同的下一條弧structarcnode*tlink;//指向弧尾相同的下一條弧}AD;tailvexheadvexhlinktlink頂點結(jié)點：typedefstructdnode{intdata;//存與頂點有關(guān)信息structarcnode*firstin；//指向以該頂點為弧頭的第一個弧結(jié)點structarcnode*firstout;//指向以該頂點為弧尾的第一個弧結(jié)點}DD;DDg[M];//g[0]不用datafirstinfirstout第十七頁，共二十一頁，2022年，8月28日例bdacabcd1234

13

12

34

31

43

42

41^^^^^^^^第十八頁，共二十一頁，2022年，8月28日無向圖的鄰接多重表表示法頂點結(jié)點：typedefstructdnode{intdata;//存與頂點有關(guān)的信息structnode*firstedge;//指向第一條依附于該頂點的邊}DD;DDga[M];//ga[0]不用datafirstedge邊結(jié)點：typedefstructnode{intmark;//標志域

intivex,jvex;//該邊依附的兩個頂點在表頭數(shù)組中位置

structnode*ilink,*jlink;//分別指向依附于ivex和jvex的下一條邊}JD;markivexilinkjvexjlink第十九頁，共二十一頁，2022年，8月28日例aecbd1234acdb5e

12

14

34