數(shù)據(jù)結(jié)構(gòu)中的圖

1、 第第7 7章章 圖（圖（GraphGraph） 主講：李耀國(guó)主講：李耀國(guó)第七章第七章 圖圖 圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有表中，數(shù)據(jù)元素之間僅有線性關(guān)系線性關(guān)系，每個(gè)元素最多只有一，每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。在樹型結(jié)構(gòu)中，數(shù)據(jù)元素之個(gè)直接前驅(qū)和一個(gè)直接后繼。在樹型結(jié)構(gòu)中，數(shù)據(jù)元素之間存在明顯的間存在明顯的層次關(guān)系層次關(guān)系，并且每層的元素可能和下一層的，并且每層的元素可能和下一層的多個(gè)元素相鄰，但只能和上一層的一個(gè)元素相鄰。而多個(gè)元素相鄰，但只能和上一層的一個(gè)元素相鄰。而在圖在圖形結(jié)構(gòu)中，結(jié)點(diǎn)

2、之間的關(guān)系可以是形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意任意的，圖中的任意兩的，圖中的任意兩個(gè)元素之間都可能相鄰個(gè)元素之間都可能相鄰。圖是計(jì)算機(jī)應(yīng)用過(guò)程中對(duì)實(shí)際問。圖是計(jì)算機(jī)應(yīng)用過(guò)程中對(duì)實(shí)際問題進(jìn)行數(shù)學(xué)抽象和描述的強(qiáng)有力的工具，數(shù)據(jù)結(jié)構(gòu)中對(duì)圖題進(jìn)行數(shù)學(xué)抽象和描述的強(qiáng)有力的工具，數(shù)據(jù)結(jié)構(gòu)中對(duì)圖的討論側(cè)重于在計(jì)算機(jī)中的討論側(cè)重于在計(jì)算機(jī)中如何表示圖如何表示圖以及如何實(shí)現(xiàn)圖的操以及如何實(shí)現(xiàn)圖的操作和作和應(yīng)用應(yīng)用等。等。第七章第七章 圖和廣義表圖和廣義表 7.1 7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu) 7.3 7.3 圖的遍歷圖的遍歷 7.4 7.4 圖的連通性問題圖

3、的連通性問題 7.5 7.5 有向無(wú)環(huán)圖及其應(yīng)用有向無(wú)環(huán)圖及其應(yīng)用 7.5.1 7.5.1 拓?fù)渑判蛲負(fù)渑判?7.5.2 7.5.2 關(guān)鍵路徑關(guān)鍵路徑 7.6 7.6 最短路徑最短路徑7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)圖圖由一個(gè)由一個(gè)頂點(diǎn)頂點(diǎn)的有窮非空集合的有窮非空集合V(G)V(G)和一個(gè)和一個(gè)弧弧的集的集合合E(G)E(G)組成，通常記做組成，通常記做G=(V,E)G=(V,E)。圖中的。圖中的頂點(diǎn)頂點(diǎn)即為即為數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素?cái)?shù)據(jù)元素，弧弧的集合的集合E E實(shí)際上是定義實(shí)際上是定義在頂點(diǎn)集合上的一個(gè)在頂點(diǎn)集合上的一個(gè)關(guān)系關(guān)系。用有序?qū)?。用有序?qū)Ρ硎緩谋硎緩膙 v到到w w

4、的一條的一條弧弧?；【哂蟹较蛐裕詭Ъ^的線段表?；【哂蟹较蛐?，以帶箭頭的線段表示，通常稱示，通常稱v v為為弧尾弧尾或或始點(diǎn)始點(diǎn)，稱，稱w w為為弧頭弧頭或或終點(diǎn)終點(diǎn)，此，此時(shí)的圖稱為時(shí)的圖稱為有向圖有向圖。若圖中從。若圖中從v v到到w w有一條弧，同時(shí)有一條弧，同時(shí)從從w w到到v v也有一條弧，則以無(wú)序?qū)σ灿幸粭l弧，則以無(wú)序?qū)?v,w)(v,w)代替這兩個(gè)代替這兩個(gè)有序?qū)τ行驅(qū)秃?表示表示v v和和w w之間的一條之間的一條邊邊。此。此時(shí)的圖在頂點(diǎn)之間不再?gòu)?qiáng)調(diào)方向性的特征，稱為時(shí)的圖在頂點(diǎn)之間不再?gòu)?qiáng)調(diào)方向性的特征，稱為無(wú)無(wú)向圖向圖。7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)圖圖G1G1是一

5、個(gè)有向圖，是一個(gè)有向圖，G1=(V1,A1)G1=(V1,A1)。其中。其中: : V1=A,C,B,F,D,E,G V1=A,C,B,F,D,E,G A1=, A1=, ,ACBFDGE有向圖有向圖G17.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 圖圖G2G2是一個(gè)無(wú)向圖，是一個(gè)無(wú)向圖，G2=(V2,E2)G2=(V2,E2)。其中：。其中： V2=A,B,C,D,E,FV2=A,B,C,D,E,F E2=(A,B),(A,C),(B,C),(B,E),(B,F),(C,F), E2=(A,B),(A,C),(B,C),(B,E),(B,F),(C,F), (C,D),(E,F),(C,E)(C,D

6、),(E,F),(C,E)ABCDEF無(wú)向圖無(wú)向圖G27.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 在實(shí)際應(yīng)用中，圖的弧或邊往往與具有一定意義在實(shí)際應(yīng)用中，圖的弧或邊往往與具有一定意義的數(shù)相關(guān)，稱這些數(shù)為的數(shù)相關(guān)，稱這些數(shù)為權(quán)權(quán)(weight)(weight)。分別稱帶權(quán)的有。分別稱帶權(quán)的有向圖和無(wú)向圖為向圖和無(wú)向圖為有向網(wǎng)有向網(wǎng)和和無(wú)向網(wǎng)無(wú)向網(wǎng)。123456712345671918212756103311706475806018069584331324430無(wú)向網(wǎng)無(wú)向網(wǎng)有向網(wǎng)有向網(wǎng)7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 稀疏圖和稠密圖稀疏圖和稠密圖 假設(shè)用假設(shè)用n n表示圖中頂點(diǎn)數(shù)目，用表示圖中頂點(diǎn)數(shù)

7、目，用e e表示表示邊或弧的數(shù)目。若不考慮頂點(diǎn)到其自身的弧或邊，則對(duì)于邊或弧的數(shù)目。若不考慮頂點(diǎn)到其自身的弧或邊，則對(duì)于無(wú)向圖，邊數(shù)無(wú)向圖，邊數(shù)e e的取值范圍是的取值范圍是0 0到到n(n-1)/2n(n-1)/2。稱具有。稱具有n(n-n(n-1)/21)/2條邊的無(wú)向圖為條邊的無(wú)向圖為完全圖完全圖。對(duì)于有向圖，弧的數(shù)目。對(duì)于有向圖，弧的數(shù)目e e的的取值范圍是取值范圍是0 0到到n(n-1)n(n-1)。稱具有。稱具有n(n-1)n(n-1)條弧的有向圖為條弧的有向圖為有有向完全圖向完全圖。若。若enlognev是圖中的一條弧，則稱是圖中的一條弧，則稱u鄰接鄰接到到v，或，或v鄰接自鄰接

8、自u(píng)。圖中所。圖中所鄰接到鄰接到某頂點(diǎn)某頂點(diǎn)v的弧的數(shù)目，的弧的數(shù)目，稱為該頂點(diǎn)的稱為該頂點(diǎn)的入度入度，記作，記作:ID(v)；反之，從某頂點(diǎn)；反之，從某頂點(diǎn)u出出發(fā)發(fā)的弧的數(shù)目，稱為該頂點(diǎn)的的弧的數(shù)目，稱為該頂點(diǎn)的出度出度，記作，記作:OD(u)。頂。頂點(diǎn)點(diǎn)v的入度和出度之的入度和出度之和和稱為該頂點(diǎn)的稱為該頂點(diǎn)的總度總度，簡(jiǎn)稱為，簡(jiǎn)稱為度度，記作記作: TD(v)。例如圖。例如圖G1中頂點(diǎn)中頂點(diǎn)B的入度的入度ID(B)=2，出，出度度OD(B)=3，度，度TD(B)=5。 無(wú)向圖中頂點(diǎn)的度定義為與該頂點(diǎn)相連的邊的數(shù)目。無(wú)向圖中頂點(diǎn)的度定義為與該頂點(diǎn)相連的邊的數(shù)目。 一般情況下，如果頂點(diǎn)一般

9、情況下，如果頂點(diǎn)vi的度記作的度記作TD(vi)，則一個(gè)含有，則一個(gè)含有n個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e條邊或弧的圖，滿足如下關(guān)系：條邊或弧的圖，滿足如下關(guān)系：niivTDe1)(21ACBFDGE7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 路徑和回路路徑和回路 若有向圖若有向圖G中中k+1個(gè)頂點(diǎn)之間都個(gè)頂點(diǎn)之間都有弧存在，則這個(gè)頂點(diǎn)的序列有弧存在，則這個(gè)頂點(diǎn)的序列v0,v1,vk為為從頂點(diǎn)從頂點(diǎn)v0到頂點(diǎn)到頂點(diǎn)vk的一條的一條有向路徑有向路徑，路徑中，路徑中弧的數(shù)目定義為弧的數(shù)目定義為路徑長(zhǎng)度路徑長(zhǎng)度。若序列中的頂點(diǎn)。若序列中的頂點(diǎn)都不相同，則為都不相同，則為簡(jiǎn)單路徑簡(jiǎn)單路徑。對(duì)無(wú)向圖，相鄰。對(duì)無(wú)向圖，相鄰頂

10、點(diǎn)之間存在邊的頂點(diǎn)之間存在邊的k+1個(gè)頂點(diǎn)序列構(gòu)成一條個(gè)頂點(diǎn)序列構(gòu)成一條長(zhǎng)度為長(zhǎng)度為k的的無(wú)向路徑無(wú)向路徑。如若。如若v0和和vk是同一個(gè)頂是同一個(gè)頂點(diǎn)，則是一條由某個(gè)頂點(diǎn)出發(fā)又回到自身的點(diǎn)，則是一條由某個(gè)頂點(diǎn)出發(fā)又回到自身的路徑，稱這種路徑為路徑，稱這種路徑為回路回路或或環(huán)環(huán)。7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 連通圖和連通分量連通圖和連通分量 若無(wú)向圖中任意兩個(gè)若無(wú)向圖中任意兩個(gè)頂點(diǎn)之間都存在一條無(wú)向路徑，則稱該無(wú)頂點(diǎn)之間都存在一條無(wú)向路徑，則稱該無(wú)向圖為向圖為連通圖連通圖。對(duì)有向圖而言，若圖中任。對(duì)有向圖而言，若圖中任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則意兩個(gè)頂點(diǎn)之間都存在一條有向路徑

11、，則稱該有向圖為稱該有向圖為強(qiáng)連通圖強(qiáng)連通圖。非連通圖中的各。非連通圖中的各個(gè)極大連通子圖稱為該圖的個(gè)極大連通子圖稱為該圖的連通分量連通分量。ABCDEFACBFDGE非強(qiáng)連通圖和強(qiáng)連通分量非強(qiáng)連通圖和強(qiáng)連通分量非連通圖和連通分量非連通圖和連通分量7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 圖的抽象數(shù)據(jù)類型圖的抽象數(shù)據(jù)類型ADT Graph ADT Graph 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象V:VV:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R:R=VRR:R=VR VR=|v,wP(v,w), VR=|v,wP(v,w), 表示從到的弧表示從到的

12、弧, , 謂詞謂詞P(v,w)P(v,w)定義了弧定義了弧的意義或信息的意義或信息 基本操作：基本操作： CreateGraph (&G,V,VR)CreateGraph (&G,V,VR)n初始條件：初始條件：V V是圖的頂點(diǎn)集，是圖的頂點(diǎn)集，VRVR是圖中弧的集合。是圖中弧的集合。n操作結(jié)果：按操作結(jié)果：按V V和和VRVR的定義構(gòu)造圖的定義構(gòu)造圖G G。 DestoryGraph (&G)DestoryGraph (&G)n初始條件：圖初始條件：圖G G存在。存在。n操作結(jié)果：銷毀圖操作結(jié)果：銷毀圖G G。 LocateVex (G,u)LocateVex

13、 (G,u)n初始條件：圖初始條件：圖G G存在，存在，u u和和G G中頂點(diǎn)有相同特征。中頂點(diǎn)有相同特征。n操作結(jié)果：若操作結(jié)果：若G G中存在頂點(diǎn)中存在頂點(diǎn)u u，則返回該頂點(diǎn)在圖中的位置；否則返回其他信息。，則返回該頂點(diǎn)在圖中的位置；否則返回其他信息。more7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) GetVex (G,v)GetVex (G,v)n初始條件：圖初始條件：圖G G存在，存在，v v是是G G中的某個(gè)頂點(diǎn)。中的某個(gè)頂點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回v v的值。的值。 PutVex (&G,v,value)PutVex (&G,v,value)n初始條件：圖初始

14、條件：圖G G存在，存在，v v是是G G中的某個(gè)頂點(diǎn)。中的某個(gè)頂點(diǎn)。n操作結(jié)果：對(duì)操作結(jié)果：對(duì)v v賦值賦值valuevalue。 FirstAdjVex (G,v)FirstAdjVex (G,v)n初始條件：圖初始條件：圖G G存在，存在， v v是是G G中的某個(gè)頂點(diǎn)。中的某個(gè)頂點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回v v的第一個(gè)鄰接點(diǎn)，若該頂點(diǎn)在的第一個(gè)鄰接點(diǎn)，若該頂點(diǎn)在G G中無(wú)鄰接點(diǎn)，則返中無(wú)鄰接點(diǎn)，則返回空?；乜?。 NextAdjVex (G,v,w)NextAdjVex (G,v,w)n初始條件：圖初始條件：圖G G存在，存在，v v是是G G中的某個(gè)頂點(diǎn)，中的某個(gè)頂點(diǎn)，w w是

15、是v v的鄰接頂點(diǎn)。的鄰接頂點(diǎn)。n操作結(jié)果：返回操作結(jié)果：返回v v的的( (相對(duì)于相對(duì)于w w的的) )下一個(gè)鄰接點(diǎn)。若下一個(gè)鄰接點(diǎn)。若w w是是v v的最后一個(gè)的最后一個(gè)鄰接點(diǎn)，則返回空。鄰接點(diǎn)，則返回空。more7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) InsertVex (&G,v) InsertVex (&G,v)n 初始條件：圖初始條件：圖G G存在，存在，v v和圖中頂點(diǎn)有相同特征。和圖中頂點(diǎn)有相同特征。n 操作結(jié)果：在圖操作結(jié)果：在圖G G中增添新頂點(diǎn)中增添新頂點(diǎn)v v。 DeleteVex (&G,v)DeleteVex (&G,v)n 初始條件：

16、圖初始條件：圖G G存在，存在，v v是是G G中的某個(gè)頂點(diǎn)。中的某個(gè)頂點(diǎn)。n 操作結(jié)果：刪除操作結(jié)果：刪除G G中頂點(diǎn)中頂點(diǎn)v v及其相關(guān)的弧。及其相關(guān)的弧。 InsertArc (&G,v,w)InsertArc (&G,v,w)n 初始條件：圖初始條件：圖G G存在，存在， v v和和w w是是G G中的兩個(gè)頂點(diǎn)。中的兩個(gè)頂點(diǎn)。n 操作結(jié)果：在圖操作結(jié)果：在圖G G中增添弧中增添弧，若，若G G是無(wú)向的，則還是無(wú)向的，則還增添對(duì)稱弧增添對(duì)稱弧。 DeleteArc (&G,v,w)DeleteArc (&G,v,w)n 初始條件：圖初始條件：圖G G存在，

17、存在， v v和和w w是是G G中的兩個(gè)頂點(diǎn)。中的兩個(gè)頂點(diǎn)。n 操作結(jié)果：在圖操作結(jié)果：在圖G G中刪除弧中刪除弧，若，若G G是無(wú)向的，則還是無(wú)向的，則還刪除對(duì)稱弧刪除對(duì)稱弧。more7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) DFSTraverse (G,v,visit() DFSTraverse (G,v,visit()n 初始條件：圖初始條件：圖G G存在，存在，v v是是G G中的某個(gè)頂點(diǎn)，中的某個(gè)頂點(diǎn)，visitvisit是是針對(duì)頂點(diǎn)的應(yīng)用函數(shù)。針對(duì)頂點(diǎn)的應(yīng)用函數(shù)。n 操作結(jié)果：從頂點(diǎn)操作結(jié)果：從頂點(diǎn)v v起深度優(yōu)先遍歷圖起深度優(yōu)先遍歷圖G G，并對(duì)每個(gè)，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)頂點(diǎn)調(diào)用函

18、數(shù)visitvisit一次且僅一次。一旦一次且僅一次。一旦visit()visit()失失敗，則操作失敗。敗，則操作失敗。 BFSTraverse (G,v,visit() BFSTraverse (G,v,visit() n 初始條件：圖初始條件：圖G G存在，存在，v v是是G G中的某個(gè)頂點(diǎn)，中的某個(gè)頂點(diǎn)，visitvisit是是針對(duì)頂點(diǎn)的應(yīng)用函數(shù)。針對(duì)頂點(diǎn)的應(yīng)用函數(shù)。n 操作結(jié)果：從頂點(diǎn)操作結(jié)果：從頂點(diǎn)v v起廣度優(yōu)先遍歷圖起廣度優(yōu)先遍歷圖G G，并對(duì)每個(gè)，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)頂點(diǎn)調(diào)用函數(shù)visitvisit一次且僅一次。一旦一次且僅一次。一旦visit()visit()失失敗，則操作

19、失敗。敗，則操作失敗。ADT GraphADT Graph7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)圖是一種典型的復(fù)雜結(jié)構(gòu)，圖中頂點(diǎn)可能同任意一圖是一種典型的復(fù)雜結(jié)構(gòu)，圖中頂點(diǎn)可能同任意一個(gè)其他頂點(diǎn)之間存在關(guān)系。因此，圖沒有順序映象個(gè)其他頂點(diǎn)之間存在關(guān)系。因此，圖沒有順序映象的存儲(chǔ)結(jié)構(gòu)。圖有兩種常用的存儲(chǔ)結(jié)構(gòu)。的存儲(chǔ)結(jié)構(gòu)。圖有兩種常用的存儲(chǔ)結(jié)構(gòu)。7.2.1 7.2.1 圖的數(shù)組圖的數(shù)組( (鄰接矩陣鄰接矩陣) )存儲(chǔ)表示存儲(chǔ)表示 鄰接矩陣是用于描述圖中頂點(diǎn)之間的關(guān)系鄰接矩陣是用于描述圖中頂點(diǎn)之間的關(guān)系( (及弧或邊的權(quán)及弧或邊的權(quán)) )的矩陣，假設(shè)圖中頂點(diǎn)數(shù)為的矩陣，假設(shè)圖中頂點(diǎn)數(shù)為n n，則鄰接矩陣，

20、則鄰接矩陣A=(aA=(ai,ji,j) )m m* *n n定義定義為：為：nAij=1 若若Vi和和Vj之間有弧或邊存在之間有弧或邊存在0 Vi和和Vj之間沒有弧或邊存在之間沒有弧或邊存在7.2.1 圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲(chǔ)表示存儲(chǔ)表示 0000000100000000010100000100001000001101000000010ACBFDGEABCDEF 010110100110000100111011110101000110有向圖有向圖G1無(wú)向圖無(wú)向圖G2G1的鄰接矩陣的鄰接矩陣G2的鄰接矩陣的鄰接矩陣7.2.1 圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲(chǔ)表示存儲(chǔ)表示

21、一般情況下，圖中沒有鄰接到自身的弧，因此矩陣中主對(duì)角一般情況下，圖中沒有鄰接到自身的弧，因此矩陣中主對(duì)角線全為零。由于無(wú)向圖中一條邊視為一對(duì)弧，則無(wú)向圖的鄰線全為零。由于無(wú)向圖中一條邊視為一對(duì)弧，則無(wú)向圖的鄰接矩陣必然是對(duì)稱矩陣。接矩陣必然是對(duì)稱矩陣。網(wǎng)的鄰接矩陣定義中，當(dāng)網(wǎng)的鄰接矩陣定義中，當(dāng)v vi i到到v vj j有弧相鄰接時(shí)，有弧相鄰接時(shí)，a ai,ji,j的值為該的值為該弧上的權(quán)值，否則為弧上的權(quán)值，否則為。1234567706475806018069584331324430 6943755818070443230603164807.2.1 圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲(chǔ)

22、表示存儲(chǔ)表示有向圖的鄰接矩陣大多為有向圖的鄰接矩陣大多為稀疏矩陣稀疏矩陣，可以采用，可以采用壓縮壓縮存儲(chǔ)表示。用存儲(chǔ)表示。用二維數(shù)組二維數(shù)組表示更為方便，它和頂點(diǎn)信息等其他圖的信息一起構(gòu)成圖的一種存儲(chǔ)表示表示更為方便，它和頂點(diǎn)信息等其他圖的信息一起構(gòu)成圖的一種存儲(chǔ)表示const INFINITY_INT_MAX=MAX; /最大值最大值設(shè)為設(shè)為MAXconst MAX_VERTEX_NUM=20; /最大頂點(diǎn)個(gè)數(shù)最大頂點(diǎn)個(gè)數(shù)typedef enum DG,DN,AG,ANGraphKind; /圖類型圖類型(有向圖、有向網(wǎng)、無(wú)向圖、有向圖、有向網(wǎng)、無(wú)向圖、無(wú)向網(wǎng)無(wú)向網(wǎng))typedef stru

23、ct ArcCellVRType adj; / VRType為頂點(diǎn)的關(guān)系類型。對(duì)無(wú)權(quán)圖，用為頂點(diǎn)的關(guān)系類型。對(duì)無(wú)權(quán)圖，用1或或0表示是否相鄰；表示是否相鄰；對(duì)帶權(quán)圖則為權(quán)值類型對(duì)帶權(quán)圖則為權(quán)值類型InfoType *info; /指向該弧相關(guān)信息的指針指向該弧相關(guān)信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM; / 描述頂點(diǎn)的數(shù)組描述頂點(diǎn)的數(shù)組AdjMatrix arcs; / 鄰接矩陣鄰接矩陣int vexnum,arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和

24、弧圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊邊)數(shù)數(shù)GraphKind kind; / 圖的種類標(biāo)志圖的種類標(biāo)志MGraph;vexsvexsMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_MAX_VERTEX_NUMVERTEX_NUM arcsarcsvexnumvexnumarcnumarcnumkindkind7.2.2圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示 鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)表示方法，是圖的一種鏈?zhǔn)酱鎯?chǔ)表示方法，它類似于樹的孩子鏈表。在有向圖的它類似于樹的孩子鏈表。在有向圖的鄰接表中，從同一個(gè)頂

25、點(diǎn)出發(fā)的弧鏈鄰接表中，從同一個(gè)頂點(diǎn)出發(fā)的弧鏈接在同一鏈表中，接在同一鏈表中，鄰接表中結(jié)點(diǎn)的個(gè)鄰接表中結(jié)點(diǎn)的個(gè)數(shù)恰好為圖中弧的個(gè)數(shù)數(shù)恰好為圖中弧的個(gè)數(shù)。在無(wú)向圖的。在無(wú)向圖的鄰接表中，同一條邊有兩個(gè)結(jié)點(diǎn)，分鄰接表中，同一條邊有兩個(gè)結(jié)點(diǎn)，分別出現(xiàn)在和它相關(guān)的兩個(gè)頂點(diǎn)的鏈表別出現(xiàn)在和它相關(guān)的兩個(gè)頂點(diǎn)的鏈表中，因此中，因此無(wú)向圖的鄰接表中結(jié)點(diǎn)個(gè)數(shù)無(wú)向圖的鄰接表中結(jié)點(diǎn)個(gè)數(shù)是邊的是邊的兩兩倍倍。7.2.2圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示ACBFDGE有向圖有向圖G1MAX_VERTEX_NUMABCEDFG - -01234561361242457.2.2圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示MAX_V

26、ERTEX_NUMABCEDF - -012345ABCDEF無(wú)向圖無(wú)向圖G22 1024015 345 2 125 124 7.2.2圖的鄰接表存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示 鄰接表定義如下：鄰接表定義如下：const MAX_VERTEX_NUM=20;typedef struct ArcNodeint adjvex; /該弧所指向的頂點(diǎn)的位置該弧所指向的頂點(diǎn)的位置struct ArcNode *nextarc; /指向下一條弧的指針指向下一條弧的指針I(yè)nfoType *info;/指向該弧相關(guān)信息的指針指向該弧相關(guān)信息的指針ArcNode;typedef struct VNodeVertex

27、Type data;/頂點(diǎn)信息頂點(diǎn)信息ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧指向第一條依附該頂點(diǎn)的弧VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)int kind; /圖的種類標(biāo)志圖的種類標(biāo)志ALGraph;算法算法7.1void CreateUDG (ALGraph &G) /采用鄰接表存儲(chǔ)表示，構(gòu)造無(wú)向圖采用鄰接表存儲(chǔ)表示，構(gòu)造無(wú)向圖G(G.kind=UDG) cinG.vexnumG.arcnumInc

28、info; for(i=0; iG.verticesi.data;/輸入頂點(diǎn)值輸入頂點(diǎn)值 G.verticesi.firstarc=NULL; /初始化鏈表頭指針為空初始化鏈表頭指針為空 /for for(k=0; kv1v2;/輸入一條弧的始點(diǎn)和終點(diǎn)輸入一條弧的始點(diǎn)和終點(diǎn) i=LocateVex(G,v1); j=LocateVex(G,v2); /確定確定v1和和v2在在G中的位置，即頂點(diǎn)在中的位置，即頂點(diǎn)在G.Vertices中的序號(hào)中的序號(hào) pi=new ArcNode; pi-adjvex=j; /對(duì)弧結(jié)點(diǎn)賦鄰接點(diǎn)對(duì)弧結(jié)點(diǎn)賦鄰接點(diǎn)“位置位置”信息信息 pi-nextarc=G.ver

29、ticesi.firstarc; G.verticesi.firstarc=pi; /插入鏈表插入鏈表G.verticesi pj=new ArcNode; pj-adjvex=i; /對(duì)弧結(jié)點(diǎn)賦鄰接點(diǎn)對(duì)弧結(jié)點(diǎn)賦鄰接點(diǎn)“位置位置”信信息息 pj-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=pj; /插入鏈表插入鏈表G.verticesj if (IncInfo)/若弧含有相關(guān)信息，則輸入若弧含有相關(guān)信息，則輸入cinpj-info; pi-info=pj-info; /for /CreateUDG7.3 圖的遍歷圖的遍歷 與二叉樹和樹的

30、遍歷類似，圖結(jié)構(gòu)也有遍歷操作，即從某個(gè)與二叉樹和樹的遍歷類似，圖結(jié)構(gòu)也有遍歷操作，即從某個(gè)頂點(diǎn)出發(fā)，沿著某條路徑對(duì)圖中其余頂點(diǎn)進(jìn)行訪問，且使每頂點(diǎn)出發(fā)，沿著某條路徑對(duì)圖中其余頂點(diǎn)進(jìn)行訪問，且使每一個(gè)頂點(diǎn)只被訪問一次。但圖的遍歷要比樹的遍歷更復(fù)雜，一個(gè)頂點(diǎn)只被訪問一次。但圖的遍歷要比樹的遍歷更復(fù)雜，因?yàn)閳D中和同一頂點(diǎn)有弧或邊相通的頂點(diǎn)之間可能也有弧或因?yàn)閳D中和同一頂點(diǎn)有弧或邊相通的頂點(diǎn)之間可能也有弧或邊，那么在訪問了某個(gè)頂點(diǎn)之后，可能沿著某條回路又回到邊，那么在訪問了某個(gè)頂點(diǎn)之后，可能沿著某條回路又回到了該頂點(diǎn)。為了避免同一頂點(diǎn)被重復(fù)訪問，則在遍歷過(guò)程中，了該頂點(diǎn)。為了避免同一頂點(diǎn)被重復(fù)訪問，則

31、在遍歷過(guò)程中，必須為已經(jīng)訪問過(guò)的頂點(diǎn)加上標(biāo)識(shí)，以便再次途徑這樣的頂必須為已經(jīng)訪問過(guò)的頂點(diǎn)加上標(biāo)識(shí)，以便再次途徑這樣的頂點(diǎn)時(shí)不再重復(fù)訪問。為此，需附設(shè)一維數(shù)組點(diǎn)時(shí)不再重復(fù)訪問。為此，需附設(shè)一維數(shù)組visited0.n-visited0.n-11，令其每個(gè)分量對(duì)應(yīng)圖中一個(gè)頂點(diǎn)，各分量的初值均設(shè)為，令其每個(gè)分量對(duì)應(yīng)圖中一個(gè)頂點(diǎn)，各分量的初值均設(shè)為FALSEFALSE或或0 0，一旦訪問了某個(gè)頂點(diǎn)，便將，一旦訪問了某個(gè)頂點(diǎn)，便將visitedvisited中相應(yīng)分量中相應(yīng)分量的值置為的值置為TRUETRUE或被訪問時(shí)的序號(hào)?；虮辉L問時(shí)的序號(hào)。 通常，對(duì)圖進(jìn)行遍歷可有兩種搜索路徑：通常，對(duì)圖進(jìn)行遍歷可有

32、兩種搜索路徑：深度優(yōu)先搜索深度優(yōu)先搜索和和廣廣度優(yōu)先搜索度優(yōu)先搜索。7.3.1 深度優(yōu)先搜索遍歷圖深度優(yōu)先搜索遍歷圖 深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷類似于樹的類似于樹的先根先根遍歷，可遍歷，可以看成是先根遍歷的推廣。以看成是先根遍歷的推廣。 假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問，假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問，則從某個(gè)頂點(diǎn)則從某個(gè)頂點(diǎn)v v出發(fā)，首先訪問該頂點(diǎn)，然出發(fā)，首先訪問該頂點(diǎn)，然后依次從它的各個(gè)后依次從它的各個(gè)未被訪問未被訪問的鄰接點(diǎn)出發(fā)的鄰接點(diǎn)出發(fā)深深度優(yōu)先搜索度優(yōu)先搜索遍歷圖，直至圖中所有和遍歷圖，直至圖中所有和v v有路有路徑相通的頂點(diǎn)都被訪問到，若此時(shí)尚有其他徑相通的頂

33、點(diǎn)都被訪問到，若此時(shí)尚有其他頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問到為止。顯然，深度優(yōu)先搜索頂點(diǎn)都被訪問到為止。顯然，深度優(yōu)先搜索是一個(gè)遞歸的過(guò)程。是一個(gè)遞歸的過(guò)程。7.3.1 深度優(yōu)先搜索遍歷圖深度優(yōu)先搜索遍歷圖 例如，從例如，從v v3 3出發(fā)對(duì)下圖進(jìn)行深度優(yōu)先搜索，首先訪問頂點(diǎn)出發(fā)對(duì)下圖進(jìn)行深度優(yōu)先搜索，首先訪問頂點(diǎn)v v3 3，然后從，然后從v v3 3的鄰接頂點(diǎn)的鄰接頂點(diǎn)v v2 2出發(fā)進(jìn)行深度優(yōu)先搜索，先后出發(fā)進(jìn)行深度優(yōu)先搜索，先后訪問訪問v v4 4、v

34、v9 9和和v v1 1，由于，由于v v3 3的第二個(gè)鄰接頂點(diǎn)的第二個(gè)鄰接頂點(diǎn)v v1 1已經(jīng)被訪問已經(jīng)被訪問過(guò)，則不再?gòu)倪^(guò)，則不再?gòu)膙 v1 1出發(fā)進(jìn)行搜索，而出發(fā)進(jìn)行搜索，而v v3 3的下一個(gè)鄰接點(diǎn)的下一個(gè)鄰接點(diǎn)v v6 6未未被訪問，則再?gòu)谋辉L問，則再?gòu)膙 v6 6出發(fā)進(jìn)行搜索。出發(fā)進(jìn)行搜索。124987563搜索過(guò)程中訪問頂點(diǎn)的次序?yàn)椋核阉鬟^(guò)程中訪問頂點(diǎn)的次序?yàn)椋簐3- v2- v4- v9- v1- v6- v5- v8- v7 7.3.1 深度優(yōu)先搜索遍歷圖深度優(yōu)先搜索遍歷圖算法算法7.27.2 Boolean visitMAX;Boolean visitMAX;void DF

35、STraverse(Graph G,Status (void DFSTraverse(Graph G,Status (* *Visit)(int v) Visit)(int v) VisitFunc=Visit; VisitFunc=Visit; for(v=0;vG.vexnum;v+) visitv=False; for(v=0;vG.vexnum;v+) visitv=False; for(v=0;vG.vexnum;v+) if(!visitv) DFS (G, v); for(v=0;vnextarc;) for(p=G.verticesv.firstarc;p;p=p-nextar

36、c;) w=p-adjvex; w=p-adjvex; if(!visitedw) if(!visitedw) DFS(G,W); DFS(G,W); /對(duì)對(duì)v v未訪問過(guò)的鄰接頂點(diǎn)未訪問過(guò)的鄰接頂點(diǎn)w w遞歸調(diào)用遞歸調(diào)用DFSDFS /for/for /DFS/DFS7.3.1深度優(yōu)先搜索遍歷圖深度優(yōu)先搜索遍歷圖查找的順序?yàn)椋翰檎业捻樞驗(yàn)椋? 1、2 2、4 4、8 8、5 5、6 6、3 3、7 72 21 13 34 45 56 67 78 8121 1241248124851248612483612480 00 00 00 00 00 00 00 01 12 23 34 45 56 6

37、7 78 81 11 11 11 11 11 11 11 11 12 24 48 85 56 63 37 761248371243861248612481241217.3.2 廣度優(yōu)先搜索遍歷圖廣度優(yōu)先搜索遍歷圖 廣度優(yōu)先搜索廣度優(yōu)先搜索的基本思想是：從圖中某頂點(diǎn)的基本思想是：從圖中某頂點(diǎn)v v出發(fā)，出發(fā)，在訪問了在訪問了v v之后依次訪問之后依次訪問v v的各個(gè)未曾訪問過(guò)的鄰接點(diǎn)，然的各個(gè)未曾訪問過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問

38、的頂點(diǎn)的鄰接點(diǎn)被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，則需要另選一個(gè)未到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，則需要另選一個(gè)未曾被訪問過(guò)的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過(guò)程，直至曾被訪問過(guò)的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問到為止。換句話說(shuō)，廣度優(yōu)先搜索圖中所有頂點(diǎn)都被訪問到為止。換句話說(shuō)，廣度優(yōu)先搜索遍歷圖的過(guò)程是以遍歷圖的過(guò)程是以v v為起點(diǎn)，由近至遠(yuǎn)，依次訪問和為起點(diǎn)，由近至遠(yuǎn)，依次訪問和v v有路有路徑相通且路徑長(zhǎng)度為徑相通且路徑長(zhǎng)度為1,2.1,2.的頂點(diǎn)。的頂點(diǎn)。7.3.2

39、 廣度優(yōu)先搜索遍歷圖廣度優(yōu)先搜索遍歷圖例如，從例如，從v3v3開始對(duì)下圖進(jìn)行廣度優(yōu)先搜索遍歷的過(guò)程為：首先訪問開始對(duì)下圖進(jìn)行廣度優(yōu)先搜索遍歷的過(guò)程為：首先訪問v3v3和和v3v3的鄰接點(diǎn)的鄰接點(diǎn)v2v2、v1v1和和v6v6，然后依次訪問，然后依次訪問v2v2的鄰接點(diǎn)的鄰接點(diǎn)v4v4和和v6v6的鄰的鄰接點(diǎn)接點(diǎn)v5v5，接著訪問，接著訪問v4v4的鄰接點(diǎn)的鄰接點(diǎn)v9v9，最后訪問，最后訪問v5v5的鄰接點(diǎn)的鄰接點(diǎn)v8v8和和v7v7。由。由于這些頂點(diǎn)的鄰接點(diǎn)都已經(jīng)被訪問，并且圖中所有頂點(diǎn)都已被訪問于這些頂點(diǎn)的鄰接點(diǎn)都已經(jīng)被訪問，并且圖中所有頂點(diǎn)都已被訪問到，廣度優(yōu)先遍歷至此結(jié)束。到，廣度優(yōu)先遍

40、歷至此結(jié)束。124987563一層一層二層二層三層三層訪問序列為：訪問序列為： v3- v2- v1- v6- v4- v5- v9- v8- v7 3216459877.3.2 廣度優(yōu)先搜索遍歷圖廣度優(yōu)先搜索遍歷圖 可見，圖的廣度優(yōu)先搜索過(guò)程類可見，圖的廣度優(yōu)先搜索過(guò)程類似于樹的層次遍歷。和深度優(yōu)先搜索類似于樹的層次遍歷。和深度優(yōu)先搜索類似，在遍歷的過(guò)程中也需要借助于訪問似，在遍歷的過(guò)程中也需要借助于訪問標(biāo)志數(shù)組標(biāo)志數(shù)組visitedvisited。并且為了實(shí)現(xiàn)按照頂。并且為了實(shí)現(xiàn)按照頂點(diǎn)被訪問的先后次序查詢它們的鄰接點(diǎn)，點(diǎn)被訪問的先后次序查詢它們的鄰接點(diǎn)，需附設(shè)一個(gè)隊(duì)列依訪問次序存儲(chǔ)已被訪

41、需附設(shè)一個(gè)隊(duì)列依訪問次序存儲(chǔ)已被訪問的頂點(diǎn)。對(duì)以鄰接矩陣表示方法存儲(chǔ)問的頂點(diǎn)。對(duì)以鄰接矩陣表示方法存儲(chǔ)的圖進(jìn)行廣度優(yōu)先遍歷的算法如的圖進(jìn)行廣度優(yōu)先遍歷的算法如7.57.5所示。所示。7.3.2 廣度優(yōu)先搜索遍歷圖廣度優(yōu)先搜索遍歷圖算法算法7.57.5void BFSTraverse(MGraph G)void BFSTraverse(MGraph G) bool visitedG.vexnum; bool visitedG.vexnum; /附設(shè)訪問標(biāo)志數(shù)組附設(shè)訪問標(biāo)志數(shù)組 SqQueue Q; SqQueue Q; /附設(shè)循環(huán)隊(duì)列附設(shè)循環(huán)隊(duì)列Q Q for(v=0;vG.vexnum;+v)

42、 visitedv=FALSE; for(v=0;vG.vexnum;+v) visitedv=FALSE; InitQueve(Q,G.vexnum); InitQueve(Q,G.vexnum); for(v=0;vG.vexnum;+v) for(v=0;vG.vexnum;+v) if(!visitedv) if(!visitedv) visitedv=TRUE;VisitFunc(G.vexv); visitedv=TRUE;VisitFunc(G.vexv); /訪問第訪問第v v個(gè)頂點(diǎn)個(gè)頂點(diǎn) EnQueue_Sq(Q,v); EnQueue_Sq(Q,v); /v/v入隊(duì)列入隊(duì)列

43、 while(!QueueEmpty_Sq(Q)while(!QueueEmpty_Sq(Q) DeQueue_Sq(Q,u); DeQueue_Sq(Q,u); /隊(duì)頭元素出隊(duì)并置為隊(duì)頭元素出隊(duì)并置為u u for(w=0;wG.vexnum;w+) for(w=0;wG.vexnum;w+) if(G.arcsu,w.adj & !visitedw) if(G.arcsu,w.adj & !visitedw) visitedw=TRUE; VisitFunc(w); visitedw=TRUE; VisitFunc(w); /訪問圖中第訪問圖中第w w個(gè)頂點(diǎn)個(gè)頂點(diǎn) EnQu

44、eue_Sq(Q,w); EnQueue_Sq(Q,w); /當(dāng)前訪問的頂點(diǎn)當(dāng)前訪問的頂點(diǎn)w w入隊(duì)列入隊(duì)列Q Q /if/if /while/while /if/if /BFSTraverse/BFSTraverse7.3.2 廣度優(yōu)先搜索遍歷圖廣度優(yōu)先搜索遍歷圖 從以上幾個(gè)算法中可以看出，遍歷圖的過(guò)程從以上幾個(gè)算法中可以看出，遍歷圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，其消實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，其消耗時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。因此若采耗時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。因此若采用同樣的存儲(chǔ)結(jié)構(gòu)，廣度優(yōu)先遍歷的時(shí)間復(fù)用同樣的存儲(chǔ)結(jié)構(gòu)，廣度優(yōu)先遍歷的時(shí)間復(fù)雜度和深度優(yōu)先搜索相同。由于

45、算法雜度和深度優(yōu)先搜索相同。由于算法7.57.5中中的存儲(chǔ)結(jié)構(gòu)為鄰接矩陣，因此算法的存儲(chǔ)結(jié)構(gòu)為鄰接矩陣，因此算法7.57.5的時(shí)的時(shí)間復(fù)雜度為間復(fù)雜度為O(nO(n2 2) )。 圖遍歷是圖的基本操作，也是一些圖的應(yīng)用圖遍歷是圖的基本操作，也是一些圖的應(yīng)用問題求解算法的基礎(chǔ)，以此為框架可以派生問題求解算法的基礎(chǔ)，以此為框架可以派生出許多應(yīng)用算法。出許多應(yīng)用算法。7.4 圖的連通性問題圖的連通性問題 7.4.1 無(wú)向圖的連通分量和生成樹無(wú)向圖的連通分量和生成樹 7.4.2 有向圖的強(qiáng)連通分量有向圖的強(qiáng)連通分量 7.4.3 連通網(wǎng)的最小生成樹連通網(wǎng)的最小生成樹 7.4.1 無(wú)向圖的連通分量和生成樹

46、無(wú)向圖的連通分量和生成樹 對(duì)于連通圖從任一頂點(diǎn)出發(fā)進(jìn)行深度（廣度）對(duì)于連通圖從任一頂點(diǎn)出發(fā)進(jìn)行深度（廣度）優(yōu)先遍歷，即可訪問到圖的所有頂點(diǎn)；對(duì)于非連通優(yōu)先遍歷，即可訪問到圖的所有頂點(diǎn)；對(duì)于非連通圖需要從多個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷。圖需要從多個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷。(a) 非連通圖非連通圖(b) 非連通圖的兩個(gè)極大連通分量非連通圖的兩個(gè)極大連通分量ABCDEFACDBEF 7.4.1 無(wú)向圖的連通分量和生成樹無(wú)向圖的連通分量和生成樹 設(shè)連通圖設(shè)連通圖G邊的集合為邊的集合為E(G)，將，將E(G)分為兩個(gè)集合分為兩個(gè)集合T(G)和和B(G)，T(G)為遍歷圖過(guò)程中經(jīng)歷的邊的集合，為遍歷圖過(guò)程中經(jīng)歷的邊的集合

47、， B(G)為為剩余的邊。剩余的邊。T(G)和和G中所有頂點(diǎn)一起構(gòu)成連通圖中所有頂點(diǎn)一起構(gòu)成連通圖G的極大連的極大連通子圖，是連通圖的生成樹。如果遍歷采用深度優(yōu)先搜索，通子圖，是連通圖的生成樹。如果遍歷采用深度優(yōu)先搜索，則得到的則得到的深度優(yōu)先生成樹深度優(yōu)先生成樹；如果遍歷采用廣度優(yōu)先搜索，則；如果遍歷采用廣度優(yōu)先搜索，則得到的得到的廣度優(yōu)先生成樹廣度優(yōu)先生成樹。而非連通圖只有生成樹林。而非連通圖只有生成樹林。(a) 連通圖連通圖1 12 23 34 45 56 67 78 8（b）深度優(yōu)先生成樹）深度優(yōu)先生成樹1 12 24 48 85 56 67 73 3(c)廣度優(yōu)先生成樹廣度優(yōu)先生成樹

48、7 76 65 54 48 82 23 31 1 7.4.2 有向圖的強(qiáng)連通分量有向圖的強(qiáng)連通分量(a) 非強(qiáng)連通圖非強(qiáng)連通圖(b) 非強(qiáng)連通圖兩個(gè)強(qiáng)連通分量非強(qiáng)連通圖兩個(gè)強(qiáng)連通分量 在有向圖在有向圖G中，如果對(duì)于每一對(duì)中，如果對(duì)于每一對(duì)vi,vjV，vi,vj ，從從vi到到vj和從和從vj到到vi都存在路徑，則都存在路徑，則G是強(qiáng)連通圖。是強(qiáng)連通圖。有向圖中的最大連通子圖稱作有向圖的強(qiáng)連通分量。有向圖中的最大連通子圖稱作有向圖的強(qiáng)連通分量。ACBFDGECBDEAF7.4.3 連通網(wǎng)的最小生成樹連通網(wǎng)的最小生成樹 在一個(gè)含有在一個(gè)含有n n個(gè)頂點(diǎn)的連通圖中，必能從中選出個(gè)頂點(diǎn)的連通圖中，必

49、能從中選出n-1n-1條邊條邊構(gòu)成一個(gè)極小連通子圖，它含有圖中全部構(gòu)成一個(gè)極小連通子圖，它含有圖中全部n n個(gè)頂點(diǎn)，但只有足個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的以構(gòu)成一棵樹的n-1n-1條邊，稱這棵樹為連通圖的條邊，稱這棵樹為連通圖的生成樹生成樹。例如，。例如，對(duì)下圖對(duì)下圖(a)(a)進(jìn)行深度優(yōu)先搜索遍歷過(guò)程中經(jīng)過(guò)的邊和全部頂點(diǎn)進(jìn)行深度優(yōu)先搜索遍歷過(guò)程中經(jīng)過(guò)的邊和全部頂點(diǎn)構(gòu)成的極小連通子圖構(gòu)成的極小連通子圖(b)(b)即為即為(a)(a)的一棵生成樹。的一棵生成樹。124987563124987563(a)(b)7.4 連通網(wǎng)的最小生成樹連通網(wǎng)的最小生成樹 在含有在含有n n個(gè)頂點(diǎn)的連通網(wǎng)中選擇個(gè)頂

50、點(diǎn)的連通網(wǎng)中選擇n-1n-1條邊，構(gòu)成一棵極小連通子圖，條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中并使該連通子圖中n-1n-1條邊上權(quán)值之條邊上權(quán)值之和達(dá)到最小，則稱其為和達(dá)到最小，則稱其為連通網(wǎng)的最連通網(wǎng)的最小生成樹小生成樹。例如，對(duì)于如右圖所示。例如，對(duì)于如右圖所示的連通網(wǎng)可以有多棵權(quán)值總和不相的連通網(wǎng)可以有多棵權(quán)值總和不相同的生成樹。同的生成樹。abcdefg1216431489106527abcdefg1639627abcdefg1243827abcdefg1216414810(a)權(quán)值總和為權(quán)值總和為43(b)權(quán)值總和為權(quán)值總和為36(a)權(quán)值總和為權(quán)值總和為64權(quán)值序列：權(quán)值序列

51、：2 3 4 5 6 7 8 9 10 12 14 167.4 連通網(wǎng)的最小生成樹連通網(wǎng)的最小生成樹構(gòu)造連通網(wǎng)的最小生成樹的算法主要有兩種。構(gòu)造連通網(wǎng)的最小生成樹的算法主要有兩種。1.1.克魯斯卡爾克魯斯卡爾(Kruskal)(Kruskal)算法算法基本思想：按照權(quán)值從小到大的順序選擇基本思想：按照權(quán)值從小到大的順序選擇n-1n-1條邊，并保證這條邊，并保證這n-1n-1條邊不構(gòu)條邊不構(gòu)成回路。成回路。具體做法：首先構(gòu)造一個(gè)只含具體做法：首先構(gòu)造一個(gè)只含n n個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成

52、一棵樹網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止。為止。abcdefg1216431489106527abcdefg1243827(c,e)產(chǎn)生回路產(chǎn)生回路(c,f)產(chǎn)生回路產(chǎn)生回路(f,g)產(chǎn)生回路產(chǎn)生回路(b,c)產(chǎn)生回路產(chǎn)生回路已選出已選出n-1條邊條邊7.4 連通網(wǎng)的最小生成樹連通網(wǎng)的最小生成樹2.2.普里姆普里姆(Prim)(Prim)算法算法 假設(shè)假設(shè)G=(V,E)G=(V,E)為一網(wǎng)，其中為一網(wǎng)，其中V V為網(wǎng)中所有頂為網(wǎng)中所有頂點(diǎn)的集合，點(diǎn)的集合，E E為網(wǎng)中所有帶權(quán)邊的集合。設(shè)置兩為網(wǎng)中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合個(gè)新的集合U U和和T T，其

53、中，其中U U用于存放用于存放G G的最小生成樹的最小生成樹中的頂點(diǎn)，中的頂點(diǎn)，T T存放存放G G的最小生成樹中的邊。令的最小生成樹中的邊。令U U的的初值為初值為U=uU=u0 0 ( (假設(shè)從頂點(diǎn)假設(shè)從頂點(diǎn)u u0 0出發(fā)構(gòu)造最小生成出發(fā)構(gòu)造最小生成樹樹) )，令，令T T的初值為空，的初值為空，T=T=。 普里姆算法的思想是：從所有普里姆算法的思想是：從所有u?Uu?U，v?V-Uv?V-U的邊中選取權(quán)值最小的邊的邊中選取權(quán)值最小的邊(u, v)(u, v)，將頂點(diǎn)，將頂點(diǎn)v v加入加入集合集合U U中，將邊中，將邊(u, v)(u, v)加入集合加入集合T T中，如此不斷重中，如此不

54、斷重復(fù)，直到復(fù)，直到U=VU=V為止，最小生成樹構(gòu)造完畢，這時(shí)為止，最小生成樹構(gòu)造完畢，這時(shí)集合集合T T中包含了最小生成樹中的所有邊。中包含了最小生成樹中的所有邊。7.4 連通網(wǎng)的最小生成樹連通網(wǎng)的最小生成樹例如，利用例如，利用PrimPrim算法對(duì)下圖從頂點(diǎn)算法對(duì)下圖從頂點(diǎn)a a開始構(gòu)造最小生開始構(gòu)造最小生成樹。成樹。abcdefg1216431489106527abcdefgU:aT:(a,b):12(a,f):16(a,g):1412U: a, b T: (a,b) (a,f):16(a,g):14(b,c):10(b,f):77U: a, b, f T: (a,b) , (b,f)

55、(a,g):14(b,c):10(f,c):6(f,e):2(f,g):92U: a, b, e, f T: (a,b) , (b,f) , (f,e) (a,g):14(b,c):10(e,c):5(e,d):4(e,g):8(f,c):6(f,g):94U: a, b, d, e, f T: (a,b) , (b,f) , (f,e) , (e,d) (a,g):14(e,g):8(f,g):9(b,c):10(d,c):3(e,c):5(f,c):63U: a, b, c, d, e, f T: (a,b) , (b,f) , (f,e) , (e,d) , (d,c) (a,g):14

56、(e,g):8(f,g):98U: a, b, c, d, e, f, g T: (a,b) , (b,f) , (f,e) , (e,d) , (d,c) , (e,g)此時(shí)，所有頂點(diǎn)都已加入集合此時(shí)，所有頂點(diǎn)都已加入集合U，即，即UV，最小生成樹構(gòu)造完畢。，最小生成樹構(gòu)造完畢。7.4 連通網(wǎng)的最小生成樹連通網(wǎng)的最小生成樹比較以上兩種算法可見：比較以上兩種算法可見： KurskalKurskal算法主要對(duì)邊進(jìn)行操作，又稱為算法主要對(duì)邊進(jìn)行操作，又稱為“加加邊法邊法”，其時(shí)間復(fù)雜度為，其時(shí)間復(fù)雜度為O(e)O(e)。這種方法比。這種方法比較適用于稀疏圖。較適用于稀疏圖。 PrimPrim算法主

57、要對(duì)頂點(diǎn)進(jìn)行操作，又稱為算法主要對(duì)頂點(diǎn)進(jìn)行操作，又稱為“加加點(diǎn)法點(diǎn)法”，其時(shí)間復(fù)雜度為，其時(shí)間復(fù)雜度為O(nO(n2 2) )。比較適用于。比較適用于稠密圖。稠密圖。7.5 有向無(wú)環(huán)圖及其應(yīng)用有向無(wú)環(huán)圖及其應(yīng)用 一個(gè)無(wú)環(huán)的有向圖稱為一個(gè)無(wú)環(huán)的有向圖稱為有向無(wú)環(huán)圖有向無(wú)環(huán)圖（directed acycline graphdirected acycline graph），簡(jiǎn)），簡(jiǎn)稱稱DAGDAG。abced 有向無(wú)環(huán)圖是描述一項(xiàng)系統(tǒng)或工程的有向無(wú)環(huán)圖是描述一項(xiàng)系統(tǒng)或工程的進(jìn)行過(guò)程進(jìn)行過(guò)程的有效工具，常用來(lái)判斷工的有效工具，常用來(lái)判斷工程能否順利進(jìn)行及估算完成時(shí)間。程能否順利進(jìn)行及估算完成時(shí)間。7.

58、5.1 拓?fù)渑判蛲負(fù)渑判?有向無(wú)環(huán)圖有向無(wú)環(huán)圖在工程計(jì)劃和管理方面有在工程計(jì)劃和管理方面有著廣泛的應(yīng)用。一項(xiàng)工程往往可以分解為著廣泛的應(yīng)用。一項(xiàng)工程往往可以分解為一些具有相對(duì)獨(dú)立性的子工程，稱這些子一些具有相對(duì)獨(dú)立性的子工程，稱這些子工程為工程為活動(dòng)活動(dòng)。子工程之間在進(jìn)行的時(shí)間上。子工程之間在進(jìn)行的時(shí)間上有著一定的相互制約關(guān)系?？梢杂糜邢驁D有著一定的相互制約關(guān)系?？梢杂糜邢驁D表示子工程及其相互制約關(guān)系，其中以表示子工程及其相互制約關(guān)系，其中以頂頂點(diǎn)點(diǎn)表示活動(dòng)表示活動(dòng)，弧弧表示活動(dòng)之間的表示活動(dòng)之間的優(yōu)先制約優(yōu)先制約關(guān)系關(guān)系，稱這種有向圖為，稱這種有向圖為活動(dòng)在頂點(diǎn)上活動(dòng)在頂點(diǎn)上的網(wǎng)的網(wǎng)絡(luò)，簡(jiǎn)稱

59、絡(luò)，簡(jiǎn)稱活動(dòng)頂點(diǎn)網(wǎng)絡(luò)活動(dòng)頂點(diǎn)網(wǎng)絡(luò)(Activity On (Activity On Vertex Network)Vertex Network)，或，或AOVAOV網(wǎng)網(wǎng)。7.5.1 拓?fù)渑判蛲負(fù)渑判蚴裁词峭負(fù)渑判颍渴裁词峭負(fù)渑判颍咳艏先艏蟈 X上的關(guān)系上的關(guān)系R R是自反的、反對(duì)稱的和傳遞的，是自反的、反對(duì)稱的和傳遞的，則稱則稱R R是集合是集合X X上的偏序關(guān)系。上的偏序關(guān)系。設(shè)設(shè)R R是集合是集合X X上的偏序，如果對(duì)每個(gè)上的偏序，如果對(duì)每個(gè)x,yXx,yX必有必有xRyxRy或或yRxyRx，則稱，則稱R R是集合是集合X X上的全序關(guān)系。上的全序關(guān)系。由某個(gè)集合上的一個(gè)偏序得到該集

60、合上的一個(gè)全序，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱為拓?fù)渑判?。這個(gè)操作稱為拓?fù)渑判?。v2v1v4v3v2v1v4v37.5.1 拓?fù)渑判蛲負(fù)渑判蚶纾谡n程計(jì)劃中，每門課程的學(xué)習(xí)就是一項(xiàng)活動(dòng)，一門課程可能以例如，在課程計(jì)劃中，每門課程的學(xué)習(xí)就是一項(xiàng)活動(dòng)，一門課程可能以其他某幾門課程為先修基礎(chǔ)，而它本身又可能是另一些課程的先修基礎(chǔ)，其他某幾門課程為先修基礎(chǔ)，而它本身又可能是另一些課程的先修基礎(chǔ)，各課程之間的先修關(guān)系可用活動(dòng)頂點(diǎn)網(wǎng)絡(luò)表示。各課程之間的先修關(guān)系可用活動(dòng)頂點(diǎn)網(wǎng)絡(luò)表示。C2C1C9C3C11C4C6C12C8C7C5C13C10課程號(hào)課程號(hào)課程名課程名先修課先修課C C1 1C C語(yǔ)言程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)無(wú)無(wú)C C2 2計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論無(wú)無(wú)C C3 3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)C C1 1 ，