資源描述：
《數(shù)據(jù)結(jié)構(gòu) C語言版 教學(xué)課件 作者 嚴(yán)蔚敏 李冬梅 吳偉民 第6章 圖.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、2021年7月25日北京林業(yè)大學(xué)信息學(xué)院李冬梅數(shù)據(jù)結(jié)構(gòu)2021年7月25日北京林業(yè)大學(xué)信息學(xué)院線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹集合——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系圖形結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖邏輯結(jié)構(gòu)2021年7月25日北京林業(yè)大學(xué)信息學(xué)院第6章 圖6.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)結(jié)構(gòu)6.3圖的遍歷6.4圖的應(yīng)用教學(xué)內(nèi)容2021年7月25日北京林業(yè)大學(xué)信息學(xué)院1.掌握：圖的基本概念及相關(guān)術(shù)語和性質(zhì)2.熟練掌握：圖的鄰接矩陣和鄰接表兩種存儲(chǔ)表示方法3.熟練掌握：圖的兩種遍歷方法DFS和B
2、FS4.熟練掌握：最短路算法（Dijkstra算法）5.掌握：最小生成樹的兩種算法及拓?fù)渑判蛩惴ǖ乃枷虢虒W(xué)目標(biāo)2021年7月25日北京林業(yè)大學(xué)信息學(xué)院6.1圖的定義和術(shù)語圖：Graph=(V,E)V：頂點(diǎn)(數(shù)據(jù)元素)的有窮非空集合；E：邊的有窮集合。無向圖：有向圖：每條邊都是無方向的每條邊都是有方向的2021年7月25日北京林業(yè)大學(xué)信息學(xué)院完全圖：任意兩個(gè)點(diǎn)都有一條邊相連無向完全圖有向完全圖n(n-1)/2條邊n(n-1)條邊2021年7月25日北京林業(yè)大學(xué)信息學(xué)院稀疏圖：有很少邊或弧的圖。稠密圖：有較多邊或弧的圖。網(wǎng)：邊/弧帶權(quán)的圖。鄰接：
3、有邊/弧相連的兩個(gè)頂點(diǎn)之間的關(guān)系。存在(vi,vj)，則稱vi和vj互為鄰接點(diǎn)；存在，則稱vi鄰接到vj，vj鄰接于vi關(guān)聯(lián)(依附)：邊/弧與頂點(diǎn)之間的關(guān)系。存在(vi,vj)/，則稱該邊/弧關(guān)聯(lián)于vi和vj2021年7月25日北京林業(yè)大學(xué)信息學(xué)院頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù),記作ID(v)頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)問：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何
4、形狀？答：是樹！而且是一棵有向樹！2021年7月25日北京林業(yè)大學(xué)信息學(xué)院路徑：接續(xù)的邊構(gòu)成的頂點(diǎn)序列。路徑長(zhǎng)度：路徑上邊或弧的數(shù)目/權(quán)值之和?；芈?環(huán))：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。簡(jiǎn)單路徑：除路徑起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同的路徑。簡(jiǎn)單回路(簡(jiǎn)單環(huán))：除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的路徑。2021年7月25日北京林業(yè)大學(xué)信息學(xué)院非連通圖連通圖強(qiáng)連通圖非強(qiáng)連通圖V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4連通圖（強(qiáng)連通圖）在無（有）向圖G=(V,{E})中，若對(duì)任何兩個(gè)頂點(diǎn)v、u都
5、存在從v到u的路徑，則稱G是連通圖（強(qiáng)連通圖）。2021年7月25日北京林業(yè)大學(xué)信息學(xué)院(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2子圖設(shè)有兩個(gè)圖G=（V，{E}）、G1=（V1，{E1}），若V1?V，E1?E，則稱G1是G的子圖。 例:(b)、(c)是(a)的子圖權(quán)與網(wǎng)圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。帶權(quán)的圖稱為網(wǎng)。2021年7月25日北京林業(yè)大學(xué)信息學(xué)院連通分量（強(qiáng)連通分量）非連通圖V0V2V3V1V5V4無向圖G的極大連通子圖稱為G的連通分量。 極大連通子圖意思
6、是：該子圖是G連通子圖，將G的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通。V0V2V3V1V5V4連通分量2021年7月25日北京林業(yè)大學(xué)信息學(xué)院有向圖G的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。極大強(qiáng)連通子圖意思是：該子圖是G的強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通的。強(qiáng)連通分量V0V1V2V3V0V2V3V12021年7月25日北京林業(yè)大學(xué)信息學(xué)院極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。生成樹：包含無向圖G所有頂點(diǎn)的極小連通子圖。生成森林：對(duì)非連通圖，由各個(gè)連通分量的生成樹的集合。連通圖
7、G1G1的生成樹V0V4V3V1V2V0V4V3V1V2V0V4V3V1V22021年7月25日北京林業(yè)大學(xué)信息學(xué)院6.2圖的存儲(chǔ)結(jié)構(gòu)鄰接表鄰接多重表十字鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）多重鏈表重點(diǎn)介紹：鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法2021年7月25日北京林業(yè)大學(xué)信息學(xué)院建立一個(gè)頂點(diǎn)表（記錄各個(gè)頂點(diǎn)信息）和一個(gè)鄰接矩陣（表示各個(gè)頂點(diǎn)之間關(guān)系）。設(shè)圖A=(V,E)有n個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組A.Edge[n][n]，定義為：數(shù)組（鄰接矩陣）表示法2021年7月25日北京林業(yè)大學(xué)信息學(xué)院鄰接矩陣：A
8、.Edge=（v1v2v3v4v5）v1v2v3v4v50000000000000000000000000分析1：無向圖的鄰接矩陣是對(duì)稱的；分析2：頂點(diǎn)i的度＝第i
