數(shù)據(jù)結(jié)構(gòu)第7章圖1-圖的定義和存儲(chǔ) 課件.ppt

《數(shù)據(jù)結(jié)構(gòu)第7章圖1-圖的定義和存儲(chǔ) 課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第7章圖數(shù)據(jù)結(jié)構(gòu)講義-圖的定義和存儲(chǔ)圖的定義：圖G是由頂點(diǎn)集V和頂點(diǎn)間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組定義為：G=（V,E）。例如，對(duì)于圖7-1所示的無(wú)向圖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圖的基本概念7.2圖的存貯結(jié)構(gòu)圖無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示

2、元素之間關(guān)系，即圖沒(méi)有順序映象的存儲(chǔ)結(jié)構(gòu)。用多重鏈表表示圖，即以一個(gè)數(shù)據(jù)域和多個(gè)指針域組成的結(jié)點(diǎn)表示圖中一個(gè)頂點(diǎn)，其中數(shù)據(jù)域存儲(chǔ)該頂點(diǎn)的信息，指針域存儲(chǔ)指向其鄰接點(diǎn)的指針。常用的有鄰接矩陣、鄰接表和十字鏈表等。不管哪一種方式，它除了要存儲(chǔ)圖中各個(gè)頂點(diǎn)本身的信息外，同時(shí)還要存儲(chǔ)頂點(diǎn)與頂點(diǎn)之間的所有關(guān)系（邊的信息）。多重鏈表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V31．圖的鄰接矩陣表示在鄰接矩陣表示中，除了存放頂點(diǎn)本身信息外，還用一個(gè)矩陣表示各個(gè)頂點(diǎn)之間的關(guān)系。若（i,j）∈E(G)或〈i,j

3、〉∈E(G),則矩陣中第i行第j列元素值為1，否則為0。圖的鄰接矩陣定義為：1若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=0其它情形7.2.1鄰接矩陣?yán)?對(duì)圖7-8所示的無(wú)向圖和有向圖的鄰接矩陣。2．從無(wú)向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣是對(duì)稱的，可壓縮存儲(chǔ)（上（下）三角）;（2）第i行或第i列中1的個(gè)數(shù)為頂點(diǎn)i的度;（3）矩陣中1的個(gè)數(shù)的一半為圖中邊的數(shù)目;（4）很容易判斷頂點(diǎn)i和頂點(diǎn)j之間是否有邊相連(看矩陣中i行j列值是否為1)。3．從有向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣不一定是對(duì)稱的;（2

4、）第i行中1的個(gè)數(shù)為頂點(diǎn)i的出度;（3）第i列中1的個(gè)數(shù)為頂點(diǎn)i的入度;（4）矩陣中1的個(gè)數(shù)為圖中弧的數(shù)目;（5）很容易判斷頂點(diǎn)i和頂點(diǎn)j是否有弧相連.4．網(wǎng)的鄰接矩陣表示類似地可以定義網(wǎng)的鄰接矩陣為：wij若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=∞其它情形網(wǎng)及網(wǎng)的鄰接矩陣見(jiàn)下圖。鄰接矩陣法優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。鄰接矩陣法缺點(diǎn)：n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。對(duì)稀疏圖而言尤其浪費(fèi)空間。1．圖的鄰接表表示圖的鄰接表

5、存儲(chǔ)方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)方法，它包括兩部分：一部分是單鏈表，用來(lái)存放邊的信息；另一部分是數(shù)組，主要用來(lái)存放頂點(diǎn)本身的數(shù)據(jù)信息。adjvexweightnext邊結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)7.2.2鄰接表左圖所示的無(wú)向圖G3和有向圖G4的鄰接表見(jiàn)右圖所示:2．從無(wú)向圖的鄰接表可以得到如下結(jié)論（1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的度；（2）所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)；（3）占用的存儲(chǔ)單元數(shù)目為n+2e。3．從有向圖的鄰接表可以得到如下結(jié)論（1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的出度；（2）所有鏈表中結(jié)點(diǎn)數(shù)目為圖中弧數(shù)；（3

6、）占用的存儲(chǔ)單元數(shù)目為n+e。從有向圖的鄰接表可知，不能求出頂點(diǎn)的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一個(gè)頂點(diǎn)的入度。例：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。8064125當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；鄰接表的缺點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。4．圖的鄰接表數(shù)據(jù)類型描述圖的鄰接表數(shù)據(jù)類型描述如下：#defineMAXN50/*MAXN表示圖中最大頂點(diǎn)數(shù)*/typedefstructe_node//定義邊結(jié)

7、點(diǎn)的結(jié)構(gòu){intadjvex;intweight;structe_node*next;}E_NODE;typedefstructv_node//定義鄰接表的表頭類型{intvertex;//頂點(diǎn)信息E_NODE*link;}V_NODE;V_NODEhead[MAXN];討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.區(qū)別：①對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。②鄰接矩陣的空

8、間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（e<