數(shù)據(jù)結(jié)構(gòu)與算法第六章清華大學(xué)出版社趙玉蘭

1、2圖圖 u圖是由頂點(diǎn)集合圖是由頂點(diǎn)集合 v 及頂點(diǎn)間的關(guān)系集合及頂點(diǎn)間的關(guān)系集合 e 所組成所組成的一種數(shù)據(jù)結(jié)構(gòu)：的一種數(shù)據(jù)結(jié)構(gòu)： graph 其中：其中： v=x|x 某個(gè)數(shù)據(jù)對(duì)象某個(gè)數(shù)據(jù)對(duì)象 是是非空的非空的有限頂點(diǎn)集合；有限頂點(diǎn)集合； e=(x, y) | x, y v /邊邊(edge)的集合的集合 或或 e= | x, y v /弧弧(arc)的集合的集合 是頂點(diǎn)之間關(guān)系的有限集合。是頂點(diǎn)之間關(guān)系的有限集合。在線(xiàn)性表中，元素個(gè)數(shù)可以為零，稱(chēng)為空表；在線(xiàn)性表中，元素個(gè)數(shù)可以為零，稱(chēng)為空表；在樹(shù)中，結(jié)點(diǎn)個(gè)數(shù)可以為零，稱(chēng)為空樹(shù)；在樹(shù)中，結(jié)點(diǎn)個(gè)數(shù)可以為零，稱(chēng)為空樹(shù)；在圖中，頂點(diǎn)個(gè)數(shù)不能為零，

2、但可以沒(méi)有邊。在圖中，頂點(diǎn)個(gè)數(shù)不能為零，但可以沒(méi)有邊。3無(wú)向圖無(wú)向圖u無(wú)向圖無(wú)向圖 g 是由兩個(gè)集合是由兩個(gè)集合 v(g) 和和 e(g) 組成的組成的 其中：其中：v(g) 是頂點(diǎn)的非空有限集；是頂點(diǎn)的非空有限集； e(g) 是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記為（記為（v,w）或（）或（w,v)，并且（，并且（v,w)=(w,v)有向圖有向圖u有向圖有向圖 g 是由兩個(gè)集合是由兩個(gè)集合 v(g) 和和 e(g) 組成的組成的 其中：其中：v(g) 是頂點(diǎn)的非空有限集；是頂點(diǎn)的非空有限集； e(g) 是有向邊（也稱(chēng)?。┑挠邢藜希∈怯邢蜻叄ㄒ卜Q(chēng)弧）的有限集

3、合，弧是頂點(diǎn)的有序?qū)Γ洖槭琼旤c(diǎn)的有序?qū)?，記為，v, w是頂點(diǎn)，是頂點(diǎn)，v 為弧為弧尾尾(或始點(diǎn)或始點(diǎn))，w 為弧頭為弧頭(終點(diǎn)終點(diǎn))， 。4例例u無(wú)向圖無(wú)向圖g1v(g1)=1,2,3,4,5,6,7e(g1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)u有向圖有向圖g2v(g2)=1,2,3,4,5,6 e(g2)=, , , , , , 245136g2157324g165圖的抽象數(shù)據(jù)類(lèi)型圖的抽象數(shù)據(jù)類(lèi)型class graph public: graph ( ); /建立一個(gè)空?qǐng)D建立一個(gè)空?qǐng)D void insertvertex ( typ

4、e & vertex ); void insertedge (int v1, int v2 ); void removevertex ( int v ); void removeedge ( int v1, int v2 ); int isempty ( ); type getweight ( int v1, int v2 ); int getfirstneighbor ( int v ); int getnextneighbor ( int v1, int v2 );6鄰接點(diǎn)（或相鄰點(diǎn)，關(guān)聯(lián)）鄰接點(diǎn)（或相鄰點(diǎn)，關(guān)聯(lián)）u如果如果 e=(u, v) 是是 e(g) 中的一條邊，則稱(chēng)中的一

5、條邊，則稱(chēng) u 與與 v 互互為鄰接點(diǎn)或相鄰點(diǎn)；稱(chēng)邊為鄰接點(diǎn)或相鄰點(diǎn)；稱(chēng)邊 e 與頂點(diǎn)與頂點(diǎn) u ,v 關(guān)聯(lián)；關(guān)聯(lián)；u如果如果 a= 是是 e(g) 中的一條弧，則稱(chēng)中的一條弧，則稱(chēng) u 鄰接到鄰接到v 或或 v 鄰接于鄰接于 u；稱(chēng)?。环Q(chēng)弧 a 與頂點(diǎn)與頂點(diǎn)u , v關(guān)聯(lián)。關(guān)聯(lián)。在線(xiàn)性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線(xiàn)性關(guān)系；在線(xiàn)性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線(xiàn)性關(guān)系；在樹(shù)結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次關(guān)系；在樹(shù)結(jié)構(gòu)中，結(jié)點(diǎn)之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。在圖結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。 fecbad線(xiàn)性結(jié)構(gòu)線(xiàn)性結(jié)構(gòu)abcdef樹(shù)結(jié)構(gòu)樹(shù)結(jié)構(gòu)v1v2v3v4v5圖結(jié)構(gòu)圖

6、結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比在線(xiàn)性結(jié)構(gòu)中，元素之間的關(guān)系為在線(xiàn)性結(jié)構(gòu)中，元素之間的關(guān)系為和和；在樹(shù)結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為在樹(shù)結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為和和；在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為。 fecbad線(xiàn)性結(jié)構(gòu)線(xiàn)性結(jié)構(gòu)abcdef樹(shù)結(jié)構(gòu)樹(shù)結(jié)構(gòu)v1v2v3v4v5圖結(jié)構(gòu)圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比9權(quán)權(quán)u與圖的邊或弧相關(guān)的數(shù)。與圖的邊或弧相關(guān)的數(shù)。網(wǎng)網(wǎng)u帶權(quán)的無(wú)向圖稱(chēng)為無(wú)向網(wǎng)；帶權(quán)的無(wú)向圖稱(chēng)為無(wú)向網(wǎng)；u帶權(quán)的有向圖稱(chēng)為有向網(wǎng)。帶權(quán)的有向圖稱(chēng)為有向網(wǎng)。有向網(wǎng)有向網(wǎng)無(wú)向網(wǎng)無(wú)向網(wǎng)10頂點(diǎn)的度（與樹(shù)中結(jié)點(diǎn)的度不同）頂點(diǎn)的度（與樹(shù)

7、中結(jié)點(diǎn)的度不同）u無(wú)向圖中，頂點(diǎn)的度是與每個(gè)頂點(diǎn)關(guān)聯(lián)的邊數(shù)，無(wú)向圖中，頂點(diǎn)的度是與每個(gè)頂點(diǎn)關(guān)聯(lián)的邊數(shù)，記作記作 td(v)。u有向圖中，頂點(diǎn)的度分成入度與出度有向圖中，頂點(diǎn)的度分成入度與出度入度：以該頂點(diǎn)為終頭的弧的數(shù)目，記為入度：以該頂點(diǎn)為終頭的弧的數(shù)目，記為 id(v)出度：以該頂點(diǎn)為始點(diǎn)的弧的數(shù)目，記為出度：以該頂點(diǎn)為始點(diǎn)的弧的數(shù)目，記為 od(v)一個(gè)頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和，即一個(gè)頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和，即td(v)=od(v)+id(v)niivtde1)(21evodvidniinii11)()(11自環(huán)自環(huán)u稱(chēng)邊稱(chēng)邊 (v, v) e(g) 或弧或弧 e(

8、g)為自環(huán)為自環(huán) 多重邊（或?。┒嘀剡叄ɑ蚧。﹗若在若在 g 中有兩條或兩條以上相同的邊或弧，稱(chēng)之中有兩條或兩條以上相同的邊或弧，稱(chēng)之為多重邊（或弧）為多重邊（或?。?2簡(jiǎn)單圖簡(jiǎn)單圖u圖中不含有自環(huán)和多重邊（或弧）的圖稱(chēng)為簡(jiǎn)單圖中不含有自環(huán)和多重邊（或?。┑膱D稱(chēng)為簡(jiǎn)單圖，否則稱(chēng)為非簡(jiǎn)單圖。圖，否則稱(chēng)為非簡(jiǎn)單圖。u本章只討論簡(jiǎn)單圖，即有兩類(lèi)圖形不在本章討論本章只討論簡(jiǎn)單圖，即有兩類(lèi)圖形不在本章討論之列之列13完全圖完全圖 u若有若有 n 個(gè)頂點(diǎn)的無(wú)向圖有個(gè)頂點(diǎn)的無(wú)向圖有 n(n-1)/2 條邊，則此圖為條邊，則此圖為完全無(wú)向圖。完全無(wú)向圖。u若有若有 n 個(gè)頂點(diǎn)的有向圖有個(gè)頂點(diǎn)的有向圖有n(n-

9、1) 條邊，則此圖為完條邊，則此圖為完全有向圖。全有向圖。稀疏圖（稀疏圖（sparse graph）u邊或弧很少的圖，通常邊數(shù)邊或弧很少的圖，通常邊數(shù) enlog2n稠密圖（稠密圖（dense graph）u無(wú)向圖中，邊數(shù)接近無(wú)向圖中，邊數(shù)接近n(n-1)/2 ；u有向圖中，弧數(shù)接近有向圖中，弧數(shù)接近n(n-1)。14路徑路徑u在圖在圖 g 中，頂點(diǎn)序列中，頂點(diǎn)序列(vi1, vi2, ,vim) 且且(vij,vij+1) e 或或 e ，j=1, 2, , m-1，則稱(chēng)此序列為，則稱(chēng)此序列為從頂點(diǎn)從頂點(diǎn) vi1 到頂點(diǎn)到頂點(diǎn)vim的一條路徑。的一條路徑。u頂點(diǎn)頂點(diǎn) vi1 稱(chēng)為始點(diǎn)；頂點(diǎn)稱(chēng)

10、為始點(diǎn)；頂點(diǎn)vim 稱(chēng)為終點(diǎn)。稱(chēng)為終點(diǎn)?；芈坊芈穟始點(diǎn)和終點(diǎn)相同的路徑。始點(diǎn)和終點(diǎn)相同的路徑。15簡(jiǎn)單路徑簡(jiǎn)單路徑u序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路簡(jiǎn)單回路u始點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑。始點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑。16路徑長(zhǎng)度路徑長(zhǎng)度 u無(wú)權(quán)圖的路徑長(zhǎng)度是指此路徑上邊（或弧）的條無(wú)權(quán)圖的路徑長(zhǎng)度是指此路徑上邊（或?。┑臈l數(shù)。數(shù)。u帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊（或?。┑臋?quán)帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊（或弧）的權(quán)之和。之和。17子圖子圖u已知圖已知圖 g(v, e) 和圖和圖 g(v, e)。若。若vv 且且 ee，則稱(chēng)，則稱(chēng) g 為為 g 的子圖。的子圖。18連通

11、圖連通圖u在無(wú)向圖中，在無(wú)向圖中， 若從頂點(diǎn)若從頂點(diǎn)v1到頂點(diǎn)到頂點(diǎn)v2有路徑，則稱(chēng)有路徑，則稱(chēng)頂點(diǎn)頂點(diǎn)v1與與v2是連通的。是連通的。u圖中任意兩個(gè)頂點(diǎn)都連通的無(wú)向圖稱(chēng)為連通圖。圖中任意兩個(gè)頂點(diǎn)都連通的無(wú)向圖稱(chēng)為連通圖。連通分量連通分量u非連通圖中極大連通子圖稱(chēng)做連通分量。非連通圖中極大連通子圖稱(chēng)做連通分量。1.1.含有極大含有極大頂點(diǎn)頂點(diǎn)數(shù)；數(shù)；2.2.依附于這些頂點(diǎn)的所有依附于這些頂點(diǎn)的所有邊邊。19例例abcdefgijlhmkabcdehmfgijlk3個(gè)連通分量個(gè)連通分量 20強(qiáng)連通圖與強(qiáng)連通分量強(qiáng)連通圖與強(qiáng)連通分量u在有向圖中，若對(duì)于每一對(duì)頂點(diǎn)在有向圖中，若對(duì)于每一對(duì)頂點(diǎn) vi

12、和和 vj，都存在，都存在一條從一條從 vi 到到 vj 和從和從 vj 到到 vi 的有向路徑，則稱(chēng)此圖的有向路徑，則稱(chēng)此圖是強(qiáng)連通圖。是強(qiáng)連通圖。u非強(qiáng)連通圖的極大強(qiáng)連通子圖稱(chēng)做強(qiáng)連通分量。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱(chēng)做強(qiáng)連通分量。v1v2v3v4v1v3v4v22個(gè)強(qiáng)連通分量個(gè)強(qiáng)連通分量 21生成樹(shù)生成樹(shù)un個(gè)頂點(diǎn)的連通圖的生成樹(shù)是包含圖中全部個(gè)頂點(diǎn)的連通圖的生成樹(shù)是包含圖中全部 n 個(gè)頂個(gè)頂點(diǎn)的一個(gè)極小連通子圖；點(diǎn)的一個(gè)極小連通子圖；abcdehm無(wú)向圖無(wú)向圖g abcdehm無(wú)向圖無(wú)向圖g的生成樹(shù)的生成樹(shù) 多多構(gòu)成回路構(gòu)成回路少少不連通不連通含有含有n-1條邊條邊22生成森林生成森林

13、u由若干棵生成樹(shù)組成，含全部頂點(diǎn)，但構(gòu)成這些由若干棵生成樹(shù)組成，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊是最少的。樹(shù)的邊是最少的。fgijlk生成森林生成森林abcdefgijlhmk無(wú)向圖無(wú)向圖gabcdehm23是否可以采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)圖是否可以采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)圖?u圖的特點(diǎn)：頂點(diǎn)之間的關(guān)系是圖的特點(diǎn)：頂點(diǎn)之間的關(guān)系是m:n，即任何兩個(gè)頂，即任何兩個(gè)頂點(diǎn)之間都可能存在關(guān)系（邊），無(wú)法通過(guò)存儲(chǔ)位點(diǎn)之間都可能存在關(guān)系（邊），無(wú)法通過(guò)存儲(chǔ)位置表示這種任意的邏輯關(guān)系，所以，圖置表示這種任意的邏輯關(guān)系，所以，圖無(wú)法無(wú)法采用采用順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)。如何存儲(chǔ)圖如何存儲(chǔ)圖?u考慮圖的定義，圖是由頂點(diǎn)和

14、邊組成的，分別考考慮圖的定義，圖是由頂點(diǎn)和邊組成的，分別考慮如何存儲(chǔ)頂點(diǎn)、如何存儲(chǔ)邊。慮如何存儲(chǔ)頂點(diǎn)、如何存儲(chǔ)邊。24鄰接矩陣（鄰接矩陣（adjacency matrix）u在圖的鄰接矩陣表示中在圖的鄰接矩陣表示中有一個(gè)記錄各個(gè)頂點(diǎn)信息的有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表頂點(diǎn)表（一維數(shù)組）（一維數(shù)組）還有一個(gè)表示各個(gè)頂點(diǎn)之間還有一個(gè)表示各個(gè)頂點(diǎn)之間鄰接鄰接關(guān)系的關(guān)系的鄰接矩陣鄰接矩陣u設(shè)圖設(shè)圖 g = (v, e) 是一個(gè)有是一個(gè)有 n 個(gè)頂點(diǎn)的圖，則個(gè)頂點(diǎn)的圖，則 g 的的鄰接矩陣定義如下鄰接矩陣定義如下 aij= 1 若若(vi, vj)e 或或 e 0 反之反之25u例，無(wú)向圖的鄰接矩陣?yán)?/p>

15、無(wú)向圖的鄰接矩陣v1v3v4v2v1 v2 v3 v4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=v1 v2 v3 v4v1v2v3v426u例，有向圖的鄰接矩陣?yán)?，有向圖的鄰接矩陣v1v2v3v4v1 v2 v3 v4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=v1 v2 v3 v4v1v2v3v427u從鄰接矩陣中可以反映圖的許多特征從鄰接矩陣中可以反映圖的許多特征無(wú)向圖無(wú)向圖l(1) 對(duì)稱(chēng)矩陣（可采用壓縮存儲(chǔ)）；對(duì)稱(chēng)矩陣（可采用壓縮存儲(chǔ)）；l(2) 每一行（或列）每一行（或列）1的個(gè)數(shù)是該頂點(diǎn)的度；的個(gè)數(shù)

16、是該頂點(diǎn)的度；l(3) 主對(duì)角線(xiàn)全為主對(duì)角線(xiàn)全為0（簡(jiǎn)單圖）。（簡(jiǎn)單圖）。有向圖有向圖l(1) 每一行每一行1的個(gè)數(shù)是該頂點(diǎn)的出度；的個(gè)數(shù)是該頂點(diǎn)的出度； l(2) 每一列每一列1的個(gè)數(shù)是該頂點(diǎn)的入度；的個(gè)數(shù)是該頂點(diǎn)的入度；l(3) 主對(duì)角線(xiàn)全為主對(duì)角線(xiàn)全為0（簡(jiǎn)單圖）；（簡(jiǎn)單圖）；l(4) 有向圖的鄰接矩陣不一定對(duì)稱(chēng)。有向圖的鄰接矩陣不一定對(duì)稱(chēng)。28u帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣aij 0 i=j 其它其它 wij 若若(vi, vj)e 或或 e 29u用鄰接矩陣表示的圖的類(lèi)的定義用鄰接矩陣表示的圖的類(lèi)的定義 class adjmatrix / 非帶權(quán)圖非帶權(quán)圖 int n； / 頂點(diǎn)

17、的個(gè)數(shù)頂點(diǎn)的個(gè)數(shù) int matrixmaxsize maxsize； / 鄰接矩陣鄰接矩陣 public: adjmatrix(int m) n=m； ; / adjmatrix class adjmatrix / 帶權(quán)圖帶權(quán)圖 const int infinite=； int n； /頂點(diǎn)的個(gè)數(shù)頂點(diǎn)的個(gè)數(shù) float matrixmaxsizemaxsize； / 鄰接矩陣鄰接矩陣 public: adjmatrix(int m) n=m； ; / adjmatrix30class adjgraph adjmatrix *adj；datatype *elem； public:adjgrap

18、h(int m) adj=new adjmatrix(m)； elm=new dataset(m)；void creategraph(); / 建立一個(gè)圖建立一個(gè)圖g的鄰接矩陣的鄰接矩陣matrixint locatevex(v) ; / 確定圖確定圖g中頂點(diǎn)中頂點(diǎn)v在頂點(diǎn)中的位置在頂點(diǎn)中的位置 datatype getvex(v); / 得到圖得到圖g中頂點(diǎn)中頂點(diǎn)v的值的值int firstadjvex(v); / 確定圖確定圖g中頂點(diǎn)中頂點(diǎn)v的第一個(gè)鄰接點(diǎn)的第一個(gè)鄰接點(diǎn) int nextadjvex(v,w);/ 確定圖確定圖g中頂點(diǎn)中頂點(diǎn)v相對(duì)于相對(duì)于w的下一個(gè)的下一個(gè)鄰接點(diǎn)鄰接點(diǎn) vo

19、id dfstraverse(int v)；/圖圖的深度優(yōu)先遍歷的深度優(yōu)先遍歷 void bfstraverse(int v)；/圖圖的的廣度優(yōu)先遍歷廣度優(yōu)先遍歷; / adjgraph31u鄰接矩陣的優(yōu)點(diǎn)鄰接矩陣的優(yōu)點(diǎn)容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。u鄰接矩陣的缺點(diǎn)鄰接矩陣的缺點(diǎn)n 個(gè)頂點(diǎn)需要個(gè)頂點(diǎn)需要 nn 個(gè)單元存儲(chǔ)邊；空間效率為個(gè)單元存儲(chǔ)邊；空間效率為o(n2)。 對(duì)稀疏圖而言尤其浪費(fèi)空間。對(duì)稀疏圖而言尤其浪費(fèi)空間。32鄰接表（鄰接表（adjacenc

20、y list）表示法）表示法u無(wú)向圖的鄰接表無(wú)向圖的鄰接表為每個(gè)頂點(diǎn)建立一個(gè)單鏈表為每個(gè)頂點(diǎn)建立一個(gè)單鏈表第第 i 個(gè)單鏈表中的結(jié)點(diǎn)表示與頂點(diǎn)個(gè)單鏈表中的結(jié)點(diǎn)表示與頂點(diǎn) vi 所關(guān)聯(lián)的所有邊所關(guān)聯(lián)的所有邊aedcbacbed10011243243404321注：鄰接表不唯一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。注：鄰接表不唯一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。33問(wèn)題問(wèn)題l在無(wú)向圖的鄰接表中，如何求每個(gè)頂點(diǎn)的度？在無(wú)向圖的鄰接表中，如何求每個(gè)頂點(diǎn)的度？ 第第 i 個(gè)鏈表中的邊結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)個(gè)鏈表中的邊結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn) i 的度的度l若頂點(diǎn)數(shù)為若頂點(diǎn)數(shù)為 n，邊數(shù)為，邊數(shù)為 e 時(shí)，則在無(wú)向圖的鄰接表

21、中時(shí)，則在無(wú)向圖的鄰接表中共需多少個(gè)結(jié)點(diǎn)？共需多少個(gè)結(jié)點(diǎn)？ n 個(gè)頂點(diǎn)結(jié)點(diǎn)，個(gè)頂點(diǎn)結(jié)點(diǎn)，2e 個(gè)邊結(jié)點(diǎn)個(gè)邊結(jié)點(diǎn) 34u有向圖的鄰接表和逆鄰接表有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第在有向圖的鄰接表中，第 i 個(gè)單鏈表鏈接的弧都是頂點(diǎn)個(gè)單鏈表鏈接的弧都是頂點(diǎn)vi發(fā)出的，也稱(chēng)做發(fā)出的，也稱(chēng)做出邊表出邊表。在有向圖的逆鄰接表中，第在有向圖的逆鄰接表中，第 i 個(gè)單鏈表鏈接的弧都是進(jìn)個(gè)單鏈表鏈接的弧都是進(jìn)入頂點(diǎn)入頂點(diǎn) vi 的，也稱(chēng)做的，也稱(chēng)做入邊表入邊表。v1v2v3v4v4v3v2v12301v4v3v2v13020鄰接表鄰接表逆鄰接表逆鄰接表01230123 用鄰接表或逆鄰接表表示有向圖

22、時(shí)，只需用鄰接表或逆鄰接表表示有向圖時(shí)，只需 n 個(gè)頂點(diǎn)結(jié)點(diǎn)，個(gè)頂點(diǎn)結(jié)點(diǎn)，e 個(gè)弧結(jié)點(diǎn)。個(gè)弧結(jié)點(diǎn)。35data：結(jié)：結(jié)點(diǎn)的數(shù)據(jù)域，保存點(diǎn)的數(shù)據(jù)域，保存頂頂點(diǎn)的數(shù)據(jù)值。點(diǎn)的數(shù)據(jù)值。firstout：結(jié)點(diǎn)的指針域，指向與該結(jié)點(diǎn)的指針域，指向與該頂頂點(diǎn)相關(guān)聯(lián)的第一條邊點(diǎn)相關(guān)聯(lián)的第一條邊 （?。ɑ。┑牡刂返牡刂繁眍^結(jié)點(diǎn)表頭結(jié)點(diǎn)datafirstoutadjvexlink邊邊/弧結(jié)點(diǎn)弧結(jié)點(diǎn)adjvex：該邊或弧所指向的頂點(diǎn)的序號(hào)：該邊或弧所指向的頂點(diǎn)的序號(hào)link：指向下一條邊或弧的指針：指向下一條邊或弧的指針adjvexlinkdatafirstout36u網(wǎng)（帶權(quán)圖）的鄰接表網(wǎng)（帶權(quán)圖）的鄰接表邊

23、邊/弧結(jié)點(diǎn)弧結(jié)點(diǎn)adjvexcostlink37u鄰接表表示的圖的類(lèi)定義鄰接表表示的圖的類(lèi)定義class earcnode /邊邊(或弧或弧)結(jié)點(diǎn)結(jié)點(diǎn) int adjvex； / 該邊或弧所指向的頂點(diǎn)的序號(hào)該邊或弧所指向的頂點(diǎn)的序號(hào)earcnode *link； / 指向下一條邊或弧的指針指向下一條邊或弧的指針 public:earcnode(int adj) adjvex=adj; link=null; friend class linkgraph; / earcnodeclass vnode / 表頭結(jié)點(diǎn)表頭結(jié)點(diǎn) datatype data； / 頂點(diǎn)的信息頂點(diǎn)的信息 earcnode *

24、firstout；/ 指向與該頂點(diǎn)關(guān)聯(lián)的第一條邊指向與該頂點(diǎn)關(guān)聯(lián)的第一條邊(弧弧) public: vnode (datatype e) data=e ; f irstout=null; friend class linkgraph; / vnode38class linkgraph /鄰接表鄰接表 int n； / 頂點(diǎn)的個(gè)數(shù)頂點(diǎn)的個(gè)數(shù) vnode gheadmaxsize； / 鄰接表鄰接表 public: linkgraph(int m) n=m； void creategraph( ) ； / 建立圖建立圖g int locatevex(v) ； / 得到頂點(diǎn)得到頂點(diǎn)v在圖中的序號(hào)在圖

25、中的序號(hào) datatype getvex(v) ； / 得到頂點(diǎn)得到頂點(diǎn)v的值的值 int firstadjvex(v) ； / 得到頂點(diǎn)得到頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)的第一個(gè)鄰接頂點(diǎn) int nextadjvex(v, w); / 確定圖確定圖g中頂點(diǎn)中頂點(diǎn)v相對(duì)于相對(duì)于w的下一的下一個(gè)鄰接點(diǎn)個(gè)鄰接點(diǎn) void dfstraverse(int v)； / 圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷 void bfstraverse(int v)； / 圖的廣度優(yōu)先遍歷圖的廣度優(yōu)先遍歷; / linkgraph39u圖的操作在鄰接表的上的實(shí)現(xiàn)圖的操作在鄰接表的上的實(shí)現(xiàn) int firstadjvex (in

26、t v) return gheadv-firstout.adjvex； / firstadjvex int nextadjvex(int v，int w) p=gheadv-firstout； while (p & p-adjvex!=w) p=p-link； if (!p | !p-link) return 0； else return p-link-adjvex； / nextadjvex40討論：鄰接表與鄰接矩陣的比較討論：鄰接表與鄰接矩陣的比較u聯(lián)系聯(lián)系都可以用來(lái)存儲(chǔ)有向圖和無(wú)向圖；都可以用來(lái)存儲(chǔ)有向圖和無(wú)向圖；鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)鄰接表中每個(gè)鏈表對(duì)

27、應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。41u區(qū)別區(qū)別對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。號(hào)無(wú)關(guān)）。鄰接矩陣的空間復(fù)雜度為鄰接矩陣的空間復(fù)雜度為o(n2)，而鄰接表的空間復(fù)雜度，而鄰接表的空間復(fù)雜度為為o(n+e)。鄰接矩陣多用于稠密圖的存儲(chǔ)（鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近接近n(n-1)/2）；而鄰）；而鄰接表多用于稀疏圖的存儲(chǔ)（接表多用于稀疏圖的存儲(chǔ)（en2）。）。42

28、圖的遍歷圖的遍歷u從圖中某一頂點(diǎn)出發(fā)，按照某種搜索路徑訪(fǎng)問(wèn)圖從圖中某一頂點(diǎn)出發(fā)，按照某種搜索路徑訪(fǎng)問(wèn)圖中所有的頂點(diǎn)，使得每個(gè)頂點(diǎn)被訪(fǎng)問(wèn)一次且僅被中所有的頂點(diǎn)，使得每個(gè)頂點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。訪(fǎng)問(wèn)一次。圖的遍歷操作要解決的關(guān)鍵問(wèn)題圖的遍歷操作要解決的關(guān)鍵問(wèn)題u在圖中，如何選取遍歷的起始頂點(diǎn)？在圖中，如何選取遍歷的起始頂點(diǎn)？ 解決方案：解決方案：從編號(hào)小的頂點(diǎn)開(kāi)始從編號(hào)小的頂點(diǎn)開(kāi)始 43u從某個(gè)起點(diǎn)開(kāi)始可能到達(dá)不了所有其它頂點(diǎn)，怎從某個(gè)起點(diǎn)開(kāi)始可能到達(dá)不了所有其它頂點(diǎn)，怎么辦？么辦？ 解決方案：解決方案：多次調(diào)用從某頂點(diǎn)出發(fā)遍歷圖的算法。多次調(diào)用從某頂點(diǎn)出發(fā)遍歷圖的算法。u圖中可能存在回路，

29、某些頂點(diǎn)可能會(huì)被重復(fù)訪(fǎng)問(wèn)，圖中可能存在回路，某些頂點(diǎn)可能會(huì)被重復(fù)訪(fǎng)問(wèn)，如何避免遍歷因回路而陷入死循環(huán)。如何避免遍歷因回路而陷入死循環(huán)。 解決方案：解決方案：附設(shè)訪(fǎng)問(wèn)標(biāo)志數(shù)組附設(shè)訪(fǎng)問(wèn)標(biāo)志數(shù)組visitedn u在圖中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)在圖中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這樣的頂點(diǎn)訪(fǎng)問(wèn)后，如何選取下一個(gè)要訪(fǎng)問(wèn)的頂這樣的頂點(diǎn)訪(fǎng)問(wèn)后，如何選取下一個(gè)要訪(fǎng)問(wèn)的頂點(diǎn)？點(diǎn)？ 解決方案：解決方案：深度深度優(yōu)先遍歷和優(yōu)先遍歷和廣度廣度優(yōu)先遍歷優(yōu)先遍歷44深度優(yōu)先遍歷深度優(yōu)先遍歷dfs（depth first search）dfs算法思想算法思想u從圖中某個(gè)頂點(diǎn)從圖中某個(gè)頂點(diǎn)v0 出發(fā)，訪(fǎng)問(wèn)

30、此頂點(diǎn)，然后依次出發(fā)，訪(fǎng)問(wèn)此頂點(diǎn)，然后依次從從v0的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至遍歷圖，直至v0 的所有鄰接點(diǎn)都被訪(fǎng)問(wèn)到。的所有鄰接點(diǎn)都被訪(fǎng)問(wèn)到。u若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。45例例46u從訪(fǎng)問(wèn)圖中某一起始點(diǎn)從訪(fǎng)問(wèn)圖中某一起始點(diǎn) v 開(kāi)始，由開(kāi)始，由 v 出發(fā)，訪(fǎng)問(wèn)它出發(fā)，訪(fǎng)問(wèn)它的第一鄰接點(diǎn)的第一鄰接點(diǎn) w1；再?gòu)模辉購(gòu)?w1 出發(fā)，訪(fǎng)問(wèn)

31、與出發(fā)，訪(fǎng)問(wèn)與 w1鄰接鄰接但還沒(méi)有訪(fǎng)問(wèn)過(guò)的頂點(diǎn)但還沒(méi)有訪(fǎng)問(wèn)過(guò)的頂點(diǎn) w2；然后再?gòu)模蝗缓笤購(gòu)?w2 出發(fā)，出發(fā)，進(jìn)行類(lèi)似的訪(fǎng)問(wèn)，進(jìn)行類(lèi)似的訪(fǎng)問(wèn)， 如此進(jìn)行下去，直到某一頂如此進(jìn)行下去，直到某一頂點(diǎn)所有的鄰接點(diǎn)都被訪(fǎng)問(wèn)完。點(diǎn)所有的鄰接點(diǎn)都被訪(fǎng)問(wèn)完。u退回到上一步剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，看是否還有其它退回到上一步剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪(fǎng)問(wèn)的鄰接點(diǎn)。如果有，則訪(fǎng)問(wèn)此頂點(diǎn)，沒(méi)有被訪(fǎng)問(wèn)的鄰接點(diǎn)。如果有，則訪(fǎng)問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類(lèi)似的訪(fǎng)問(wèn)；之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類(lèi)似的訪(fǎng)問(wèn)；如果沒(méi)有，就再退回一步進(jìn)行搜索。如果沒(méi)有，就再退回一步進(jìn)行搜索。u重復(fù)上述過(guò)程，直到連通圖中所有頂

32、點(diǎn)都被訪(fǎng)問(wèn)重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。過(guò)為止。47連通圖的深度優(yōu)先遍歷算法連通圖的深度優(yōu)先遍歷算法void dfstraverse( ) /深度優(yōu)先求圖的連通分量深度優(yōu)先求圖的連通分量 int visitedn； /設(shè)置訪(fǎng)問(wèn)標(biāo)志數(shù)組設(shè)置訪(fǎng)問(wèn)標(biāo)志數(shù)組 for (v=0; vn; v+) visitedv=0； /初始化訪(fǎng)問(wèn)標(biāo)志數(shù)組初始化訪(fǎng)問(wèn)標(biāo)志數(shù)組 for (v=0; vn; v+) if (!visitedv) dfs (v)；/每次從尚未訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出發(fā)每次從尚未訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出發(fā)/ dfstraversevoid dfs (int v) /從頂點(diǎn)從頂點(diǎn)v出發(fā)訪(fǎng)問(wèn)包含該頂

33、點(diǎn)的最大連通子圖中的所有頂點(diǎn)出發(fā)訪(fǎng)問(wèn)包含該頂點(diǎn)的最大連通子圖中的所有頂點(diǎn) visitedv=1； visit(v)； for (w=firstadjvex(v); w; w=nextadjvex(v, w) if (!visitedw) dfs(w)； / dfs48例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。v1v3v2v4v5v6v7v8深一層遞歸深一層遞歸遞歸返回遞歸返回 v1遍歷序列：遍歷序列： v2 v4 v549例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。v1v3v2v4v5v6v7v8深一層遞歸深一層

34、遞歸遞歸返回遞歸返回 v1遍歷序列：遍歷序列： v2 v4 v850例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。v1v3v2v4v5v6v7v8深一層遞歸深一層遞歸遞歸返回遞歸返回 v1遍歷序列：遍歷序列： v2 v451例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。v1v3v2v4v5v6v7v8深一層遞歸深一層遞歸遞歸返回遞歸返回 v1遍歷序列：遍歷序列： v7 v3 v652u不同存儲(chǔ)結(jié)構(gòu)下的不同存儲(chǔ)結(jié)構(gòu)下的dfs實(shí)現(xiàn)實(shí)現(xiàn)圖以鄰接矩陣存儲(chǔ)圖以鄰接矩陣存儲(chǔ) void dfs (int v) visitedv=1;

35、 visit(v); for (w=0; w0) if (!visitedw) dfs(w); / dfs圖以鄰接表存儲(chǔ)圖以鄰接表存儲(chǔ)void dfs(int v) visitedv=1; p=gheadv-firstout; while (p) w=p-adjvex; if (!visitedw ) dfs(w); p=p-link; / dfs53例例v1v2v4v5v3v7v6v8例例01231342data firstout 1 6 7 2adjvex link45 5 3 716785676深度遍歷：深度遍歷：v1v3 v7 v6 v2 v4 v8 v554算法分析算法分析u圖中有圖

36、中有 n 個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e 條邊。條邊。u如果用鄰接矩陣存儲(chǔ)圖，則查找每一個(gè)頂點(diǎn)的所如果用鄰接矩陣存儲(chǔ)圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為有的邊，所需時(shí)間為o(n)，則遍歷圖中所有的頂點(diǎn)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為所需的時(shí)間為o(n2)。u如果用鄰接表存儲(chǔ)圖，在每一個(gè)單鏈如果用鄰接表存儲(chǔ)圖，在每一個(gè)單鏈 表中可以找表中可以找到某個(gè)頂點(diǎn)到某個(gè)頂點(diǎn) v 的所有鄰接頂點(diǎn)的所有鄰接頂點(diǎn) w。由于總共有。由于總共有 2e 個(gè)邊結(jié)點(diǎn)個(gè)邊結(jié)點(diǎn)(無(wú)向圖無(wú)向圖)，所以?huà)呙柽叺臅r(shí)間為，所以?huà)呙柽叺臅r(shí)間為o(e)。而。而且對(duì)所有頂點(diǎn)遞歸訪(fǎng)問(wèn)且對(duì)所有頂點(diǎn)遞歸訪(fǎng)問(wèn)1次，所以遍歷圖的時(shí)間復(fù)次，所以遍歷圖的時(shí)

37、間復(fù)雜性為雜性為o(n+e)。55廣度優(yōu)先遍歷廣度優(yōu)先遍歷bfs（breadth first search）思路思路u在訪(fǎng)問(wèn)了起始頂點(diǎn)在訪(fǎng)問(wèn)了起始頂點(diǎn) v 之后，由之后，由 v 出發(fā)，依次訪(fǎng)問(wèn)出發(fā)，依次訪(fǎng)問(wèn) v 的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn) w1, w2, , wt，然后，然后再順序訪(fǎng)問(wèn)再順序訪(fǎng)問(wèn) w1, w2, , wt 的所有未被訪(fǎng)問(wèn)過(guò)的鄰的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)。再?gòu)倪@些訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出發(fā)，再訪(fǎng)問(wèn)它們接點(diǎn)。再?gòu)倪@些訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出發(fā)，再訪(fǎng)問(wèn)它們的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)， ，如此重復(fù)，直，如此重復(fù)，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)完為止。到圖中所有頂點(diǎn)都被

38、訪(fǎng)問(wèn)完為止。56例例 57說(shuō)明說(shuō)明u廣度優(yōu)先遍歷是一種分層的搜索過(guò)程，每向前走廣度優(yōu)先遍歷是一種分層的搜索過(guò)程，每向前走一步可能訪(fǎng)問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣一步可能訪(fǎng)問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先遍歷不是一個(gè)有往回退的情況。因此，廣度優(yōu)先遍歷不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。遞歸的過(guò)程，其算法也不是遞歸的。u為了實(shí)現(xiàn)逐層訪(fǎng)問(wèn)，算法中使用了一個(gè)隊(duì)列，以為了實(shí)現(xiàn)逐層訪(fǎng)問(wèn)，算法中使用了一個(gè)隊(duì)列，以記憶正在訪(fǎng)問(wèn)的頂點(diǎn)，以便向下一層訪(fǎng)問(wèn)。記憶正在訪(fǎng)問(wèn)的頂點(diǎn)，以便向下一層訪(fǎng)問(wèn)。u與深度優(yōu)先遍歷過(guò)程一樣，為避免重復(fù)訪(fǎng)問(wèn)，需與深度優(yōu)先遍歷過(guò)程一樣，為避免重復(fù)訪(fǎng)問(wèn)，需

39、要一個(gè)輔助數(shù)組要一個(gè)輔助數(shù)組 visited n，對(duì)被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)加，對(duì)被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)加以標(biāo)記。以標(biāo)記。58算法思想算法思想u1）清隊(duì)列）清隊(duì)列q；u2）對(duì)出發(fā)頂點(diǎn)）對(duì)出發(fā)頂點(diǎn) v 做做v 入隊(duì)；標(biāo)記入隊(duì)；標(biāo)記 v；u3）當(dāng)）當(dāng) q 不空反復(fù)做：不空反復(fù)做：出隊(duì)頭元素到出隊(duì)頭元素到 u；訪(fǎng)問(wèn)訪(fǎng)問(wèn) u；將將 u 的每個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)的每個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn) w 入隊(duì)；標(biāo)記入隊(duì)；標(biāo)記 w。59廣度優(yōu)先搜索算法廣度優(yōu)先搜索算法void bfs (int v) /廣度優(yōu)先求圖的連通分量廣度優(yōu)先求圖的連通分量 q=new queue( )； /清隊(duì)列清隊(duì)列q q.enter(v)； /每次從尚未訪(fǎng)問(wèn)過(guò)的

40、頂點(diǎn)中選取一個(gè)頂點(diǎn)每次從尚未訪(fǎng)問(wèn)過(guò)的頂點(diǎn)中選取一個(gè)頂點(diǎn)v visitedv=1； /標(biāo)記標(biāo)記v while (!q.empty() /q不空不空 u=q.leave()； /出隊(duì)頭元素到出隊(duì)頭元素到u visited(u)； /訪(fǎng)問(wèn)訪(fǎng)問(wèn)u for (w=firstadjvex(u); w; w=nextadjvex(u, w) if (!visitedw) q.enter(w)； /將將u的每個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)的每個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)w 入隊(duì)入隊(duì) visitedw=1； / bfs60ubfs從出發(fā)點(diǎn)只能遍歷一個(gè)連通分量，若對(duì)任意圖從出發(fā)點(diǎn)只能遍歷一個(gè)連通分量，若對(duì)任意圖的遍歷需要對(duì)每個(gè)分量中一

41、個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)為的遍歷需要對(duì)每個(gè)分量中一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行出發(fā)點(diǎn)進(jìn)行bfs遍歷。遍歷。 void bfstraverse() /廣度優(yōu)先求圖的連通分量廣度優(yōu)先求圖的連通分量 int visitedn； /設(shè)置訪(fǎng)問(wèn)標(biāo)志數(shù)組設(shè)置訪(fǎng)問(wèn)標(biāo)志數(shù)組 for (v=0；vn；v+) visitedv=0； /初始化訪(fǎng)問(wèn)標(biāo)志初始化訪(fǎng)問(wèn)標(biāo)志 for (v=0；vn；v+) if (!visitedv) bfs( v)； / bfstraverse61例，廣度優(yōu)先遍歷序列，入隊(duì)序列，出隊(duì)序列。例，廣度優(yōu)先遍歷序列，入隊(duì)序列，出隊(duì)序列。v1v3v2v4v5v6v7v8遍歷序列：遍歷序列：v5v6v7v8

42、v4v1v2v362算法分析算法分析u如果用鄰接矩陣存儲(chǔ)圖，則對(duì)于每一個(gè)被訪(fǎng)問(wèn)過(guò)如果用鄰接矩陣存儲(chǔ)圖，則對(duì)于每一個(gè)被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的 n 個(gè)元素，總的時(shí)個(gè)元素，總的時(shí)間代價(jià)為間代價(jià)為o(n2)。u如果用鄰接表存儲(chǔ)圖，則循環(huán)的總時(shí)間代價(jià)為如果用鄰接表存儲(chǔ)圖，則循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + + dn-1 = o(e)，其中的，其中的 di 是頂點(diǎn)是頂點(diǎn) i 的的度。而且對(duì)所有頂點(diǎn)訪(fǎng)問(wèn)度。而且對(duì)所有頂點(diǎn)訪(fǎng)問(wèn)1次，所以遍歷圖的時(shí)間次，所以遍歷圖的時(shí)間復(fù)雜性為復(fù)雜性為o(n+e)。63dfs 與與 bfs 之比較之比較u空間復(fù)雜度相同，都是空間復(fù)雜度相

43、同，都是o(n)（借用了堆?；蜿?duì)列）；（借用了堆?；蜿?duì)列）；u時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無(wú)關(guān)。有關(guān)，而與搜索路徑無(wú)關(guān)。64生成樹(shù)生成樹(shù)u包含連通無(wú)向圖中全部頂點(diǎn)的極小連通子圖（包含連通無(wú)向圖中全部頂點(diǎn)的極小連通子圖（n 個(gè)個(gè)頂點(diǎn)、頂點(diǎn)、n-1 條邊）條邊）u一個(gè)連通圖的生成樹(shù)不唯一一個(gè)連通圖的生成樹(shù)不唯一使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)u對(duì)于非連通圖，通過(guò)圖的遍歷，得到的是生成森對(duì)于非

44、連通圖，通過(guò)圖的遍歷，得到的是生成森林林65例例（a）深度優(yōu)先生成樹(shù)深度優(yōu)先生成樹(shù) （b） 廣度優(yōu)先生成樹(shù)廣度優(yōu)先生成樹(shù)v1v3v2v4v5v6v7v8v1v3v2v4v5v6v7v866最小生成樹(shù)最小生成樹(shù)mst（minimum-cost spanning tree）u連通無(wú)向網(wǎng)中連通無(wú)向網(wǎng)中邊權(quán)之和邊權(quán)之和最小的生成樹(shù)最小的生成樹(shù)最小生成樹(shù)最小生成樹(shù)mst的典型用途的典型用途u假設(shè)在假設(shè)在 7 個(gè)城市之間要建立通信網(wǎng)絡(luò)線(xiàn)，要求使得個(gè)城市之間要建立通信網(wǎng)絡(luò)線(xiàn)，要求使得每個(gè)城市之間連通且費(fèi)用最少。每個(gè)城市之間連通且費(fèi)用最少。數(shù)學(xué)模型數(shù)學(xué)模型連通網(wǎng)連通網(wǎng)表示表示7個(gè)城市間的通信網(wǎng)個(gè)城市間的通信網(wǎng)

45、l頂點(diǎn)頂點(diǎn)表示城市表示城市l(wèi)邊邊表示城市間的通信線(xiàn)路表示城市間的通信線(xiàn)路l邊的權(quán)值邊的權(quán)值表示線(xiàn)路的經(jīng)濟(jì)代價(jià)表示線(xiàn)路的經(jīng)濟(jì)代價(jià)281234567101614181225242267構(gòu)造最小生成樹(shù)的準(zhǔn)則構(gòu)造最小生成樹(shù)的準(zhǔn)則u必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹(shù)；必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹(shù)；u必須使用且僅使用必須使用且僅使用 n-1 條邊來(lái)連接網(wǎng)絡(luò)中的條邊來(lái)連接網(wǎng)絡(luò)中的 n 個(gè)頂個(gè)頂點(diǎn)；點(diǎn)；u不能使用產(chǎn)生回路的邊。不能使用產(chǎn)生回路的邊。求一個(gè)連通無(wú)向網(wǎng)中最小生成樹(shù)的方法求一個(gè)連通無(wú)向網(wǎng)中最小生成樹(shù)的方法uprim 算法算法ukruskal 算法算法都是利用都是利用mst的性質(zhì)的性質(zhì)構(gòu)

46、造最小生成樹(shù)構(gòu)造最小生成樹(shù)68最小生成樹(shù)的性質(zhì)最小生成樹(shù)的性質(zhì)u若集合若集合 u 是集合是集合 v 的一個(gè)非空子集，若的一個(gè)非空子集，若 (u, v) 是是一條具有最小權(quán)值的邊，其中一條具有最小權(quán)值的邊，其中 u u，v v-u；則：；則：(u, v) 必在最小生成樹(shù)上。必在最小生成樹(shù)上。uv-u69prim 算法算法uprim 算法的基本思想算法的基本思想設(shè)連通設(shè)連通 n= v, e ，t 是是 n 的最小生成樹(shù)中邊的集合，的最小生成樹(shù)中邊的集合， u 是生成樹(shù)的頂點(diǎn)集合。是生成樹(shù)的頂點(diǎn)集合。（1） t= ，u= u （ u 為任一頂點(diǎn)）；為任一頂點(diǎn)）； （2）在所有）在所有 uu，vv-u

47、 的邊的邊 (u, v)e 中找一條代中找一條代價(jià)最小的邊價(jià)最小的邊 (u, v) 加入集合加入集合 t 中，同時(shí)中，同時(shí) v 加入加入 u； （3）重復(fù)（）重復(fù)（2），直到），直到 u=v 為止。為止。70u例例0126345281612222510251418t = u = 0 min10, 28=10(0,5), 5min25, 28=25, (5,4), 4min28, 25, 22=22, (4,3), 3min28, 25, 18, 12=12, (3,2), 2min28, 25, 18, 16=16, (2,1), 1min25, 18, 14=14, (1,6), 6 u=v

48、，算法結(jié)束，算法結(jié)束71uprim 算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)圖的存儲(chǔ)：鄰接矩陣圖的存儲(chǔ)：鄰接矩陣在構(gòu)造過(guò)程中，還設(shè)置了一個(gè)輔助數(shù)組在構(gòu)造過(guò)程中，還設(shè)置了一個(gè)輔助數(shù)組closedge：l每個(gè)元素每個(gè)元素closedgev有兩個(gè)域有兩個(gè)域 lowcost：存放生成樹(shù)頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹(shù)外各頂點(diǎn)：存放生成樹(shù)頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹(shù)外各頂點(diǎn)v的各邊上的當(dāng)前最小權(quán)值的各邊上的當(dāng)前最小權(quán)值 adjvex：記錄生成樹(shù)頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)：記錄生成樹(shù)頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近（即權(quán)值最?。╉旤c(diǎn)最近（即權(quán)值最?。?2u從頂點(diǎn)從頂點(diǎn)0出發(fā)利用出發(fā)利用prim算法構(gòu)造最小生成樹(shù)過(guò)程中算法構(gòu)造最小生

49、成樹(shù)過(guò)程中輔助數(shù)組各分量的值的變化輔助數(shù)組各分量的值的變化i1 23456closedgeadjvexlowcost0280000100525422424312318216i1 23456edgeadjvexlowcost1140123456u100000052501011422131212161114173u利用利用 prim 算法求最小生成樹(shù)的算法算法求最小生成樹(shù)的算法class addarray int adjvex; float lowcost;/ addarrayvoid minspantree_prim (int u, addarray closedge, addarray edg

50、e, adjmatrix g)/ 設(shè)圖以鄰接矩陣存儲(chǔ)，用設(shè)圖以鄰接矩陣存儲(chǔ)，用prim算法從頂點(diǎn)算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)出發(fā)構(gòu)造網(wǎng)g的的最小生成樹(shù)且保存到數(shù)組最小生成樹(shù)且保存到數(shù)組edge中中 for(v=0；vn；v+) uv=0； uu=1； for (v=0；v n；v+) if（u!=v) closedgev.adjvex=u;74 closedgev.lowcost=g.matrixuv; for (t=1；tn；t+) /選擇其余的選擇其余的n-1個(gè)頂點(diǎn)個(gè)頂點(diǎn) k=minimum(closedge)； / 求出求出t的下一個(gè)頂點(diǎn)的下一個(gè)頂點(diǎn)k頂點(diǎn)頂點(diǎn) u=closedgek.adjv

51、ex； edgek.lowcost=g.matrixku; /保存選中邊的權(quán)值保存選中邊的權(quán)值 edgek.adjvex=u; /保存選中邊的頂點(diǎn)保存選中邊的頂點(diǎn) uk=1； for (j=0；jg.matrixkj) closedgej.lowcost=g.matrixkj； closedgej.adjvex=k； / for / minspantree_prim75uprime 算法分析算法分析設(shè)連通無(wú)向網(wǎng)有設(shè)連通無(wú)向網(wǎng)有 n 個(gè)頂點(diǎn)，則該算法的時(shí)間復(fù)雜度為個(gè)頂點(diǎn)，則該算法的時(shí)間復(fù)雜度為o(n2)適用于稠密的網(wǎng)絡(luò)適用于稠密的網(wǎng)絡(luò)76kruscal 算法算法u基本思想基本思想 先構(gòu)造一個(gè)只含

52、先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)、不含有邊的零圖個(gè)頂點(diǎn)、不含有邊的零圖 t ，然后從，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使權(quán)值最小的邊開(kāi)始，若它的添加不使 t 產(chǎn)生回路，則在產(chǎn)生回路，則在 t 上加上這條邊，如此重復(fù)，直至加上上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。條邊為止。77u例例10121416252278u算法思想算法思想設(shè)無(wú)向連通圖設(shè)無(wú)向連通圖 g=(v, e) 的最小生成樹(shù)為的最小生成樹(shù)為 t=(u, te)1）初始化：）初始化：u=v；te= ；2）循環(huán)直到）循環(huán)直到 t 中的連通分量個(gè)數(shù)為中的連通分量個(gè)數(shù)為 1l在在 e 中尋找最短邊中尋找最短邊 (u, v)；l如果頂

53、點(diǎn)如果頂點(diǎn) u、v 位于位于 t 的兩個(gè)不同的連通分量，則將的兩個(gè)不同的連通分量，則將邊邊 (u, v) 并入并入 te，并將這兩個(gè)連通分量合為一個(gè)；，并將這兩個(gè)連通分量合為一個(gè)；l在在 e 中標(biāo)記邊中標(biāo)記邊 (u, v)，使之不參加后續(xù)最短邊的選取。，使之不參加后續(xù)最短邊的選取。79有向圖可以用來(lái)描述一個(gè)工程（或系統(tǒng)）的進(jìn)行過(guò)程。有向圖可以用來(lái)描述一個(gè)工程（或系統(tǒng)）的進(jìn)行過(guò)程。u每個(gè)工程由若干個(gè)子工程（活動(dòng)）組成，完成了每個(gè)工程由若干個(gè)子工程（活動(dòng)）組成，完成了這些子工程整個(gè)工程就結(jié)束了。這些子工程整個(gè)工程就結(jié)束了。u這些子工程間有兩種關(guān)系這些子工程間有兩種關(guān)系有先后順序：即前一子工程結(jié)束后

54、一子工程才能開(kāi)始有先后順序：即前一子工程結(jié)束后一子工程才能開(kāi)始無(wú)先后順序：即兩個(gè)子工程誰(shuí)先誰(shuí)后都互不影響無(wú)先后順序：即兩個(gè)子工程誰(shuí)先誰(shuí)后都互不影響 80例，學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門(mén)課程的學(xué)習(xí)就例，學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門(mén)課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求有先修課是整個(gè)工程的一些活動(dòng)。其中有些課程要求有先修課程，有些則不要求。程，有些則不要求。81兩個(gè)問(wèn)題兩個(gè)問(wèn)題u整個(gè)工程能否順利進(jìn)行？整個(gè)工程能否順利進(jìn)行？u哪些活動(dòng)是影響工程按期完工的關(guān)鍵？哪些活動(dòng)是影響工程按期完工的關(guān)鍵？ 拓?fù)渑判蛲負(fù)渑判?關(guān)鍵路徑關(guān)鍵路徑82aov 網(wǎng)網(wǎng)u用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)

55、系的用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖，稱(chēng)為頂點(diǎn)表示活動(dòng)的網(wǎng)（有向圖，稱(chēng)為頂點(diǎn)表示活動(dòng)的網(wǎng)（activity on vertices）u若若是圖中的有向邊，則表示活動(dòng)是圖中的有向邊，則表示活動(dòng) vi 必須先必須先于活動(dòng)于活動(dòng) vj 進(jìn)行進(jìn)行uaov 網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)不能網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)不能以自己為先決條件以自己為先決條件83u例例學(xué)生課程學(xué)習(xí)工程圖學(xué)生課程學(xué)習(xí)工程圖84由給定的由給定的 aov 網(wǎng)所描述的工程是否可行？網(wǎng)所描述的工程是否可行？u檢測(cè)方法：拓?fù)渑判驒z測(cè)方法：拓?fù)渑判驅(qū)τ邢驁D構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)對(duì)有向圖構(gòu)造其頂點(diǎn)

56、的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該都在它的拓?fù)溆行蛐蛄兄?，則該 aov 網(wǎng)必定不存在回網(wǎng)必定不存在回路，工程可行。路，工程可行。相反，如果得不到滿(mǎn)足要求的拓?fù)溆行蛐蛄校瑒t說(shuō)明相反，如果得不到滿(mǎn)足要求的拓?fù)溆行蛐蛄?，則說(shuō)明aov 網(wǎng)中存在有向回路，此網(wǎng)中存在有向回路，此 aov 網(wǎng)所代表的工程是不網(wǎng)所代表的工程是不可行的。可行的。85概念概念u拓?fù)洌ㄓ行颍┬蛄型負(fù)洌ㄓ行颍┬蛄性谠?aov 網(wǎng)中若將各個(gè)頂點(diǎn)（代表各個(gè)活動(dòng)）排列成一網(wǎng)中若將各個(gè)頂點(diǎn)（代表各個(gè)活動(dòng)）排列成一個(gè)線(xiàn)性有序的序列個(gè)線(xiàn)性有序的序列 v1, v2, , vn，使得若從頂點(diǎn)，使得若從頂點(diǎn) vi 到到 vj

57、有有一條有向路徑，則在序列中頂點(diǎn)一條有向路徑，則在序列中頂點(diǎn) vi 必須排在頂點(diǎn)必須排在頂點(diǎn) vj 之前。之前。u拓?fù)渑判蛲負(fù)渑判蛟谠?aov 網(wǎng)中找一個(gè)拓?fù)湫蛄械倪^(guò)程。網(wǎng)中找一個(gè)拓?fù)湫蛄械倪^(guò)程。86u例，對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到的拓例，?duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到的拓?fù)溆行蛐蛄袨閾溆行蛐蛄袨?7u例，對(duì)下列有向圖不能求得它的拓?fù)溆行蛐蛄欣?，?duì)下列有向圖不能求得它的拓?fù)溆行蛐蛄衎dac因?yàn)閳D中存在一個(gè)有向回路因?yàn)閳D中存在一個(gè)有向回路 b, c, d88拓?fù)渑判虻乃枷胪負(fù)渑判虻乃枷雞輸入一個(gè)輸入一個(gè) aov 網(wǎng)，令網(wǎng)，令 n 為頂點(diǎn)個(gè)數(shù)。為頂點(diǎn)個(gè)數(shù)。(1) 在在 aov 網(wǎng)中選一

58、個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并輸出之。網(wǎng)中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并輸出之。(2) 從圖中刪去該頂點(diǎn)，同時(shí)刪去與該頂點(diǎn)關(guān)聯(lián)的弧。從圖中刪去該頂點(diǎn)，同時(shí)刪去與該頂點(diǎn)關(guān)聯(lián)的弧。(3) 重復(fù)以上重復(fù)以上 (1)、(2) 步，直到步，直到l全部頂點(diǎn)均已輸出，拓?fù)湫蛄行纬?，拓?fù)渑判蛲瓿?；全部頂點(diǎn)均已輸出，拓?fù)湫蛄行纬?，拓?fù)渑判蛲瓿桑籰或圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說(shuō)或圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說(shuō)明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí) aov 網(wǎng)中一定存在有網(wǎng)中一定存在有向回路。向回

59、路。89u例例eabcghdfabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 入度為零的頂點(diǎn)入度為零的頂點(diǎn) 弧頭頂點(diǎn)的入度減弧頭頂點(diǎn)的入度減 1輸出輸出90拓?fù)渑判虻乃惴ㄋ枷胪負(fù)渑判虻乃惴ㄋ枷雞圖的存儲(chǔ)：鄰接表圖的存儲(chǔ)：鄰接表u增設(shè)一個(gè)數(shù)組增設(shè)一個(gè)數(shù)組 indegree ，記錄各個(gè)頂點(diǎn)的入度，記錄各個(gè)頂點(diǎn)的入度在輸入數(shù)據(jù)時(shí)，每輸入一條弧在輸入數(shù)據(jù)時(shí)，每輸入一條弧，就需要建立一個(gè)弧，就需要建立一個(gè)弧結(jié)點(diǎn)，將它鏈入相應(yīng)弧鏈表中，并統(tǒng)計(jì)入度信息結(jié)點(diǎn)，將它鏈入相應(yīng)弧鏈表中，并統(tǒng)計(jì)入度信息 earcnode *p = new earcnode (k); pl

60、ink = gheadj.firstout; gheadj.firstout = p; indegreek+;/頂點(diǎn)頂點(diǎn) k 入度加入度加1 91u使用一個(gè)鏈?zhǔn)綏＃褂靡粋€(gè)鏈?zhǔn)綏?，存放入度為零的頂點(diǎn)存放入度為零的頂點(diǎn)只要出現(xiàn)入度為零的頂點(diǎn)，就將它加入棧中只要出現(xiàn)入度為零的頂點(diǎn)，就將它加入棧中由于表頭結(jié)點(diǎn)的由于表頭結(jié)點(diǎn)的“入度計(jì)數(shù)域入度計(jì)數(shù)域”在變成在變成0之后，已經(jīng)無(wú)用，之后，已經(jīng)無(wú)用，故用它作為鏈?zhǔn)綏９视盟鳛殒準(zhǔn)綏使用頂點(diǎn)棧的拓?fù)渑判蛩惴梢悦枋鋈缦率褂庙旤c(diǎn)棧的拓?fù)渑判蛩惴梢悦枋鋈缦?1) 建立入度為零的頂點(diǎn)棧；建立入度為零的頂點(diǎn)棧；(2) 當(dāng)入度為零的頂點(diǎn)棧不空時(shí)，重復(fù)執(zhí)行當(dāng)入度為零的頂點(diǎn)棧不空時(shí)，