第12章 圖(一)

1、計(jì)算機(jī)與控制工程學(xué)院第第1212章章 圖（一）圖（一）計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 圖的基本概念圖的基本概念 圖的存儲(chǔ)圖的存儲(chǔ) 圖的遍歷圖的遍歷 最小生成樹(shù)最小生成樹(shù)2計(jì)算機(jī)與控制工程學(xué)院圖的定義圖的定義 圖圖（graphgraph）：用線（）：用線（邊邊）連接起來(lái)的頂點(diǎn)）連接起來(lái)的頂點(diǎn)（節(jié)點(diǎn)節(jié)點(diǎn)）的集合）的集合 圖圖G=(V, E)G=(V, E) V V：頂點(diǎn)有限集合：頂點(diǎn)有限集合 E E：邊有限集合，：邊有限集合，(i, j)(i, j)，i i、j jV V3計(jì)算機(jī)與控制工程學(xué)院4計(jì)算機(jī)與控制工程學(xué)院5計(jì)算機(jī)與控制工程學(xué)院6計(jì)算機(jī)與控制工程學(xué)院7計(jì)算機(jī)與控制工程學(xué)院基本概念基本

2、概念(1)(1)頂點(diǎn)頂點(diǎn) (2)(2)邊邊 (3)(3)無(wú)向邊無(wú)向邊 (4)(4)有向邊有向邊(5)(5)關(guān)聯(lián)于關(guān)聯(lián)于 (6)(6)關(guān)聯(lián)至關(guān)聯(lián)至 (7)(7)鄰接于鄰接于 (8)(8)鄰接至鄰接至 (9)(9)無(wú)向圖無(wú)向圖 (10)(10)有向圖有向圖 (11)(11)完全圖完全圖 (12)(12)稀疏圖稀疏圖 (13)(13)稠密圖稠密圖(14)(14)帶權(quán)圖帶權(quán)圖 (15)(15)子圖子圖(16)(16)頂點(diǎn)的度頂點(diǎn)的度 (17)(17)入度入度 (18)(18)出度出度(19)(19)路徑路徑 (20)(20)路徑長(zhǎng)度路徑長(zhǎng)度 (21)(21)簡(jiǎn)單路徑簡(jiǎn)單路徑 (22)(22)回路回路(

3、23)(23)連通圖連通圖 (24)(24)連通分量連通分量 (25)(25)強(qiáng)連通圖強(qiáng)連通圖 (26)(26)強(qiáng)連通分量強(qiáng)連通分量(27)(27)生成樹(shù)生成樹(shù) (28)(28)生成森林生成森林8計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念1-81-8有向邊無(wú)向邊邊：(i, j)E=(1,2),(1,3),(1,4),(2,3),(3,4)E=(1,2),(2,3),(3,4),(4,3),(3,5),(5,4)(1)頂點(diǎn) (2)邊 (3)無(wú)向邊 (4)有向邊(5)關(guān)聯(lián)于 (6)關(guān)聯(lián)至 (7)鄰接于 (8)鄰接至 9計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念9-139-13(9)(9)無(wú)向圖：所有邊都是無(wú)向

4、邊的圖無(wú)向圖：所有邊都是無(wú)向邊的圖(10)(10)有向圖：所有邊都是有向邊的圖有向圖：所有邊都是有向邊的圖(11)(11)完全圖：邊數(shù)達(dá)到最大的圖完全圖：邊數(shù)達(dá)到最大的圖 n(n-1)/2n(n-1)/2(12)(12)稀疏圖：有很少邊的圖稀疏圖：有很少邊的圖(13)(13)稠密圖：有較多邊的圖稠密圖：有較多邊的圖10計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念1414 加權(quán)有向圖、加權(quán)無(wú)向圖加權(quán)有向圖、加權(quán)無(wú)向圖：每條邊賦予一個(gè)權(quán)重每條邊賦予一個(gè)權(quán)重(14)(14)網(wǎng)絡(luò)網(wǎng)絡(luò)（networknetwork）11計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念1515(15)(15)子圖：設(shè)有兩個(gè)圖子圖：設(shè)有兩個(gè)圖

5、G=(V, E)G=(V, E)和和G=(V, E)G=(V, E)， 如果如果VV是是V V的子集的子集 而且而且EE是是E E的子集的子集 則稱則稱GG是是G G的子圖的子圖121234123計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念16-1816-18(16)(16)頂點(diǎn)頂點(diǎn)v v的的度度：與：與v v關(guān)聯(lián)的邊的數(shù)目關(guān)聯(lián)的邊的數(shù)目(17)(17)有向圖中頂點(diǎn)有向圖中頂點(diǎn)v v的的入度入度：關(guān)聯(lián)至：關(guān)聯(lián)至v v的邊的數(shù)目的邊的數(shù)目(18)(18)有向圖中頂點(diǎn)有向圖中頂點(diǎn)v v的的出度出度：關(guān)聯(lián)于：關(guān)聯(lián)于v v的邊的數(shù)目的邊的數(shù)目131234入度：1,1,1,1出度：2,0,1,1計(jì)算機(jī)與控制工程

6、學(xué)院基本概念基本概念19-2219-22(19)(19)路徑路徑：當(dāng)且僅當(dāng)對(duì)于每一個(gè)當(dāng)且僅當(dāng)對(duì)于每一個(gè)j j（11j jk k），），邊邊( (i ij j, , i ij j+1+1) )都在都在E E中時(shí)，中時(shí)，頂點(diǎn)序列頂點(diǎn)序列P P= =i i1 1, , i i2 2, ., , ., i ik k是圖或有向圖是圖或有向圖G G=(=(V V, , E E) )中一條從中一條從i i1 1到到i ik k的路徑的路徑(20)(20)路徑長(zhǎng)度路徑長(zhǎng)度：路徑上所有邊的長(zhǎng)度之和：路徑上所有邊的長(zhǎng)度之和(21)(21)簡(jiǎn)單路徑簡(jiǎn)單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑(2

7、2)(22)回路回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑14計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念23-2423-24(23)(23)如果圖中任意兩個(gè)頂點(diǎn)如果圖中任意兩個(gè)頂點(diǎn)v vi i和和v vj j都是連通的，都是連通的，則圖則圖G G是是連通圖連通圖(24)(24)無(wú)向圖中的無(wú)向圖中的極大極大連通子圖稱為連通子圖稱為連通分量連通分量1512345計(jì)算機(jī)與控制工程學(xué)院161234675981011121312345812910111367計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念25-2625-26(25)(25)對(duì)于有向圖中任意兩個(gè)頂點(diǎn)對(duì)于有向圖中任意兩個(gè)頂點(diǎn)

8、v vi i和和v vj j，如果，如果從從v vi i到到v vj j和從和從v vj j到到v vi i都有路徑，則圖都有路徑，則圖G G是是強(qiáng)連強(qiáng)連通圖通圖(26)(26)有向圖中的極大連通子圖稱為有向圖中的極大連通子圖稱為強(qiáng)連通分量強(qiáng)連通分量1712341234計(jì)算機(jī)與控制工程學(xué)院基本概念基本概念27-2827-28(27)(27)一個(gè)連通圖的一個(gè)連通圖的生成樹(shù)生成樹(shù)含有圖中全部頂點(diǎn)，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的但只有足以構(gòu)成一棵樹(shù)的n-1n-1條邊條邊 無(wú)環(huán)的無(wú)向連通圖無(wú)環(huán)的無(wú)向連通圖樹(shù)樹(shù) 生成樹(shù)生成樹(shù)（spanning treespanning tree）：包含）：包含

9、G G中所有頂中所有頂點(diǎn)且是點(diǎn)且是G G的子圖的樹(shù)的子圖的樹(shù)(28)(28)生成森林：略生成森林：略18計(jì)算機(jī)與控制工程學(xué)院生成樹(shù)例生成樹(shù)例19計(jì)算機(jī)與控制工程學(xué)院圖的特性圖的特性G G為無(wú)向圖，頂點(diǎn)為無(wú)向圖，頂點(diǎn)i i的的度度（degreedegree）：與頂）：與頂點(diǎn)點(diǎn)i i相連的邊的數(shù)目相連的邊的數(shù)目特性特性1 1 設(shè)設(shè)G=(V, E)G=(V, E)為無(wú)向圖，為無(wú)向圖，|V|=n|V|=n，|E|=e|E|=e，d di i為頂點(diǎn)為頂點(diǎn)i i的度，則有的度，則有 1)1) 0 0e en(n-1)/2n(n-1)/2ednii2120計(jì)算機(jī)與控制工程學(xué)院特性特性1 1示例示例e=n(n

10、-1)/2完全圖21計(jì)算機(jī)與控制工程學(xué)院特性特性2 2G G為有向圖為有向圖入度入度（in-degreein-degree）：關(guān)聯(lián)）：關(guān)聯(lián)至至頂點(diǎn)頂點(diǎn)i i的邊的數(shù)的邊的數(shù)目，目，d di iinin出度出度（out-degreeout-degree）：關(guān)聯(lián)）：關(guān)聯(lián)于于頂點(diǎn)頂點(diǎn)i i的邊的數(shù)的邊的數(shù)目，目，d di ioutout特性特性2 G=(V, E)2 G=(V, E)為有向圖，有：為有向圖，有： 0 0e en(n-1)n(n-1)1)1) eddnioutiniini1122計(jì)算機(jī)與控制工程學(xué)院特性特性2 2示例示例e=n(n-1)完全有向圖23計(jì)算機(jī)與控制工程學(xué)院抽象數(shù)據(jù)類型抽象

11、數(shù)據(jù)類型抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型GraphGraph 實(shí)例實(shí)例頂點(diǎn)集合頂點(diǎn)集合V V和邊集合和邊集合E E操作操作CreateCreate( (n n) )：創(chuàng)建一個(gè)具有：創(chuàng)建一個(gè)具有n n個(gè)頂點(diǎn)、沒(méi)有邊的無(wú)向圖個(gè)頂點(diǎn)、沒(méi)有邊的無(wú)向圖ExistExist( (i i, ,j j) )：如果存在邊（：如果存在邊（i i, ,j j）則返回）則返回truetrue，否則返回，否則返回falsefalseEdgesEdges()()：返回圖中邊的數(shù)目：返回圖中邊的數(shù)目VerticesVertices()()：返回圖中頂點(diǎn)的數(shù)目：返回圖中頂點(diǎn)的數(shù)目AddAdd( (i i, ,j j) )：向圖中添加

12、邊（：向圖中添加邊（i i, ,j j）DeleteDelete( (i i, ,j j) )：刪除邊（：刪除邊（i i, ,j j）DegreeDegree( (i i) )：返回頂點(diǎn)：返回頂點(diǎn)i i的度的度 24計(jì)算機(jī)與控制工程學(xué)院有向圖抽象數(shù)據(jù)類型有向圖抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型DiGraphDiGraph 實(shí)例實(shí)例頂點(diǎn)集合頂點(diǎn)集合V V和邊集合和邊集合E E操作操作CreateCreate( (n n) )：創(chuàng)建一個(gè)具有：創(chuàng)建一個(gè)具有n n個(gè)頂點(diǎn)、沒(méi)有邊的有向圖個(gè)頂點(diǎn)、沒(méi)有邊的有向圖ExistExist( (i i, ,j j) )：如果存在邊（：如果存在邊（i i, ,j

13、j）則返回）則返回truetrue，否則返回，否則返回falsefalseEdgesEdges()()：返回圖中邊的數(shù)目：返回圖中邊的數(shù)目VerticesVertices()()：返回圖中頂點(diǎn)的數(shù)目：返回圖中頂點(diǎn)的數(shù)目AddAdd( (i i, ,j j) )：向圖中添加邊（：向圖中添加邊（i i, ,j j）DeleteDelete( (i i, ,j j) )：刪除邊（：刪除邊（i i, ,j j）InDegreeInDegree( (i i) )：返回頂點(diǎn)：返回頂點(diǎn)i i的入度的入度OutDegreeOutDegree( (i i) )：返回頂點(diǎn)：返回頂點(diǎn)i i的出度的出度 25計(jì)算機(jī)與

14、控制工程學(xué)院小結(jié)小結(jié) 線性表：?jiǎn)吻膀?qū)、單后繼線性表：?jiǎn)吻膀?qū)、單后繼 樹(shù)：?jiǎn)吻膀?qū)、多后繼樹(shù)：?jiǎn)吻膀?qū)、多后繼 圖：節(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩圖：節(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能是相關(guān)的個(gè)數(shù)據(jù)元素之間都可能是相關(guān)的 圖是真實(shí)世界中最一般的情況圖是真實(shí)世界中最一般的情況 當(dāng)前最熱的研究：社會(huì)計(jì)算！當(dāng)前最熱的研究：社會(huì)計(jì)算！26計(jì)算機(jī)與控制工程學(xué)院小結(jié)（續(xù)）小結(jié)（續(xù)） 線性表可以是空表、樹(shù)可以是空樹(shù)，但圖不線性表可以是空表、樹(shù)可以是空樹(shù)，但圖不能是空?qǐng)D，即圖的頂點(diǎn)集合必非空能是空?qǐng)D，即圖的頂點(diǎn)集合必非空 無(wú)向圖考慮連通性，有向圖考慮強(qiáng)連通性無(wú)向圖考慮連通性，有向圖考慮強(qiáng)連通

15、性 對(duì)非強(qiáng)連通的有向圖和非連通的無(wú)向圖遍歷對(duì)非強(qiáng)連通的有向圖和非連通的無(wú)向圖遍歷將得到將得到生成森林生成森林27計(jì)算機(jī)與控制工程學(xué)院特別說(shuō)明特別說(shuō)明 頂點(diǎn)對(duì)的細(xì)致表示方式頂點(diǎn)對(duì)的細(xì)致表示方式 有向圖中：有向圖中： 無(wú)向圖中：無(wú)向圖中：(i,j)(i,j) 頂點(diǎn)對(duì)的通用表示方式頂點(diǎn)對(duì)的通用表示方式 有向圖和無(wú)向圖均為有向圖和無(wú)向圖均為(i,j)(i,j) 無(wú)特殊要求時(shí)，上述方式都可無(wú)特殊要求時(shí)，上述方式都可28計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 圖的基本概念圖的基本概念 圖的存儲(chǔ)及基本操作圖的存儲(chǔ)及基本操作 圖的遍歷圖的遍歷 最小生成樹(shù)最小生成樹(shù)29計(jì)算機(jī)與控制工程學(xué)院三種存儲(chǔ)方式三種存儲(chǔ)方式

16、 鄰接矩陣鄰接矩陣 鄰接壓縮表鄰接壓縮表 鄰接鏈表鄰接鏈表 十字鏈表十字鏈表30順序存儲(chǔ)順序存儲(chǔ)鏈表存儲(chǔ)鏈表存儲(chǔ)計(jì)算機(jī)與控制工程學(xué)院存儲(chǔ)方式存儲(chǔ)方式1 1：鄰接矩陣：鄰接矩陣 鄰接矩陣鄰接矩陣（adjacency matrixadjacency matrix） 圖圖G=(V, E)G=(V, E)有有n n個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，V=1, 2, ., nV=1, 2, ., n n nn n的矩陣的矩陣A A G G為無(wú)向圖為無(wú)向圖 G G為有向圖為有向圖其他或, 0),(),( , 1),(EijEjijiA其他, 0),( , 1),(EjijiA31計(jì)算機(jī)與控制工程學(xué)院鄰接矩陣?yán)徑泳仃嚴(yán)?2計(jì)

17、算機(jī)與控制工程學(xué)院鄰接矩陣?yán)ɡm(xù)）鄰接矩陣?yán)ɡm(xù)）123567433計(jì)算機(jī)與控制工程學(xué)院鄰接矩陣?yán)ɡm(xù)）鄰接矩陣?yán)ɡm(xù)）34計(jì)算機(jī)與控制工程學(xué)院鄰接矩陣特性鄰接矩陣特性對(duì)對(duì)n n頂點(diǎn)的無(wú)向圖，頂點(diǎn)的無(wú)向圖，A(i, i)=0A(i, i)=0，1 1i in n無(wú)向圖的鄰接矩陣是無(wú)向圖的鄰接矩陣是對(duì)稱對(duì)稱的，的，A(i, j)=A(j, i), 1A(i, j)=A(j, i), 1i in n對(duì)對(duì)n n頂點(diǎn)的無(wú)向圖，頂點(diǎn)的無(wú)向圖，行、列之和均等于頂點(diǎn)的度行、列之和均等于頂點(diǎn)的度injnjdijAjiA11),(),(35計(jì)算機(jī)與控制工程學(xué)院鄰接矩陣特性鄰接矩陣特性對(duì)對(duì)n n頂點(diǎn)的有向圖頂點(diǎn)的

18、有向圖行之和等于頂點(diǎn)的出度行之和等于頂點(diǎn)的出度列之和等于頂點(diǎn)的入度列之和等于頂點(diǎn)的入度ininjoutinjdijAdjiA11),(),(36計(jì)算機(jī)與控制工程學(xué)院使用數(shù)組實(shí)現(xiàn)鄰接矩陣使用數(shù)組實(shí)現(xiàn)鄰接矩陣 二維數(shù)組二維數(shù)組 an+1n+1an+1n+1，aijaijA(i, j)A(i, j)，2(n+1)2(n+1)2 2字節(jié)字節(jié) annann，ai-1j-1ai-1j-1A(i, j)A(i, j)，2n2n2 2字節(jié)字節(jié) 優(yōu)化策略優(yōu)化策略 對(duì)角線無(wú)需存儲(chǔ)，節(jié)省對(duì)角線無(wú)需存儲(chǔ)，節(jié)省2n2n字節(jié)，形成一個(gè)新的字節(jié)，形成一個(gè)新的 (n-1)(n-1)n n的矩陣的矩陣sizeof(int)=2

19、37計(jì)算機(jī)與控制工程學(xué)院數(shù)組實(shí)現(xiàn)示例數(shù)組實(shí)現(xiàn)示例38計(jì)算機(jī)與控制工程學(xué)院數(shù)組實(shí)現(xiàn)示例（續(xù)）數(shù)組實(shí)現(xiàn)示例（續(xù)）123567439計(jì)算機(jī)與控制工程學(xué)院數(shù)組實(shí)現(xiàn)示例（續(xù)）數(shù)組實(shí)現(xiàn)示例（續(xù)）40計(jì)算機(jī)與控制工程學(xué)院可能的優(yōu)化可能的優(yōu)化 矩陣元素取值只是矩陣元素取值只是0 0或或1 1，只需一個(gè)二進(jìn)制位即，只需一個(gè)二進(jìn)制位即可保存可保存 n(n-1)/8n(n-1)/8字節(jié)，節(jié)省字節(jié)，節(jié)省1616倍倍 整數(shù)操作整數(shù)操作位操作位操作，存儲(chǔ)、檢索復(fù)雜，存儲(chǔ)、檢索復(fù)雜 無(wú)向圖是對(duì)稱矩陣，只保存上（下）三角即可無(wú)向圖是對(duì)稱矩陣，只保存上（下）三角即可 n(n-1)/16n(n-1)/16字節(jié)字節(jié)41計(jì)算機(jī)與控制

20、工程學(xué)院時(shí)間復(fù)雜性時(shí)間復(fù)雜性 求給定節(jié)點(diǎn)的鄰接節(jié)點(diǎn)集合，求給定節(jié)點(diǎn)的鄰接節(jié)點(diǎn)集合，Q Q(n)(n) 求圖中總的邊數(shù)，求圖中總的邊數(shù)，Q Q(n(n2 2) ) 增加、刪除一條邊，增加、刪除一條邊，Q Q(1)(1)42計(jì)算機(jī)與控制工程學(xué)院存儲(chǔ)方式存儲(chǔ)方式2 2：鄰接壓縮表：鄰接壓縮表 圖較為圖較為“稀疏稀疏”，鄰接矩陣空間浪費(fèi)，鄰接矩陣空間浪費(fèi) 鄰接壓縮表，鄰接壓縮表，packed-adjacency-listpacked-adjacency-list 使用一維數(shù)組使用一維數(shù)組h0:n+1h0:n+1，l l0:x0:x 有向圖：有向圖：x=e-1x=e-1；無(wú)向圖：；無(wú)向圖：x=2e-1x

21、=2e-1l l：保存鄰接頂點(diǎn)集合：保存鄰接頂點(diǎn)集合頂點(diǎn)頂點(diǎn)1 1的鄰接頂點(diǎn)，頂點(diǎn)的鄰接頂點(diǎn)，頂點(diǎn)2 2的鄰接頂點(diǎn)，的鄰接頂點(diǎn)，. hihi：頂點(diǎn)：頂點(diǎn)i i鄰接頂點(diǎn)集合在鄰接頂點(diǎn)集合在l l中的起始位置中的起始位置43計(jì)算機(jī)與控制工程學(xué)院鄰接壓縮表示例鄰接壓縮表示例44計(jì)算機(jī)與控制工程學(xué)院鄰接壓縮表示例（續(xù)）鄰接壓縮表示例（續(xù)）123567445計(jì)算機(jī)與控制工程學(xué)院鄰接壓縮表示例鄰接壓縮表示例46計(jì)算機(jī)與控制工程學(xué)院優(yōu)化優(yōu)化 數(shù)組元素的壓縮數(shù)組元素的壓縮 h h：取值范圍：取值范圍02e02e， 位即可位即可l l：取值范圍：取值范圍1n1n， 位即可位即可 總空間：總空間：) 12(log

22、2en2log)log)(log2) 12(log) 1(22nenOneen47計(jì)算機(jī)與控制工程學(xué)院時(shí)間復(fù)雜性時(shí)間復(fù)雜性 e e遠(yuǎn)遠(yuǎn)小于遠(yuǎn)遠(yuǎn)小于n n2 2空間復(fù)雜性遠(yuǎn)優(yōu)于鄰接矩陣空間復(fù)雜性遠(yuǎn)優(yōu)于鄰接矩陣 頂點(diǎn)頂點(diǎn)i i的度的度hi+1-hihi+1-hi，邊總數(shù)，邊總數(shù)hn+1/2hn+1/2，Q Q(1)(1) 增加、刪除一條邊，增加、刪除一條邊，O(n+e)O(n+e)48計(jì)算機(jī)與控制工程學(xué)院存儲(chǔ)方式存儲(chǔ)方式3 3：鄰接鏈表：鄰接鏈表 鄰接壓縮表插入、刪除復(fù)雜鄰接壓縮表插入、刪除復(fù)雜 鄰接鏈表（鄰接鏈表（linked-adjacency-listlinked-adjacency-lis

23、t） 鄰接表（鄰接頂點(diǎn)集合）用鏈表保存鄰接表（鄰接頂點(diǎn)集合）用鏈表保存 ChainChain類型的數(shù)組類型的數(shù)組h hhihi頂點(diǎn)頂點(diǎn)i i的鄰接表的鄰接表49計(jì)算機(jī)與控制工程學(xué)院鄰接鏈表示例鄰接鏈表示例50計(jì)算機(jī)與控制工程學(xué)院鄰接鏈表示例（續(xù)）鄰接鏈表示例（續(xù)）123567451計(jì)算機(jī)與控制工程學(xué)院鄰接鏈表示例（續(xù)）鄰接鏈表示例（續(xù)）52計(jì)算機(jī)與控制工程學(xué)院復(fù)雜性分析復(fù)雜性分析 空間復(fù)雜性空間復(fù)雜性 2(n+m+1)2(n+m+1)，有向圖：，有向圖：m=em=e，無(wú)向圖：，無(wú)向圖：m=2em=2e 時(shí)間復(fù)雜性時(shí)間復(fù)雜性 插入、刪除邊高效插入、刪除邊高效 求鄰接頂點(diǎn)集合：求鄰接頂點(diǎn)集合：Q

24、Q(n)(n) 求邊的總數(shù)：求邊的總數(shù)：Q Q(e)(e)53計(jì)算機(jī)與控制工程學(xué)院存儲(chǔ)方式存儲(chǔ)方式4 4：十字鏈表：十字鏈表54計(jì)算機(jī)與控制工程學(xué)院網(wǎng)絡(luò)的描述網(wǎng)絡(luò)的描述 圖描述簡(jiǎn)單擴(kuò)充，描述邊的耗費(fèi)圖描述簡(jiǎn)單擴(kuò)充，描述邊的耗費(fèi) 耗費(fèi)鄰接矩陣（耗費(fèi)鄰接矩陣（cost-adjacency-matrixcost-adjacency-matrix）C C A(i, j)=1A(i, j)=1，C(i, j)C(i, j)對(duì)應(yīng)邊的耗費(fèi)（權(quán)重）對(duì)應(yīng)邊的耗費(fèi)（權(quán)重） A(i, j)=0A(i, j)=0，C(i, j)=C(i, j)=不存在邊不存在邊55計(jì)算機(jī)與控制工程學(xué)院耗費(fèi)鄰接矩陣?yán)馁M(fèi)鄰接矩陣?yán)?6

25、計(jì)算機(jī)與控制工程學(xué)院耗費(fèi)鄰接矩陣?yán)ɡm(xù)）耗費(fèi)鄰接矩陣?yán)ɡm(xù)）57計(jì)算機(jī)與控制工程學(xué)院耗費(fèi)鄰接矩陣?yán)ɡm(xù)）耗費(fèi)鄰接矩陣?yán)ɡm(xù)）58計(jì)算機(jī)與控制工程學(xué)院鄰接鏈表實(shí)現(xiàn)鄰接鏈表實(shí)現(xiàn)59計(jì)算機(jī)與控制工程學(xué)院小結(jié)小結(jié) 鄰接矩陣適用于稠密圖、鄰接表適用于稀疏圖鄰接矩陣適用于稠密圖、鄰接表適用于稀疏圖 需要熟練掌握前三種表示方法需要熟練掌握前三種表示方法60計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 圖的基本概念圖的基本概念 圖的存儲(chǔ)及基本操作圖的存儲(chǔ)及基本操作 圖的遍歷圖的遍歷 最小生成樹(shù)最小生成樹(shù)61計(jì)算機(jī)與控制工程學(xué)院圖的遍歷圖的遍歷 從一個(gè)給定節(jié)點(diǎn)開(kāi)始，訪問(wèn)所有可達(dá)節(jié)點(diǎn)，且每從一個(gè)給定節(jié)點(diǎn)開(kāi)始，訪問(wèn)所有可達(dá)

26、節(jié)點(diǎn)，且每個(gè)頂點(diǎn)僅訪問(wèn)一次個(gè)頂點(diǎn)僅訪問(wèn)一次 寬度優(yōu)先搜索寬度優(yōu)先搜索（Breadth-First SearchBreadth-First Search, , BFSBFS） 開(kāi)始頂點(diǎn)開(kāi)始頂點(diǎn)1 1 1 1可達(dá)的頂點(diǎn)集合可達(dá)的頂點(diǎn)集合2, 3, 42, 3, 4 2, 3, 42, 3, 4可達(dá)的頂點(diǎn)集合可達(dá)的頂點(diǎn)集合5, 6, 75, 6, 7 5, 6, 75, 6, 7可達(dá)的頂點(diǎn)集合可達(dá)的頂點(diǎn)集合8, 98, 962計(jì)算機(jī)與控制工程學(xué)院寬度優(yōu)先搜索示例寬度優(yōu)先搜索示例63計(jì)算機(jī)與控制工程學(xué)院寬度優(yōu)先搜索算法偽代碼寬度優(yōu)先搜索算法偽代碼/ / /從頂點(diǎn)從頂點(diǎn)v v 開(kāi)始的寬度優(yōu)先搜索開(kāi)始的寬

27、度優(yōu)先搜索把頂點(diǎn)把頂點(diǎn)v v標(biāo)記為已到達(dá)頂點(diǎn)；標(biāo)記為已到達(dá)頂點(diǎn)；初始化隊(duì)列初始化隊(duì)列Q Q，其中僅包含一個(gè)元素，其中僅包含一個(gè)元素v v; ;while while ( (Q Q不空不空) ) 從隊(duì)列中刪除頂點(diǎn)從隊(duì)列中刪除頂點(diǎn)w w; ;令令u u 為鄰接于為鄰接于w w 的頂點(diǎn)的頂點(diǎn); ;while while ( (u u) ) if if ( ( u u 尚未被標(biāo)記尚未被標(biāo)記) ) 把把u u 加入隊(duì)列；加入隊(duì)列；把把u u 標(biāo)記為已到達(dá)頂點(diǎn)；標(biāo)記為已到達(dá)頂點(diǎn)； u u = = 鄰接于鄰接于w w 的下一個(gè)頂點(diǎn)；的下一個(gè)頂點(diǎn)； 64計(jì)算機(jī)與控制工程學(xué)院定理定理12-112-1 定理定理1

28、2-112-1 設(shè)設(shè)N N是一個(gè)任意的圖、有向圖或網(wǎng)絡(luò)，是一個(gè)任意的圖、有向圖或網(wǎng)絡(luò)，v v 是是N N 中的任意頂點(diǎn)中的任意頂點(diǎn)上述偽代碼能夠標(biāo)記從上述偽代碼能夠標(biāo)記從v v 出發(fā)可以到達(dá)的所出發(fā)可以到達(dá)的所有頂點(diǎn)（包括頂點(diǎn)有頂點(diǎn)（包括頂點(diǎn)v v）。）。65計(jì)算機(jī)與控制工程學(xué)院復(fù)雜性分析復(fù)雜性分析 可達(dá)頂點(diǎn)都被標(biāo)記可達(dá)頂點(diǎn)都被標(biāo)記 每個(gè)頂點(diǎn)只加入隊(duì)列一次，也只刪除一次每個(gè)頂點(diǎn)只加入隊(duì)列一次，也只刪除一次處理一次處理一次 處理頂點(diǎn)處理頂點(diǎn)遍歷它所有鄰接頂點(diǎn)遍歷它所有鄰接頂點(diǎn) 鄰接矩陣鄰接矩陣Q Q(sn)(sn) 鄰接鏈表鄰接鏈表)(Qioutid66計(jì)算機(jī)與控制工程學(xué)院深度優(yōu)先搜索深度優(yōu)先搜

29、索 Depth-First SearchDepth-First Search，DFSDFS v v為開(kāi)始頂點(diǎn)，首先標(biāo)記為開(kāi)始頂點(diǎn)，首先標(biāo)記v v 選擇一個(gè)與選擇一個(gè)與v v鄰接，且尚未標(biāo)記的頂點(diǎn)鄰接，且尚未標(biāo)記的頂點(diǎn)u u 像處理像處理v v一樣對(duì)一樣對(duì)u u進(jìn)行處理進(jìn)行處理DFSDFS遞歸調(diào)用遞歸調(diào)用 對(duì)對(duì)u u的處理完畢后，選擇另一個(gè)與的處理完畢后，選擇另一個(gè)與v v相鄰且未標(biāo)記相鄰且未標(biāo)記的頂點(diǎn)，繼續(xù)搜索的頂點(diǎn)，繼續(xù)搜索 若不存在，搜索中止若不存在，搜索中止67計(jì)算機(jī)與控制工程學(xué)院深度優(yōu)先搜索例深度優(yōu)先搜索例1 12 25 58 8 3 3 4 46 6 7 79 968計(jì)算機(jī)與控制工程

30、學(xué)院生成樹(shù)生成樹(shù) 對(duì)連通圖進(jìn)行對(duì)連通圖進(jìn)行BFSBFS，所有頂點(diǎn)都被標(biāo)記，所有頂點(diǎn)都被標(biāo)記 到達(dá)一個(gè)新的頂點(diǎn)，要通過(guò)相應(yīng)的邊到達(dá)一個(gè)新的頂點(diǎn)，要通過(guò)相應(yīng)的邊 恰好恰好n-1n-1條邊條邊連通子圖連通子圖生成樹(shù)生成樹(shù)69計(jì)算機(jī)與控制工程學(xué)院寬度優(yōu)先搜索構(gòu)造生成樹(shù)寬度優(yōu)先搜索構(gòu)造生成樹(shù)16870計(jì)算機(jī)與控制工程學(xué)院深度優(yōu)先搜索構(gòu)造生成樹(shù)深度優(yōu)先搜索構(gòu)造生成樹(shù)71計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 圖的基本概念圖的基本概念 圖的存儲(chǔ)及基本操作圖的存儲(chǔ)及基本操作 圖的遍歷圖的遍歷 最小生成樹(shù)最小生成樹(shù)72計(jì)算機(jī)與控制工程學(xué)院最小耗費(fèi)生成樹(shù)最小耗費(fèi)生成樹(shù)問(wèn)題關(guān)鍵：如何選擇生成樹(shù)的問(wèn)題關(guān)鍵：如何選擇生成樹(shù)的n-1n-1條邊條邊KruskalKruskal每個(gè)步驟選擇一條邊加入生成樹(shù)每個(gè)步驟選擇一條邊加入生成樹(shù)貪心準(zhǔn)則：不會(huì)產(chǎn)生環(huán)路，且耗費(fèi)最小貪心準(zhǔn)則：不會(huì)產(chǎn)生環(huán)路，且耗費(fèi)最小可按耗費(fèi)遞增順序考察每條邊可按耗費(fèi)遞增順序考察每條邊若產(chǎn)生環(huán)路，丟棄若產(chǎn)生環(huán)路，丟棄1.1. 否則，加入否則，加入73計(jì)算機(jī)與控制工程學(xué)院例例74計(jì)算機(jī)與控制工程學(xué)院例（續(xù)）例（續(xù)）75計(jì)算機(jī)與控制工程學(xué)院例（續(xù)）例（續(xù)）76計(jì)算機(jī)與控制工程學(xué)院偽代碼偽代碼/ / /在一個(gè)具有在一個(gè)具有n n 個(gè)頂點(diǎn)的網(wǎng)絡(luò)中找到一棵最小生成樹(shù)個(gè)頂點(diǎn)的網(wǎng)絡(luò)中找到一棵最小生成樹(shù)令令T T為所選邊的集合，初始化為所選邊的集合，初始化T T=