圖的定義和術(shù)語及存儲(chǔ)結(jié)構(gòu)

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：多對(duì)多多對(duì)多（m:n)27.1 7.1 基本術(shù)語基本術(shù)語7.2 7.2 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)7.3 7.3 圖的遍歷圖的遍歷7.4 7.4 圖的連通性圖的連通性7.5 7.5 圖的應(yīng)用圖的應(yīng)用第第7 7章章 圖圖37.1 7.1 圖的基本術(shù)語圖的基本術(shù)語其中：其中：V V 是是G G 的頂點(diǎn)集合，是有窮非空集；的頂點(diǎn)集合，是有窮非空集； VRVR| v,wV | v,wV 且且 P(v,w),P(v,w),是有窮集是有窮集. . 問：問：當(dāng)當(dāng)VR VR 為空時(shí)，圖為空時(shí)，圖G G存在否？存在否？V=vertex 圖：圖：記為記為 Graph( V, VR

2、)E EA AC CB BD D表示從表示從 v v 到到 w w 的一條弧，的一條弧，并稱并稱 w w 為為弧頭弧頭，v v 為為弧尾弧尾。 P(v,w) P(v,w) 定義了弧定義了弧 的意義的意義或信息?；蛐畔?。答：還存在！但此時(shí)圖答：還存在！但此時(shí)圖G G只有頂點(diǎn)。只有頂點(diǎn)。4E EA AC CB BD D例如例如: : G = (V, VR)G = (V, VR)其中其中V=A, B, C, D, EV=A, B, C, D, EVR=, ,VR=, , , , , , , , , , 無向圖：無向圖：由頂點(diǎn)集和邊集構(gòu)成的圖由頂點(diǎn)集和邊集構(gòu)成的圖(“(“邊邊”無方向）無方向）若若 V

3、R VR 必有必有 VR, VR, 則稱則稱 (v,w)(v,w) 為頂點(diǎn)為頂點(diǎn) v v 和頂點(diǎn)和頂點(diǎn) w w 之間存在一條邊。之間存在一條邊。有向圖：有向圖：由頂點(diǎn)集和弧集構(gòu)成的圖由頂點(diǎn)集和弧集構(gòu)成的圖（“弧弧”是有方向的）是有方向的）5BCAFED例如例如: : G=(V,VR)G=(V,VR)其中：其中：V=A, B, C, D, E, FV=A, B, C, D, E, FVR=(A, B), (A, E),VR=(A, B), (A, E), (B, E), (B, E), (C, D), (D, F), (B, F), (C, F) (C, D), (D, F), (B, F),

4、(C, F) v若若 n n 個(gè)頂點(diǎn)的無向圖有個(gè)頂點(diǎn)的無向圖有 n n( (n n-1)/2 -1)/2 條邊條邊, , 稱為稱為無向完全無向完全圖圖v若若 n n 個(gè)頂點(diǎn)的有向圖有個(gè)頂點(diǎn)的有向圖有n n( (n-n-1) 1) 條邊條邊, , 稱為稱為有向完全圖有向完全圖證明：證明：證明：證明：若是有向完全圖，則若是有向完全圖，則n個(gè)頂點(diǎn)中個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)都有一條弧指向其它的每個(gè)頂點(diǎn)都有一條弧指向其它n-1個(gè)個(gè)頂點(diǎn)頂點(diǎn), 因此總邊數(shù)因此總邊數(shù)=n(n-1)12346證明：證明：從從可以直接推論出無向完全圖的可以直接推論出無向完全圖的邊數(shù)邊數(shù)因?yàn)闊o方向，兩弧合并為一邊，因?yàn)闊o方向，兩弧合并為

5、一邊，所以邊數(shù)減半，總邊數(shù)為所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。1234例：判斷下列例：判斷下列4種圖形各屬什么類型？種圖形各屬什么類型？7稀疏圖：稀疏圖：稠密圖：稠密圖： 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 則稱則稱 圖圖G 是是 圖圖G 的子圖。的子圖。子子 圖：圖：邊較少的圖。通常邊數(shù)遠(yuǎn)少于邊較少的圖。通常邊數(shù)遠(yuǎn)少于邊很多的圖。邊很多的圖。無向圖中，邊數(shù)接近無向圖中，邊數(shù)接近有向圖中，邊數(shù)接近有向圖中，邊數(shù)接近BBCABECFABECF例如：例如：8ABECF1597211132有向網(wǎng)有向網(wǎng)或或無向網(wǎng)無向網(wǎng)是弧或邊帶權(quán)的圖是弧或

6、邊帶權(quán)的圖。鄰接點(diǎn)：鄰接點(diǎn)：若邊若邊(v,w) VR，則，則頂點(diǎn)頂點(diǎn)v v 和頂點(diǎn)和頂點(diǎn)w w 互為鄰接點(diǎn)?；猷徑狱c(diǎn)。 邊邊(v,w) (v,w) 依附依附于頂點(diǎn)于頂點(diǎn)v v 和和w w，或者，或者與頂點(diǎn)與頂點(diǎn)v,wv,w相關(guān)聯(lián)相關(guān)聯(lián) 。頂點(diǎn)頂點(diǎn)v v的度：的度：是和是和v v 相關(guān)聯(lián)的邊的數(shù)目相關(guān)聯(lián)的邊的數(shù)目, ,記為記為TD(v)TD(v). .頂點(diǎn)頂點(diǎn)v v的出度的出度: : 以頂點(diǎn)以頂點(diǎn)v v 為尾的弧的數(shù)目為尾的弧的數(shù)目; ;記為記為OD(v)OD(v). .頂點(diǎn)頂點(diǎn)v v的入度的入度: : 以頂點(diǎn)以頂點(diǎn)v v 為頭的弧的數(shù)目為頭的弧的數(shù)目, ,記為記為ID(v)ID(v). .頂

7、點(diǎn)的度頂點(diǎn)的度(TD)=(TD)=出度出度(OD)+(OD)+入度入度(ID)(ID)問：當(dāng)有向圖中僅問：當(dāng)有向圖中僅1 1個(gè)頂點(diǎn)的入個(gè)頂點(diǎn)的入度為度為0,0,其余頂點(diǎn)的入度均其余頂點(diǎn)的入度均為為1 1，此時(shí)是何形狀？，此時(shí)是何形狀？答：是樹！答：是樹！而且是一棵而且是一棵有向樹！有向樹！9路徑路徑: :設(shè)圖設(shè)圖G=(V,VR)G=(V,VR)中的一個(gè)頂點(diǎn)序列中的一個(gè)頂點(diǎn)序列: :v=vv=vi,0 i,0 ,v,vi,1 i,1 , , v, , vi,mi,m=w =w 中，中，(v(vi,j-1 i,j-1 ,v,vi,ji,j) )（或（或 v vi,j-1i,j-1,v,vi,ji,

8、j） VRVR 1jm,1jm,則稱從頂點(diǎn)則稱從頂點(diǎn)v v 到頂?shù)巾旤c(diǎn)點(diǎn)w w 之間存在一條路徑。之間存在一條路徑。路徑長度：路徑長度：路徑上邊路徑上邊（或?。ɑ蚧。┑臄?shù)目。的數(shù)目。ABECF如如: :從從A A到到F F長度為長度為 3 3 的路徑的路徑A,B,C,FA,B,C,F或或AA，E E，C C，F(xiàn)F簡單路徑簡單路徑: :指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單回路簡單回路: :指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。10連通圖：連通圖：無向無向圖圖G G中任意中任意兩

9、個(gè)頂點(diǎn)之間都有路徑相兩個(gè)頂點(diǎn)之間都有路徑相連通。連通。連通分量：連通分量：非連通圖中非連通圖中的極大連通子圖。的極大連通子圖。BACDFEBACDFE強(qiáng)連通圖：強(qiáng)連通圖：在有向圖中在有向圖中, , 每一對(duì)頂點(diǎn)每一對(duì)頂點(diǎn)v vi i和和v vj j, , 都存都存在一條從在一條從v vi i到到v vj j和從和從v vj j到到v vi i的路徑的路徑強(qiáng)連通分量：強(qiáng)連通分量：非強(qiáng)連通非強(qiáng)連通圖中的極大強(qiáng)連通子圖。圖中的極大強(qiáng)連通子圖。ABECFABECF11生成樹：生成樹：v1v2v3v4生成森林：生成森林： 假設(shè)一個(gè)連通圖有假設(shè)一個(gè)連通圖有 n n 個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和 e e 條邊，其中條邊，

10、其中 n-1 n-1 條邊和條邊和 n n 個(gè)個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生該極小連通子圖為此連通圖的生成樹。成樹。由若干棵由若干棵生成樹生成樹組成，含全部頂點(diǎn)，但構(gòu)成組成，含全部頂點(diǎn)，但構(gòu)成這些樹的邊是最少的。（對(duì)有向或無向圖均這些樹的邊是最少的。（對(duì)有向或無向圖均適用）適用）12CreatGraph(&G, V, VR)/按定義按定義(V,VR)(V,VR)構(gòu)造圖構(gòu)造圖DestroyGraph(&G) / / 銷毀圖銷毀圖結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀對(duì)頂點(diǎn)的訪問操作對(duì)頂點(diǎn)的訪問操作LocateVex(G, u) /

11、 / 若若G G中存在頂點(diǎn)中存在頂點(diǎn)u u，則返回該頂點(diǎn)，則返回該頂點(diǎn)在圖中在圖中“位置位置”，否則返回其它信息。，否則返回其它信息。GetVex(G, v) / / 返回返回 v v 的值。的值。PutVex(&G, v, value) / / 對(duì)對(duì) v v 賦值賦值valuevalue。結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作遍歷遍歷插入或刪除弧插入或刪除弧基本操作基本操作對(duì)頂點(diǎn)的訪問操作對(duì)頂點(diǎn)的訪問操作13對(duì)鄰接點(diǎn)的操作對(duì)鄰接點(diǎn)的操作FirstAdjVex(G, v); /返回返回v v的的“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)” ” 若該若該

12、頂點(diǎn)在頂點(diǎn)在G G中沒有鄰接點(diǎn)，則返回中沒有鄰接點(diǎn)，則返回“空空”。NextAdjVex(G, v, w); /返回返回v v的（相對(duì)于的（相對(duì)于w w的）的） “ “下下一個(gè)鄰接點(diǎn)一個(gè)鄰接點(diǎn)”。若。若w w是是v v的最后一個(gè)鄰接點(diǎn)，則返回的最后一個(gè)鄰接點(diǎn)，則返回“空空”。插入或刪除頂點(diǎn)插入或刪除頂點(diǎn)InsertVex(&G, v); /在圖在圖G G中增添新頂點(diǎn)中增添新頂點(diǎn)v v。DeleteVex(&G, v)；/刪除刪除G G中頂點(diǎn)中頂點(diǎn)v v及其相關(guān)的弧。及其相關(guān)的弧。14插入和刪除弧插入和刪除弧InsertArc(&G, v, w); / / 在在G G中增

13、添弧中增添弧，若，若G G是是無向的，則還增添對(duì)稱弧無向的，則還增添對(duì)稱弧。DeleteArc(&G, v, w); /在在G G中刪除弧中刪除弧，若，若G G是是無向的，則還刪除對(duì)稱弧無向的，則還刪除對(duì)稱弧。DFSTraverse(G, v, Visit(); /從頂點(diǎn)從頂點(diǎn)v v起深度優(yōu)先遍歷起深度優(yōu)先遍歷圖圖G G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)VisitVisit一次且僅一次。一次且僅一次。BFSTraverse(G, v, Visit(); /從頂點(diǎn)從頂點(diǎn)v起廣度優(yōu)先遍歷圖起廣度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一次且

14、僅一次。遍遍 歷歷157.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)圖的特點(diǎn)：圖的特點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)： 難！難！ （多個(gè)頂點(diǎn)，無序可言，無法僅以（多個(gè)頂點(diǎn)，無序可言，無法僅以頂點(diǎn)坐標(biāo)表達(dá)相互關(guān)系）頂點(diǎn)坐標(biāo)表達(dá)相互關(guān)系）可用可用多重鏈表多重鏈表但可但可用用數(shù)組數(shù)組描述元素間關(guān)系。描述元素間關(guān)系。非線性結(jié)構(gòu)非線性結(jié)構(gòu)（m :nm :n）鄰接矩陣鄰接矩陣鄰接表鄰接表十字鏈表十字鏈表鄰接多重表鄰接多重表各種表示法成立的原各種表示法成立的原則：存入電腦后能唯則：存入電腦后能唯一復(fù)原一復(fù)原16 建立一個(gè)建立一個(gè)頂點(diǎn)表頂點(diǎn)表和一個(gè)和一個(gè)鄰接矩陣鄰接矩陣。 , ),( ,

15、,.否否則則或或者者如如果果01AEjiEjijiarcs記錄各個(gè)頂點(diǎn)信息記錄各個(gè)頂點(diǎn)信息表示各個(gè)頂點(diǎn)之間關(guān)系表示各個(gè)頂點(diǎn)之間關(guān)系 設(shè)圖設(shè)圖 A = (A = (V V, , E E ) ) 有有 n n 個(gè)頂點(diǎn)，則圖的鄰接個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組矩陣是一個(gè)二維數(shù)組 A A.arcs.arcs n nn n ，定義為：，定義為：17鄰接矩陣：鄰接矩陣：A.arcs =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點(diǎn)表：頂點(diǎn)表：無向圖的鄰接矩陣如何表示？無向圖的鄰接矩陣如何表示？v1

16、v2v3v5v4v418例例2 2 ：有向圖的鄰接矩陣如何表示？：有向圖的鄰接矩陣如何表示？有向圖的鄰接矩陣可能是不對(duì)稱的。有向圖的鄰接矩陣可能是不對(duì)稱的。頂點(diǎn)頂點(diǎn)v vi i的出度的出度= =第第i i行元素之和行元素之和; ; 頂點(diǎn)頂點(diǎn)v vi i的入度的入度= =第第i i列元素之和列元素之和; ; 頂點(diǎn)的度頂點(diǎn)的度= =第第i i行元素之和行元素之和+ +第第i i列元素之和。列元素之和。v1v2v3v4鄰接矩陣：鄰接矩陣：A.arcs =( v1 v2 v3 v4 )v1v2v3v4在有向圖的鄰接矩陣中，在有向圖的鄰接矩陣中， 第第i i行含義：以結(jié)點(diǎn)行含義：以結(jié)點(diǎn)v vi i為尾的

17、弧為尾的弧( (即出度邊）；即出度邊）； 第第j j列含義：以結(jié)點(diǎn)列含義：以結(jié)點(diǎn)v vj j為頭的弧為頭的弧( (即入度邊）。即入度邊）。頂點(diǎn)表：頂點(diǎn)表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 19例例3 3 ： 有權(quán)圖（即網(wǎng)絡(luò)）的鄰接矩陣如何表示？有權(quán)圖（即網(wǎng)絡(luò)）的鄰接矩陣如何表示？定義：定義：A.arcs i j =Wij 或（或（vi, vj）VR 反之反之v1v2v3v4Nv5v65489755613鄰接矩陣：鄰接矩陣： N.arcs =(v1 v2 v3 v4 v5 v6)頂點(diǎn)表：頂點(diǎn)表： 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v620 容

18、易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。點(diǎn)的鄰接點(diǎn)等等。 n n個(gè)頂點(diǎn)需要個(gè)頂點(diǎn)需要個(gè)單元存儲(chǔ)邊個(gè)單元存儲(chǔ)邊( (弧弧););空間效率為空間效率為O(O(n n ) )。鄰接矩陣法鄰接矩陣法優(yōu)點(diǎn)：優(yōu)點(diǎn)：鄰接矩陣法鄰接矩陣法缺點(diǎn)：缺點(diǎn)：對(duì)稀疏圖而言尤對(duì)稀疏圖而言尤其浪費(fèi)空間。其浪費(fèi)空間。圖的鄰接矩陣在機(jī)內(nèi)如何表示？圖的鄰接矩陣在機(jī)內(nèi)如何表示？ （參見教材（參見教材P161P161）注：注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#define INFINITY

19、 INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)假設(shè)的最大頂點(diǎn)數(shù)typedef enum DG, DN, UDG,UDN GraphKind; /有向圖，有向網(wǎng)，無向圖，無向網(wǎng)有向圖，有向網(wǎng)，無向圖，無向網(wǎng) 21typedef struct ArcCell / / 弧的定義弧的定義 VRType adj; / VRType/ VRType是頂點(diǎn)關(guān)系類型。是頂點(diǎn)關(guān)系類型。/對(duì)無權(quán)圖對(duì)無權(quán)圖, ,用用1 1或或0 0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。 InfoType *info; / / 該弧相關(guān)該弧相關(guān)信

20、息的指針信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct / / 圖的定義圖的定義 VertexType vexsMAX_VERTEX_NUM; / / 頂點(diǎn)向量頂點(diǎn)向量 AdjMatrix arcs; / / 鄰接矩陣鄰接矩陣 int vexnum, arcnum; / / 頂點(diǎn)數(shù)，弧數(shù)頂點(diǎn)數(shù)，弧數(shù) GraphKind kind; / / 圖的種類標(biāo)志圖的種類標(biāo)志 MGraph;22adjvexnextarcinfodatafirstarc鄰接點(diǎn)域，鄰接點(diǎn)域，表示表示v vi i 鄰接鄰接點(diǎn)的位置點(diǎn)的位置

21、鏈域，鏈域，指向指向下一條邊或下一條邊或弧的結(jié)點(diǎn)弧的結(jié)點(diǎn)數(shù)據(jù)域，數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)存儲(chǔ)頂點(diǎn)v vi i 信息信息鏈域，鏈域，指向指向單鏈表的第單鏈表的第一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)邊或弧的信息邊或弧的信息23例例1 1：無向圖的鄰接表如何表示？：無向圖的鄰接表如何表示？v1v2v3v5v4v4鄰接表：鄰接表：0123413341420請(qǐng)注意：鄰接表不唯一！請(qǐng)注意：鄰接表不唯一！因各個(gè)邊結(jié)點(diǎn)的鏈入順序因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。是任意的。v1v2v3v4v5231420v v1 1鄰接點(diǎn)鄰接點(diǎn)v v4 4的位置的位置此無權(quán)圖未開此無權(quán)圖未開第第3 3分量分量TD(Vi)=單鏈表中單鏈表中V Vi i鏈接的

22、結(jié)點(diǎn)個(gè)數(shù)鏈接的結(jié)點(diǎn)個(gè)數(shù)24例例2 2：有向圖的鄰接表如何表示？：有向圖的鄰接表如何表示？v1v2v3v4V4V3V2V12301鄰接表鄰接表( (出邊出邊) )V4V3V2V13020逆鄰接表逆鄰接表( (入邊入邊) )01230123在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。OD(Vi)=鄰接表中鄰接表中Vi鏈接的結(jié)點(diǎn)數(shù)鏈接的結(jié)點(diǎn)數(shù)ID(Vi)=逆鄰接表中逆鄰接表中Vi i鏈接的結(jié)點(diǎn)數(shù)鏈接的結(jié)點(diǎn)數(shù)TD(Vi) = OD( Vi ) + ID( Vi )25例例3 3：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。8

23、064125當(dāng)鄰接表的當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形存儲(chǔ)結(jié)構(gòu)形成后，圖便成后，圖便唯一確定！唯一確定！26分析分析1：對(duì)于對(duì)于n n個(gè)頂點(diǎn)個(gè)頂點(diǎn)e e條邊的無向圖，鄰接表中除了條邊的無向圖，鄰接表中除了n n個(gè)頭結(jié)點(diǎn)外，只有個(gè)頭結(jié)點(diǎn)外，只有2e2e個(gè)表結(jié)點(diǎn)個(gè)表結(jié)點(diǎn), ,空間效率為空間效率為O(n+2e)O(n+2e)。若是稀疏圖若是稀疏圖(en(en2 2) )，則比鄰接矩陣表示法，則比鄰接矩陣表示法O(nO(n2 2) )省空省空間。間。鄰接表存儲(chǔ)法的特點(diǎn)：鄰接表存儲(chǔ)法的特點(diǎn)：分析分析2:2:在有向圖中，鄰接表中除了在有向圖中，鄰接表中除了n n個(gè)頭結(jié)點(diǎn)外，只個(gè)頭結(jié)點(diǎn)外，只有有e e個(gè)表結(jié)點(diǎn)個(gè)表結(jié)點(diǎn),

24、 ,空間效率為空間效率為O(n+e)O(n+e)。若是稀疏圖，則比。若是稀疏圖，則比鄰接矩陣表示法合適。鄰接矩陣表示法合適。它其實(shí)是對(duì)鄰接矩陣法的一種它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)，兩個(gè)結(jié)點(diǎn)表示一條邊或弧改進(jìn)，兩個(gè)結(jié)點(diǎn)表示一條邊或弧鄰接表的鄰接表的缺點(diǎn)：缺點(diǎn)：鄰接表的鄰接表的優(yōu)點(diǎn)：優(yōu)點(diǎn)： 空間效率高；空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒有鄰接矩陣兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒有鄰接矩陣方便。方便。27討論：鄰接表與鄰接矩陣有什么異同之處？討論：鄰接表與鄰接矩陣有什么異同之處？1. 1. 聯(lián)系：聯(lián)系

25、：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2. 2. 區(qū)別：區(qū)別： 對(duì)于任一確定的無向圖，鄰接矩陣是唯一的（行列對(duì)于任一確定的無向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一鄰接表不唯一（鏈接次序（鏈接次序與頂點(diǎn)編號(hào)無關(guān)）。與頂點(diǎn)編號(hào)無關(guān)）。 鄰接矩陣的空間復(fù)雜度為鄰接矩陣的空間復(fù)雜度為O(nO(n2 2),),而鄰接表的空間復(fù)而鄰接表的空間復(fù)雜度為雜度為O(n+e)O(n+e)。3. 3. 用途：用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（鄰接矩

26、陣多用于稠密圖的存儲(chǔ)（e e接近接近n(n-1)/2)n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（而鄰接表多用于稀疏圖的存儲(chǔ)（enen2 2) )28圖的鄰接表在機(jī)內(nèi)如何表示？圖的鄰接表在機(jī)內(nèi)如何表示？ （參見教材（參見教材P163P163）#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)假設(shè)的最大頂點(diǎn)數(shù)Typedef struct ArcNode /弧結(jié)構(gòu)弧結(jié)構(gòu) int adjvex; /該弧所指向的頂點(diǎn)位置該弧所指向的頂點(diǎn)位置 struct ArcNode *nextarcs; /指向下一條弧的指針指向下一條弧的指針 InfoArc *info; /該弧相關(guān)信息的

27、指針該弧相關(guān)信息的指針 ArcNode；29Typedef struct /圖結(jié)構(gòu)圖結(jié)構(gòu) AdjList vertics ; /應(yīng)包含鄰接表應(yīng)包含鄰接表 int vexnum, arcnum; /應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù)應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù) int kind; /還應(yīng)說明圖的種類（用標(biāo)志）還應(yīng)說明圖的種類（用標(biāo)志）ALGraph; Typedef struct VNode /頂點(diǎn)結(jié)構(gòu)頂點(diǎn)結(jié)構(gòu) VertexType data; /頂點(diǎn)信息頂點(diǎn)信息 ArcNode * firstarc; /指向第一條依附該頂點(diǎn)指向第一條依附該頂點(diǎn)的弧的指針的弧的指針VNode, AdjList MAX_VERTE

28、X_NUM ; /鄰接表鄰接表 30 它是它是有向圖有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 思路：思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。的結(jié)合。(1)(1)開設(shè)弧結(jié)點(diǎn)，設(shè)開設(shè)弧結(jié)點(diǎn)，設(shè)5 5個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素）個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素）(2)(2)開設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)開設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)3 3個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）元素）tailvex headvex hlinktlinkinfo弧結(jié)點(diǎn)弧結(jié)點(diǎn)tailvex: 弧尾頂點(diǎn)位置弧尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置弧頭頂點(diǎn)位置hlink: 弧頭相同的下一弧位置弧頭相同的下一弧位置tlink: 弧尾相同的下一弧位置弧尾相同的下一弧位置info: 弧信息弧信息31 data : 頂點(diǎn)信息頂點(diǎn)信息firstin : 以頂點(diǎn)為弧頭的第以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)一條弧結(jié)點(diǎn)firstout: 以頂點(diǎn)為弧尾的第以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)一條弧結(jié)點(diǎn)問：問：n n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)data firstinfirstout頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)十字鏈表優(yōu)點(diǎn)：十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等。容易操作，如求頂