計(jì)算機(jī)軟件及應(yīng)用數(shù)據(jù)結(jié)構(gòu)圖PPT課件

1、5. 熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此應(yīng)掌握 1 至 2 種建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法。6. 學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。7. 了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。第1頁/共35頁2 其中：V 是G 的頂點(diǎn)集合，是有窮非空集； E 是G 的邊集合，是有窮集。問：當(dāng)E(G)為空時(shí)，圖G存在否？答：還存在！但此時(shí)圖G只有頂點(diǎn)而沒有邊。有向圖：無向圖：完全圖：圖G中的每條邊都是有方向的；圖G中的每條邊都是無方向的；圖G任意兩個(gè)頂點(diǎn)都有一條邊相連接；v若 n 個(gè)頂點(diǎn)的無向圖有 n(n-1)/2 條邊, 稱為無向

2、完全圖v若 n 個(gè)頂點(diǎn)的有向圖有n(n-1) 條邊, 稱為有向完全圖V=vertex E=edge圖：記為 G( V, E )v1v2v3v5v4v4v1v2v3v4第2頁/共35頁3證明：證明：若是完全有向圖，則n個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)都有一條弧指向其它n-1個(gè)頂點(diǎn), 因此總邊數(shù)=n(n-1)證明：從可以直接推論出無向完全圖的邊數(shù)因?yàn)闊o方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。12341234第3頁/共35頁4例：判斷下列4種圖形各屬什么類型？無向無向圖(樹)有向圖有向G1的頂點(diǎn)集合為V(G1)=0,1,2,3邊集合為E(G1)=(0,1),(0,2),(0,3),(1,2)

3、,(1,3),(2,3)完全圖完全圖第4頁/共35頁5稀疏圖：稀疏圖：稠密圖：稠密圖： 設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。子 圖：邊較少的圖。通常邊數(shù)遠(yuǎn)少于邊很多的圖。 無向圖中，邊數(shù)接近有向圖中，邊數(shù)接近第5頁/共35頁6帶權(quán)圖：帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。連通圖：在無向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。帶權(quán)圖在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)vi和

4、vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱此圖是強(qiáng)連通圖。強(qiáng)連通圖：網(wǎng) 絡(luò)：DEABCFJLMGHIK非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。第6頁/共35頁7生成樹：v1v2v3v4v如果在生成樹上添加1條邊，必定構(gòu)成一個(gè)環(huán)。v若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。生成森林：第7頁/共35頁8鄰接點(diǎn)：鄰接點(diǎn)：有向邊(u, v)稱為弧，邊的始點(diǎn)u 叫弧尾，終點(diǎn)v 叫弧頭。頂點(diǎn) v 的入度是以 v 為終點(diǎn)的有向邊的條數(shù), 記作 ID(v); 頂點(diǎn) v 的出度是以 v 為始點(diǎn)的有向邊的條數(shù), 記作 OD(v)。若 (u, v) 是 E(G) 中的一條邊，則稱 u 與

5、v 互為鄰接頂點(diǎn)?；☆^和弧尾：入度和出度：?jiǎn)枺寒?dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？uv度：頂點(diǎn)v 的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中, 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。答：是樹！而且是一棵有向樹！第8頁/共35頁9簡(jiǎn)單路徑：簡(jiǎn)單路徑：路徑上各頂點(diǎn) v1,v2,.,vm 均不互相重復(fù)?；芈罚?若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合，則稱這樣的路徑為回路或環(huán)。路徑：在圖 G(V, E) 中, 若從頂點(diǎn) vi 出發(fā), 沿一些邊經(jīng)過一些頂點(diǎn) vp1, vp2, , vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列 ( vi vp1 vp2 . vp

6、m vj ) 為從頂點(diǎn)vi 到頂點(diǎn) vj 的路徑。它經(jīng)過的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj)應(yīng)當(dāng)是屬于E的邊。路徑長(zhǎng)度：非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)；帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。圖的術(shù)語（續(xù)）第9頁/共35頁圖是一種數(shù)據(jù)元素間存在的數(shù)據(jù)結(jié)構(gòu)加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類型。 ADT Graph數(shù)據(jù)對(duì)象：V是具有相同特性的數(shù)據(jù)元素的集 合，稱為頂點(diǎn)集。 數(shù)據(jù)關(guān)系：R = E E= | v, wV 且 P(v, w), 頂點(diǎn)對(duì) 稱為邊或弧，P(v,w) 定義了 的意義或信息 10第10頁/共35頁初始化操作CreateGraph(&G, nu

7、m);操作結(jié)果：構(gòu)造一個(gè)頂點(diǎn)數(shù)為num，邊數(shù)為0的圖。 銷毀操作DestroyGraph(&G);初始條件：圖 G 存在。操作結(jié)果：銷毀圖 G。 第11頁/共35頁引用型操作FirstAdjVex(G, v);初始條件：圖 G 存在，v 是 G 中某個(gè)頂點(diǎn)。操作結(jié)果：返回 v 的第一個(gè)。若該頂點(diǎn)在 G 中沒有鄰接點(diǎn)，則返回“空”。 若G，則稱 w 為 v 的鄰接點(diǎn)，若(v,w)G，則稱 w 和 v 互為鄰接點(diǎn)。 NextAdjVex(G, v, w);初始條件:圖G存在,v是G中某個(gè)頂點(diǎn),w是v的鄰接頂點(diǎn)。 操作結(jié)果:返回 v 的（相對(duì)于 w 的）鄰接點(diǎn)。若 w是 v 的最后一個(gè)鄰接點(diǎn)，則返回

8、“空”。 若 v 有多個(gè)鄰接點(diǎn)，則在圖的存儲(chǔ)結(jié)構(gòu)建立之后，其鄰接點(diǎn)之間的相對(duì)次序也就自然形成了。12第12頁/共35頁加工型操作InsertEdge(&G, v, w);初始條件：圖 G 存在，v 和 w 是 G 中兩個(gè)頂點(diǎn)。操作結(jié)果：在 G 中增添以v, w為頂點(diǎn)的邊 DeleteEdge(&G, v, w);初始條件：圖 G 存在，v 和 w 是 G 中兩個(gè)頂點(diǎn)。操作結(jié)果：在 G 中刪除以v, w為頂點(diǎn)的邊。 ADT Graph 13第13頁/共35頁14圖的特點(diǎn)：圖的特點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)： 難?。ǘ鄠€(gè)頂點(diǎn)，無序，僅用頂點(diǎn)坐標(biāo)無法表達(dá)相互關(guān)系）可用多重鏈表但可用數(shù)組描述元素間關(guān)

9、系。非線性結(jié)構(gòu)（m :n）鄰接矩陣鄰接表十字鏈表鄰接多重表各種表示法成立的原則：存入電腦后能惟一復(fù)原第14頁/共35頁15 , ),( , ,.否否則則或或者者如如果果01AEjiEjijiEdge鄰接矩陣：A.Edge =（v1 v2 v3 v4 v5)v1v2v3v4v5頂點(diǎn)表：下面無向圖的鄰接矩陣如何表示？v1v2v3v5v4v4記錄各個(gè)頂點(diǎn)信息表示各個(gè)頂點(diǎn)之間關(guān)系0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0第15頁/共35頁16例2 ：下面有向圖的鄰接矩陣如何表示？有向圖的鄰接矩陣可能是不對(duì)稱的。頂點(diǎn)vi的出度=第i行元素之和，OD(vi

10、)= jA.Edge i j 頂點(diǎn)vi的入度=第i列元素之和。ID(vi )= iA.Edge j i 頂點(diǎn)的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi )v1v2v3v4鄰接矩陣：A.Edge =( v1 v2 v3 v4 )v1v2v3v4在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。頂點(diǎn)表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 第16頁/共35頁17 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。 n個(gè)頂

11、點(diǎn)需要個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n )。例3 ： 有權(quán)圖（即網(wǎng)絡(luò)）的鄰接矩陣如何表示？定義：A.Edge i j =Wij 或（vi, vj）VR 無邊（?。﹙1v2v3v4Nv5v65489755613以有向網(wǎng)為例：鄰接矩陣：N.Edge =( v1 v2 v3 v4 v5 v6 )鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：頂點(diǎn)表： 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v6對(duì)稀疏圖而言尤其浪費(fèi)空間。第17頁/共35頁18注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /假

12、設(shè)的最大頂點(diǎn)數(shù)Typedef enum DG, DN, UG, UN GraphKind; /有向/無向圖，有向/無向網(wǎng)圖的鄰接矩陣在機(jī)內(nèi)如何表示？ （參見教材（參見教材P161P161）對(duì)于n個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率=O(n2)Typedef struct ArcCell /?。ㄟ叄┙Y(jié)點(diǎn)的定義 VRType adj; /頂點(diǎn)間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型 InfoType *info; /該弧相關(guān)信息的指針ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;Typedef struct /圖的定義VertexType vexs MAX

13、_VERTEX_NUM ; /頂點(diǎn)表，用一維向量即可(n)AdjMatrix arcs; /鄰接矩陣n*nInt Vernum, arcnum; /頂點(diǎn)總數(shù)n，?。ㄟ叄┛倲?shù)eGraphKind kind; /圖的種類標(biāo)志MGraph; 第18頁/共35頁19Status CreateUDN(MGraph &G) /無向網(wǎng)的構(gòu)造，用鄰接矩陣表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /輸入總頂點(diǎn)數(shù)n、總弧數(shù)e和信息for(i=0;iG.vexnum,;+i) scanf(&G.vexsi );/輸入n個(gè)頂點(diǎn)值，存入一維向量例：用鄰接矩陣生成無向網(wǎng)的算法（參見

14、教材（參見教材P162P162）對(duì)于n個(gè)頂點(diǎn)e條弧的網(wǎng)，建網(wǎng)時(shí)間效率 = O(n+n2+e*n)for(i=0; iG.vexnum; +i) /對(duì)鄰接矩陣n*n個(gè)單元初始化，adj=,info=NULLfor(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL; for(k=0;kG.arcnum;+k) /給鄰接矩陣有關(guān)單元賦初值(循環(huán)次數(shù)弧數(shù)e scanf(&v1, &v2, &w); /輸入弧的兩頂點(diǎn)以及對(duì)應(yīng)權(quán)值 i=LocateVex(G,v1); j=LocateVex(G,v2); /找到兩頂點(diǎn)在矩陣中的位置(n次) G.arcsij.adj=w;

15、 /輸入對(duì)應(yīng)權(quán)值 If(IncInfo) Input(*G.); /如果弧有信息則填入 G.arcsij = G.arcs j i； /無向網(wǎng)是對(duì)稱矩陣 return OK; / CreateUDN 第19頁/共35頁20adjvex nextarcinfodatafirstarc鄰接點(diǎn)域，表示vi 鄰接點(diǎn)的位置鏈域，指向下一個(gè)邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi 信息鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)第20頁/共35頁21例例1 1：無向圖的鄰接表如何表示？無向圖的鄰接表如何表示？v1v2v3v5v4v4鄰接表0123413341420例2：有向圖的

16、鄰接表如何表示？v1v2v3v4V4V3V2V12301鄰接表(出邊)V4V3V2V13020逆鄰接表(入邊)請(qǐng)注意：鄰接表不惟一！因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。v1v2v3v4v5231420v1鄰接點(diǎn)v4的位置此無權(quán)圖未開第3分量01230123第21頁/共35頁22例例3 3：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。絡(luò)。當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！第22頁/共35頁23分析1: 對(duì)于n個(gè)頂點(diǎn)e條邊的無向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。鄰接表

17、存儲(chǔ)法的特點(diǎn)：分析2:在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)怎樣計(jì)算無向圖頂點(diǎn)的度？鄰接表的缺點(diǎn)：怎樣計(jì)算有向圖頂點(diǎn)的出度？怎樣計(jì)算有向圖頂點(diǎn)的入度？怎樣計(jì)算有向圖頂點(diǎn)Vi的度：需遍歷全表鄰接表的優(yōu)點(diǎn)：TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù)OD(Vi)單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)I D( Vi ) 鄰接點(diǎn)為Vi的弧個(gè)數(shù)TD(Vi) = OD( Vi ) + I D( Vi )空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒有鄰接矩陣方便。第23頁/共35頁

18、241. 聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2. 區(qū)別： 對(duì)于任一確定的無向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無關(guān)）。 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3. 用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（en2)第24頁/共35頁25圖的鄰接表在機(jī)內(nèi)如何表示？ （參見教材（參見教材P163P163）#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)空間效率為O(n+2e)或O(n+e)時(shí)間效率為O(

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

20、de *nextarcs; /指向下一條弧的指針 InfoArc *info; /該弧相關(guān)信息的指針 ArcNode；第25頁/共35頁26 它是有向圖的另一種鏈?zhǔn)浇Y(jié)構(gòu)。 思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。1、開設(shè)弧結(jié)點(diǎn)，設(shè)5個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素）2、開設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）tailvexheadvexhlinktlinkinfo data : 頂點(diǎn)信息Firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)Firstout: 以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)dataFirstinFirstout頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)tailvex: 弧尾頂點(diǎn)位置 headvex:

21、 弧頭頂點(diǎn)位置hlink: 弧頭相同的下一弧位置tlink: 弧尾相同的下一弧位置info: 弧信息n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？仍用順序存儲(chǔ)結(jié)構(gòu)第26頁/共35頁27#define MAX_VERTEX_NUM 20十字鏈表存儲(chǔ)結(jié)構(gòu)描述：十字鏈表存儲(chǔ)結(jié)構(gòu)描述：Typedef struct ArcBox /弧結(jié)點(diǎn)結(jié)構(gòu)，5分量 int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox;Typedef struct VexNode /頂點(diǎn)結(jié)構(gòu), 3分量 VertexType data; ArcBox * f

22、irstin,*firstout;VexNode;Typedef struct /圖結(jié)構(gòu),整體概念 VexNode xlist MAX_VERTEX_NUM ; /表頭向量 int vexnum, arcnum;OLGraph; 采用十字鏈表構(gòu)造有向圖算法見教材p165第27頁/共35頁28v1v2v3v42 0233031例：畫出有向圖的十字鏈表。例：畫出有向圖的十字鏈表。十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等。FirstoutFirstindata頂點(diǎn)結(jié)點(diǎn)infotlinkhlinkheadvextailvex弧結(jié)點(diǎn)0v11v22v33v401230 102此無權(quán)圖未開第4分量空間

23、復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。第28頁/共35頁29這是無向圖的另一種存儲(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ù)元素）markivexilinkjvexjlinkinfo邊結(jié)點(diǎn) data : 存儲(chǔ)頂點(diǎn)信息Firstedge : 依附頂點(diǎn)的第一條邊結(jié)點(diǎn)dataFirstedge頂點(diǎn)結(jié)點(diǎn)mark：標(biāo)志域ivex， jvex : 邊依附的兩個(gè)頂點(diǎn)位置 ilink: 指向下一條依附頂點(diǎn) i 的邊位置jlink; 指向下一條依附頂點(diǎn) j 的邊位置info: 邊信息n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？仍用順序

24、存儲(chǔ)結(jié)構(gòu)第29頁/共35頁30121 4232 43 4 v1v2v3v5v4v4例：畫出無向圖的鄰接多重例：畫出無向圖的鄰接多重表表鄰接多重表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的度等。0v11v22v33v44v501234Firstedgedata頂點(diǎn)結(jié)點(diǎn)markinfojlinkjvexilinkivex邊結(jié)點(diǎn)空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。0103此無權(quán)圖未開第6分量(v1,v2)(v1,v4)(v2,v3)(v2,v5)(v3,v4)(v3,v5)(v4,v5)第30頁/共35頁31一、深度優(yōu)先搜索二、廣度優(yōu)先搜索 遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫做圖的基本運(yùn)算。遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過程。圖的特