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

1、1,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：,多對(duì)多 （m:n),2,7.1 基本術(shù)語(yǔ) 7.2 存儲(chǔ)結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性 7.5 圖的應(yīng)用,第7章 圖,3,7.1 圖的基本術(shù)語(yǔ),其中：V 是G 的頂點(diǎn)集合，是有窮非空集； VR| v,wV 且 P(v,w),是有窮集.,問(wèn)：當(dāng)VR 為空時(shí)，圖G存在否？,V=vertex,圖：記為 Graph( V, VR ),表示從 v 到 w 的一條弧，并稱 w 為弧頭，v 為弧尾。 P(v,w) 定義了弧 的意義或信息。,答：還存在！但此時(shí)圖G只有頂點(diǎn)。,4,例如:,G = (V, VR),其中 V=A, B, C, D, E VR=, , , , ,

2、, ,無(wú)向圖：由頂點(diǎn)集和邊集構(gòu)成的圖(“邊”無(wú)方向）,若VR 必有VR, 則稱 (v,w) 為頂點(diǎn) v 和頂點(diǎn) w 之間存在一條邊。,有向圖：由頂點(diǎn)集和弧集構(gòu)成的圖（“弧”是有方向的）,5,例如: G=(V,VR) 其中： V=A, B, C, D, E, F VR=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) ,若 n 個(gè)頂點(diǎn)的無(wú)向圖有 n(n-1)/2 條邊, 稱為無(wú)向完全圖 若 n 個(gè)頂點(diǎn)的有向圖有n(n-1) 條邊, 稱為有向完全圖,證明：,有向完全圖有n(n-1)條邊。,證明：若是有向完全圖，則n個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)都有一

3、條弧指向其它n-1個(gè)頂點(diǎn), 因此總邊數(shù)=n(n-1),6,證明：從可以直接推論出無(wú)向完全圖的邊數(shù)因?yàn)闊o(wú)方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。,無(wú)向完全圖有n(n-1)/2 條邊。,例：判斷下列4種圖形各屬什么類型？,7,稀疏圖：稠密圖：,設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。,子 圖：,邊較少的圖。通常邊數(shù)遠(yuǎn)少于nlogn 邊很多的圖。,無(wú)向圖中，邊數(shù)接近n(n-1)/2 有向圖中，邊數(shù)接近n(n-1),B,例如：,8,15,9,7,21,11,3,2,有向網(wǎng)或無(wú)向網(wǎng)是弧或邊帶權(quán)的圖。,鄰接點(diǎn)：若邊(v,

4、w) VR，則頂點(diǎn)v 和頂點(diǎn)w 互為鄰接點(diǎn)。,邊(v,w) 依附于頂點(diǎn)v 和w，或者與頂點(diǎn)v,w相關(guān)聯(lián) 。,頂點(diǎn)v的度：是和v 相關(guān)聯(lián)的邊的數(shù)目,記為TD(v).,頂點(diǎn)v的出度: 以頂點(diǎn)v 為尾的弧的數(shù)目;記為OD(v).,頂點(diǎn)v的入度: 以頂點(diǎn)v 為頭的弧的數(shù)目,記為ID(v).,頂點(diǎn)的度(TD)=出度(OD)+入度(ID),問(wèn)：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？,答：是樹(shù)！而且是一棵有向樹(shù)！,9,路徑:設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列: v=vi,0 ,vi,1 , , vi,m=w 中，(vi,j-1 ,vi,j)（或 vi,j-1,vi,j） VR

5、 1jm,則稱從頂點(diǎn)v 到頂點(diǎn)w 之間存在一條路徑。 路徑長(zhǎng)度：路徑上邊（或弧）的數(shù)目。,如:從A到F長(zhǎng)度為 3 的路徑A,B,C,F或A，E，C，F(xiàn),簡(jiǎn)單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。,簡(jiǎn)單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。,10,連通圖：無(wú)向圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相連通。,連通分量：非連通圖中的極大連通子圖。,強(qiáng)連通圖：在有向圖中, 每一對(duì)頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑,強(qiáng)連通分量：非強(qiáng)連通圖中的極大強(qiáng)連通子圖。,11,生成樹(shù)：,生成森林：,假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n-1 條邊和 n 個(gè)

6、頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹(shù)。,由若干棵生成樹(shù)組成，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊是最少的。（對(duì)有向或無(wú)向圖均適用）,12,CreatGraph( /返回v的“第一個(gè)鄰接點(diǎn)” 若該頂點(diǎn)在G中沒(méi)有鄰接點(diǎn)，則返回“空”。,NextAdjVex(G, v, w); /返回v的（相對(duì)于w的） “下一個(gè)鄰接點(diǎn)”。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。,插入或刪除頂點(diǎn),InsertVex( /在圖G中增添新頂點(diǎn)v。,DeleteVex( /從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。,BFSTraverse(G, v, Visit(); /從頂點(diǎn)

7、v起廣度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。,遍 歷,15,7.2 圖的存儲(chǔ)結(jié)構(gòu),圖的特點(diǎn)：,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：,順序存儲(chǔ)結(jié)構(gòu)：,難！,（多個(gè)頂點(diǎn)，無(wú)序可言，無(wú)法僅以頂點(diǎn)坐標(biāo)表達(dá)相互關(guān)系）,可用多重鏈表,鄰接矩陣(數(shù)組)表示法 鄰接表(鏈?zhǔn)?表示法 十字鏈表表示法 鄰接多重表表示法,但可用數(shù)組描述元素間關(guān)系。,非線性結(jié)構(gòu)（m :n）,鄰接矩陣,鄰接表 十字鏈表 鄰接多重表,各種表示法成立的原則：存入電腦后能唯一復(fù)原,16, 建立一個(gè)頂點(diǎn)表和一個(gè)鄰接矩陣。,1. 鄰接矩陣（數(shù)組）表示法,記錄各個(gè)頂點(diǎn)信息,表示各個(gè)頂點(diǎn)之間關(guān)系, 設(shè)圖 A = (V, E ) 有 n 個(gè)頂點(diǎn)，則圖

8、的鄰接矩陣是一個(gè)二維數(shù)組 A.arcsnn，定義為：,17,分析1：無(wú)向圖的鄰接矩陣是對(duì)稱的； 分析2：頂點(diǎn)i 的度第 i 行 (列) 中1 的個(gè)數(shù)； 特別：完全圖的鄰接矩陣中，對(duì)角元素為0，其余全1。,例1：,鄰接矩陣：,A.arcs =,（ v1 v2 v3 v4 v5 ）,v1 v2 v3 v4 v5,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,頂點(diǎn)表：,無(wú)向圖的鄰接矩陣如何表示？,18,例2 ：有向圖的鄰接矩陣如何表示？,分析1：有向圖的鄰接矩陣可能是不對(duì)稱的。 分析2：頂點(diǎn)vi的出度=第i行元素之和; 頂點(diǎn)vi的入度=第i列元素

9、之和; 頂點(diǎn)的度=第i行元素之和+第i列元素之和。,鄰接矩陣：,A.arcs =,( v1 v2 v3 v4 ),v1 v2 v3 v4,注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）； 第j列含義：以結(jié)點(diǎn)vj為頭的弧(即入度邊）。,頂點(diǎn)表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,19,例3 ： 有權(quán)圖（即網(wǎng)絡(luò)）的鄰接矩陣如何表示？,定義：,鄰接矩陣：,N.arcs =,(v1 v2 v3 v4 v5 v6),頂點(diǎn)表：, 5 7 4 8 9 5 6 5 3 1 ,v1 v2 v3 v4 v5 v6,20,容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷

10、頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。 n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。,鄰接矩陣法優(yōu)點(diǎn)：,鄰接矩陣法缺點(diǎn)：,對(duì)稀疏圖而言尤其浪費(fèi)空間。,圖的鄰接矩陣在機(jī)內(nèi)如何表示？ （參見(jiàn)教材P161）,注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù) typedef enum DG, DN, UDG,UDN GraphKind; /有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng),21,typedef struct ArcCell / 弧的定義 VRType adj;

11、/ VRType是頂點(diǎn)關(guān)系類型。 /對(duì)無(wú)權(quán)圖,用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。 InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef struct / 圖的定義 VertexType vexsMAX_VERTEX_NUM; / 頂點(diǎn)向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;,22,2. 鄰接表（鏈?zhǔn)剑┍硎痉? 對(duì)每個(gè)頂點(diǎn)vi 建立一個(gè)單鏈表

12、，把與vi有關(guān)聯(lián)的邊（或以vi為尾的弧)的信息鏈接起來(lái)，表中每個(gè)結(jié)點(diǎn)都設(shè)為3個(gè)域。, 每個(gè)單鏈表還應(yīng)當(dāng)附設(shè)一個(gè)表頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息；,表結(jié)點(diǎn),頭結(jié)點(diǎn),鄰接點(diǎn)域，表示vi 鄰接點(diǎn)的位置,鏈域，指向下一條邊或弧的結(jié)點(diǎn),數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi 信息,鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn), 每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。,邊或弧的信息,23,例1：無(wú)向圖的鄰接表如何表示？,鄰接表：,請(qǐng)注意：鄰接表不唯一！因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。,v1鄰接點(diǎn)v4的位置,此無(wú)權(quán)圖未開(kāi)第3分量,TD(Vi)=單鏈表中Vi鏈接的結(jié)點(diǎn)個(gè)數(shù),24,例2：有向圖的鄰接表如何表示？,鄰接表(出邊),逆鄰接表(

13、入邊),0123,0123,在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。,OD(Vi)=鄰接表中Vi鏈接的結(jié)點(diǎn)數(shù)ID(Vi)=逆鄰接表中Vi鏈接的結(jié)點(diǎn)數(shù),TD(Vi) = OD( Vi ) + ID( Vi ),25,例3：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫(huà)出該網(wǎng)絡(luò)。,80,64,1,2,5,當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！,26,分析1：對(duì)于n個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。 若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。,鄰接表存儲(chǔ)法的特點(diǎn)：,分析2:在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O

14、(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。,它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)，兩個(gè)結(jié)點(diǎn)表示一條邊或弧,鄰接表的缺點(diǎn)：,鄰接表的優(yōu)點(diǎn)：,空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；,判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。,27,討論：鄰接表與鄰接矩陣有什么異同之處？,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)）。 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。 3. 用途： 鄰接矩

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

16、 /應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù) int kind; /還應(yīng)說(shuō)明圖的種類（用標(biāo)志） ALGraph;,Typedef struct VNode /頂點(diǎn)結(jié)構(gòu) VertexType data; /頂點(diǎn)信息 ArcNode * firstarc; /指向第一條依附該頂點(diǎn)的弧的指針 VNode, AdjList MAX_VERTEX_NUM ; /鄰接表,30,它是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。 (1)開(kāi)設(shè)弧結(jié)點(diǎn)，設(shè)5個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素） (2)開(kāi)設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）,弧結(jié)點(diǎn),3. 十字鏈表表示法,tailvex: 弧

17、尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置 hlink: 弧頭相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息,31,data : 頂點(diǎn)信息 firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn) firstout: 以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn),問(wèn)：n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？,順序存儲(chǔ)結(jié)構(gòu),頂點(diǎn)結(jié)點(diǎn),十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等。,空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。,32,0 1 2,例：畫(huà)出有向圖的十字鏈表。,弧結(jié)點(diǎn),頂點(diǎn)結(jié)點(diǎn),33,這是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，當(dāng)對(duì)邊操作時(shí)建議采用此種結(jié)構(gòu)存儲(chǔ)。 （1）設(shè)立邊結(jié)點(diǎn)， 6個(gè)域（每條邊是一個(gè)數(shù)據(jù)元素） （2）設(shè)立頂點(diǎn)結(jié)點(diǎn)， 2個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）,邊結(jié)點(diǎn),4. 鄰接多重表表示法,mark：標(biāo)志域，標(biāo)記該邊是否被搜索過(guò)。 ivex， jvex :