數(shù)據(jù)結(jié)構(gòu)第7章

1、第第7章章 圖圖 7.1 圖的定義與基本術(shù)語圖的定義與基本術(shù)語 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 7.3 圖的遍歷圖的遍歷 7.4 圖的連通性問題圖的連通性問題 7.5 有向無環(huán)圖的應(yīng)用有向無環(huán)圖的應(yīng)用 7.6 最短路徑最短路徑 引言 圖（Graph）是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 結(jié)點之間的關(guān)系可以是任意的，不受限制，圖中任意兩個元素之間都可能相關(guān)。 圖有著更為廣泛的應(yīng)用，已經(jīng)滲透到計算機(jī)、邏輯學(xué)、物理、化學(xué)、通信、甚至日常生活中，圖論是計算機(jī)的重要理論分支。7.1 圖的定義和術(shù)語圖的定義和術(shù)語 圖圖(Graph)G由兩個集合由兩個集合V(Vertex)和和E(Edge)組成組成,記為

2、記為G=(V,E),其中其中V是頂點的有限集合是頂點的有限集合,記為記為V(G),E是連接是連接V中兩個中兩個不同頂點不同頂點(頂點對頂點對)的邊的有限集合的邊的有限集合,記為記為E(G)。 在圖在圖G中中,如果代表邊的頂點對是無序的如果代表邊的頂點對是無序的,則稱則稱G為為無向圖無向圖,無向圖中代表邊的無序頂點對通常用圓括號括起來無向圖中代表邊的無序頂點對通常用圓括號括起來,用以表示用以表示一條無向邊。一條無向邊。 如果表示邊的頂點對是有序的如果表示邊的頂點對是有序的,則稱則稱G為為有向圖有向圖,在有向圖在有向圖中代表邊的頂點對通常用尖括號括起來中代表邊的頂點對通常用尖括號括起來 。（。（弧

3、弧）1. 圖的定義圖的定義 有向圖、無向圖示例有向圖、無向圖示例 本章不予討論的圖本章不予討論的圖2. 基本術(shù)語基本術(shù)語 l完全圖、稀疏圖與稠密圖完全圖、稀疏圖與稠密圖n:圖中頂點的個數(shù)圖中頂點的個數(shù); e:圖中邊或弧的數(shù)目。圖中邊或弧的數(shù)目。無向圖其邊數(shù)無向圖其邊數(shù)e的取值范圍是的取值范圍是0n(n-1)/2。 無向完全圖無向完全圖：有：有n(n-1)/2條邊的無向圖。條邊的無向圖。有向圖其邊數(shù)有向圖其邊數(shù)e的取值范圍是的取值范圍是0n(n-1)。 有向完全圖有向完全圖：有：有n(n-1)條邊的有向圖。條邊的有向圖。 稀疏圖稀疏圖：對于有很少條邊的圖：對于有很少條邊的圖(enlogn)， 反

4、之稱為反之稱為稠密圖稠密圖。 1 0 2 3 1 0 2 3 (a) (b) l子圖子圖有兩個圖有兩個圖G=(V, E)和圖和圖G=(V, E), 若若V V且且E E, 則稱圖則稱圖G為為G的子圖。的子圖。l鄰接點鄰接點 1 3 0 2 4 (a) (b) 1 3 0 2 4 1 3 0 2 4 (c) l頂點的度、入度和出度頂點的度、入度和出度在無向圖中在無向圖中,頂點所具有的邊的數(shù)目稱為該頂點所具有的邊的數(shù)目稱為該頂點的度頂點的度。在有向圖中在有向圖中,以頂點以頂點v為頭的弧的數(shù)目為頭的弧的數(shù)目,稱為該頂點的稱為該頂點的入度入度。以頂。以頂點點v為尾的弧的數(shù)目為尾的弧的數(shù)目,稱為該頂點的

5、稱為該頂點的出度出度。一個頂點的入度與出。一個頂點的入度與出度的和為該頂點的度。度的和為該頂點的度。一般地，一般地， 若圖若圖G中有中有n個頂點，個頂點，e條邊或弧，則圖中頂點的度與條邊或弧，則圖中頂點的度與邊的關(guān)系如下：邊的關(guān)系如下： 2)(1niivTDel 權(quán)與網(wǎng)權(quán)與網(wǎng) 在實際應(yīng)用中，有時圖的邊或弧上往往與具有一定意義的在實際應(yīng)用中，有時圖的邊或弧上往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可以表示從一個頂點到另一個頂點的距離或耗費等信息。我們以表示從一個頂點到另一個頂點的距離或耗費等信息。我們將這種帶權(quán)的圖

6、叫做將這種帶權(quán)的圖叫做賦權(quán)圖賦權(quán)圖或或網(wǎng)網(wǎng)。 l路徑與回路路徑與回路 無向圖無向圖G=(V,E)中從頂點中從頂點v到到v的路徑是一個頂點序列的路徑是一個頂點序列vi0,vi1,vi2,vin，其中，其中(vij-1, vij)E, 1jn。如果圖。如果圖G是有向圖，是有向圖，則路徑也是有向的，頂點序列應(yīng)滿足則路徑也是有向的，頂點序列應(yīng)滿足E， 1jn。路徑的長度路徑的長度: 路徑上經(jīng)過的弧或邊的數(shù)目。路徑上經(jīng)過的弧或邊的數(shù)目?；芈坊芈坊蚧颦h(huán)環(huán): 簡單路徑簡單路徑:表示路徑的頂點序列中的頂點各不相同。表示路徑的頂點序列中的頂點各不相同。簡單回路簡單回路:除了第一個和最后一個頂點外，其余各頂點均不

7、重除了第一個和最后一個頂點外，其余各頂點均不重復(fù)出現(xiàn)的回路。復(fù)出現(xiàn)的回路。 l連通圖、強(qiáng)連通圖連通圖、強(qiáng)連通圖 在無（有）向圖在無（有）向圖G=G=中，若對任何兩個頂點中，若對任何兩個頂點u、v都存在都存在從從u到到v的路徑，則稱的路徑，則稱G G是連通圖是連通圖( (強(qiáng)連通圖強(qiáng)連通圖) )。(b)(b)非連通圖非連通圖 V0V0 V1V1 V2V2 V3V3(c)(c)強(qiáng)連通圖強(qiáng)連通圖(a)(a)連通圖連通圖V0V0V3V3V2V2V1V1V4V4V5V5(d)(d)非強(qiáng)連通圖非強(qiáng)連通圖 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3連通分量連通分量

8、:無向圖中的極大連通子圖。無向圖中的極大連通子圖。強(qiáng)連通分量強(qiáng)連通分量: 有向圖的極大強(qiáng)連通子圖。有向圖的極大強(qiáng)連通子圖。非連通圖，有兩個連通分量非連通圖，有兩個連通分量 V0V0 V1V1 V2V2 V3V3非強(qiáng)連通圖非強(qiáng)連通圖 V0V0 V1V1 V2V2 V3V3有兩個強(qiáng)連通分量有兩個強(qiáng)連通分量V0V0V3V3V2V2V1V1V4V4V5V5l生成樹生成樹: 連通圖的生成樹是一個極小連通子圖，它含有圖連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的中全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。條邊。 例例1 1 交通圖（公路、鐵路）交通圖（公路、鐵路） 頂點：

9、地點頂點：地點 邊：連接地點的公路邊：連接地點的公路 交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；圖的應(yīng)用示例圖的應(yīng)用示例 例例2 2 電路圖電路圖 頂點：元件頂點：元件 邊：連接元件之間的線路邊：連接元件之間的線路 例例3 3 通訊線路圖通訊線路圖 頂點：地點頂點：地點 邊：地點間的連線邊：地點間的連線 例例4 4 各種流程圖各種流程圖 如產(chǎn)品的生產(chǎn)流程圖如產(chǎn)品的生產(chǎn)流程圖 頂點：工序頂點：工序 邊：各道工序之間的順序關(guān)系邊：各道工序之間的順序關(guān)系 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3

10、V37.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)1. 鄰接矩陣表示法（數(shù)組表示法）鄰接矩陣表示法（數(shù)組表示法） l圖圖G是一個具有是一個具有n個頂點的無權(quán)圖，個頂點的無權(quán)圖，G的鄰接矩陣是具有如下的鄰接矩陣是具有如下性質(zhì)的性質(zhì)的nn矩陣矩陣A： 1, ,), , 0, ijijv vv vEA i j若(或其它l若圖若圖G是一個有是一個有n個頂點的網(wǎng)，則它的鄰接矩陣是具有如下性個頂點的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的質(zhì)的nn矩陣矩陣A：, ,), , , ijijijwv vv vEA i j若(或其它 1 3 0 2 4 1 3 0 2 4 (a) (b ) 011011011111010011011

11、10101A 01001000001100001100010102A8273496221V32V2V4V1V6V5 8 7 4 9 8 2 1 2 3 2 7 1 3 2 4 2 6 9 2 2 6 1234561 2 3 4 5 6l網(wǎng)的數(shù)組表示法網(wǎng)的數(shù)組表示法鄰接矩陣表示法類型描述鄰接矩陣表示法類型描述 define MAX_VERTEX_NUM 20 /最多頂點個數(shù)最多頂點個數(shù)define INFINITY INT_MAX /表示極大值表示極大值typedef enumDG, DN, UDG, UDN GraphKind; typedef struct ArcCell VRType ad

12、j; InfoType *info; ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點向量頂點向量 AdjMatrix arcs; /鄰接矩陣鄰接矩陣 int vexnum, arcnum; /圖的頂點數(shù)和弧數(shù)圖的頂點數(shù)和弧數(shù) GraphKind kind; /圖的種類標(biāo)志圖的種類標(biāo)志 MGraph;鄰接矩陣的特點如下鄰接矩陣的特點如下：(1)(1)圖的鄰接矩陣表示是惟一的。圖的鄰接矩陣表示是惟一的。(2)(2)無向圖的鄰接矩陣一定是一個對稱矩陣。因

13、此無向圖的鄰接矩陣一定是一個對稱矩陣。因此, ,按照壓縮存按照壓縮存儲的思想儲的思想, ,在具體存放鄰接矩陣時只需存放上在具體存放鄰接矩陣時只需存放上( (或下或下) )三角形陣三角形陣的元素即可。的元素即可。(3)(3)判斷兩頂點判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為是否為1；(4) 頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值量賦值1或清或清0；(5)不帶權(quán)的有向圖的鄰接矩陣一般來說是一個稀疏矩陣不帶權(quán)的有向圖的鄰接矩陣一般來說是一個稀疏矩陣,因此因此,當(dāng)圖的頂點較多時當(dāng)圖

14、的頂點較多時,可以采用三元組表的方法存儲鄰接矩陣?？梢圆捎萌M表的方法存儲鄰接矩陣。(6) 對于無向圖對于無向圖,鄰接矩陣的第鄰接矩陣的第i行行(或第或第i列列)非零元素非零元素(或非或非元元素素)的個數(shù)正好是第的個數(shù)正好是第i個頂點個頂點vi的度。的度。(7)(7)對于有向圖對于有向圖, ,鄰接矩陣的第鄰接矩陣的第i i行行( (或第或第i i列列) )非零元素非零元素( (或非或非元素元素) )的個數(shù)正好是第的個數(shù)正好是第i i個頂點個頂點v vi i的出度的出度( (或入度或入度) )。(8)(8)用鄰接矩陣方法存儲圖用鄰接矩陣方法存儲圖, ,很容易確定圖中任意兩個頂點之很容易確定圖中

15、任意兩個頂點之間是否有邊相連。但是間是否有邊相連。但是, ,要確定圖中有多少條邊要確定圖中有多少條邊, ,則必須按行、則必須按行、按列對每個元素進(jìn)行檢測按列對每個元素進(jìn)行檢測, ,所花費的時間代價很大。這是用鄰所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。接矩陣存儲圖的局限性。2.2.鄰接表存儲方法鄰接表存儲方法 圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲方法。在鄰接表中的存儲方法。在鄰接表中, ,對圖中每個頂點建立一個單鏈表對圖中每個頂點建立一個單鏈表, ,第第i i個單鏈表中的結(jié)點表示依附于頂點個單鏈表中的結(jié)點表示依附于頂點

16、v vi i的邊的邊( (對有向圖是以頂對有向圖是以頂點點v vi i為尾的弧為尾的弧) )。每個單鏈表上附設(shè)一個表頭結(jié)點。表結(jié)點和。每個單鏈表上附設(shè)一個表頭結(jié)點。表結(jié)點和表頭結(jié)點的結(jié)構(gòu)如下：表頭結(jié)點的結(jié)構(gòu)如下：adjvexnextarcinfodatafirstarc表結(jié)點表結(jié)點表頭結(jié)點表頭結(jié)點data存儲頂點存儲頂點vi的名稱或其他信息的名稱或其他信息; firstarc指向鏈表中第一個指向鏈表中第一個結(jié)點。結(jié)點。 adjvex指示與頂點指示與頂點vi鄰接的點在圖中的位置鄰接的點在圖中的位置;nextarc指示下一指示下一條邊或弧的結(jié)點條邊或弧的結(jié)點; info存儲與邊或弧相關(guān)的信息存儲與

17、邊或弧相關(guān)的信息,如權(quán)值等。如權(quán)值等。 1 3 0 2 4 1 3 0 2 4 (a) (b) 0 1 2 3 4 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 1 2 3 0 3 3 4 3 v0 v1 v2 v3 v4 (a) (b) 8273496221V32V2V4V1V6V5表頭頂點的鄰接頂點編號和邊相關(guān)的信息指向下一個鄰接頂點的指針(a) 表結(jié)點結(jié)構(gòu)(b) 鄰接鏈表12345628546947183241225262431721336214663219425632V1V2V3V4V5V6l網(wǎng)的鄰接鏈表表示網(wǎng)的鄰接鏈

18、表表示鄰接表存儲結(jié)構(gòu)的類型定義：鄰接表存儲結(jié)構(gòu)的類型定義：typedef struct ArcNode/表結(jié)點結(jié)構(gòu)類型表結(jié)點結(jié)構(gòu)類型int adjvex; /該弧該弧(邊邊)的終點位置的終點位置 struct ArcNode *nextarc; /指向下一條弧的指針指向下一條弧的指針 InfoType info; /該弧的相關(guān)信息該弧的相關(guān)信息 ArcNode;typedef struct Vnode /頭結(jié)點的類型頭結(jié)點的類型Vertex data; /頂點信息頂點信息 ArcNode *firstarc; /指向第一條弧指向第一條弧 VNode, AdjListMAX_VERTEX_NUM

19、;typedef struct /鄰接表鄰接表 AdjList vertices; int vexnum, arcnum; /圖中頂點數(shù)圖中頂點數(shù)n和邊數(shù)和邊數(shù)e int kind; /圖的類型圖的類型 ALGraph; 鄰接表的特點如下鄰接表的特點如下：(1)(1)鄰接表表示不惟一。這是因為在每個頂點對應(yīng)的單鏈表中鄰接表表示不惟一。這是因為在每個頂點對應(yīng)的單鏈表中, ,各邊結(jié)點的鏈接次序可以是任意的各邊結(jié)點的鏈接次序可以是任意的, ,取決于建立鄰接表的算法以取決于建立鄰接表的算法以及邊的輸入次序。及邊的輸入次序。(2)(2)對于有對于有n個頂點和個頂點和e條邊的無向圖條邊的無向圖, ,其鄰接

20、表有其鄰接表有n個頭結(jié)點和個頭結(jié)點和2e個表結(jié)點。顯然個表結(jié)點。顯然, ,在總的邊數(shù)小于在總的邊數(shù)小于n(n-1)/2的情況下的情況下, ,鄰接表比鄰鄰接表比鄰接矩陣要節(jié)省空間。接矩陣要節(jié)省空間。(3)(3)對于無向圖對于無向圖, ,鄰接表的頂點鄰接表的頂點vi對應(yīng)的第對應(yīng)的第i i個鏈表的表結(jié)點數(shù)目個鏈表的表結(jié)點數(shù)目正好是頂點正好是頂點vi的度。的度。(4)(4)對于有向圖對于有向圖, ,鄰接表的頂點鄰接表的頂點vi對應(yīng)的第對應(yīng)的第i i個鏈表的表結(jié)點數(shù)目個鏈表的表結(jié)點數(shù)目僅僅是僅僅是vi的出度。其入度為鄰接表中所有的出度。其入度為鄰接表中所有adjvex域值為域值為i的表結(jié)的表結(jié)點數(shù)目。（

21、點數(shù)目。（逆鄰接表逆鄰接表）圖圖G1的逆鄰接表表示法的逆鄰接表表示法 十字鏈表十字鏈表 鄰接多重表鄰接多重表將有向圖的鄰接表和逆鄰接表結(jié)合在一起，就得到了將有向圖的鄰接表和逆鄰接表結(jié)合在一起，就得到了有向圖有向圖的另的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)一種鏈?zhǔn)酱鎯Y(jié)構(gòu)十字鏈表十字鏈表。十字鏈表十字鏈表vexinfofirstoutfirstin表結(jié)點表結(jié)點頭結(jié)點頭結(jié)點tailvex : 弧尾頂點位置弧尾頂點位置headvex : 弧頭頂點位置弧頭頂點位置tnext : 弧尾相同的下一條弧弧尾相同的下一條弧vexinfo : 頂點的信息頂點的信息firstin : 第一條關(guān)聯(lián)第一條關(guān)聯(lián)入弧入弧結(jié)點結(jié)點first

22、out : 第一條關(guān)聯(lián)第一條關(guān)聯(lián)出弧出弧結(jié)點結(jié)點tailvextnextheadvexhnextarcinfohnext : 弧頭相同的下一條弧弧頭相同的下一條弧arcinfo : 弧的信息弧的信息v1v2v4v3e1e2e4e5e3e6e70123v1v2v3v40 1 e10 2 e22 0 e33 0 e53 1 e63 2 e72 3 e4鄰接多重表鄰接多重表鄰接表是無向圖的一種很有效的存儲結(jié)構(gòu)，在鄰接表中容易求得頂鄰接表是無向圖的一種很有效的存儲結(jié)構(gòu)，在鄰接表中容易求得頂點和邊的各種信息；點和邊的各種信息；但在鄰接表中，每一條邊都有兩個結(jié)點表示，因此在某些對邊進(jìn)行但在鄰接表中，每一條

23、邊都有兩個結(jié)點表示，因此在某些對邊進(jìn)行的操作的操作(例如對搜索過的邊做標(biāo)記例如對搜索過的邊做標(biāo)記)中就需要對每一條邊處理兩遍；中就需要對每一條邊處理兩遍；故引入故引入鄰接多重表鄰接多重表實現(xiàn)實現(xiàn)無向圖無向圖的存儲結(jié)構(gòu)。的存儲結(jié)構(gòu)。鄰接多重表的結(jié)構(gòu)與十字鏈表相似鄰接多重表的結(jié)構(gòu)與十字鏈表相似vexinfo firstedge頭結(jié)點頭結(jié)點vexinfo : 頂點的信息頂點的信息firstedge : 第一條關(guān)聯(lián)邊結(jié)點第一條關(guān)聯(lián)邊結(jié)點表結(jié)點表結(jié)點ivex : 邊的第一個頂點位置邊的第一個頂點位置jvex : 邊的另一個頂點位置邊的另一個頂點位置inext : 頂點頂點 i 的下一條關(guān)聯(lián)邊的下一條關(guān)聯(lián)

24、邊jnext : 頂點頂點 j 的下一條關(guān)聯(lián)邊的下一條關(guān)聯(lián)邊einfo : 邊的信息邊的信息ivex inextjvex jnexteinfomarkmark : 標(biāo)志域，是否遍歷過標(biāo)志域，是否遍歷過作業(yè)：作業(yè)：7.17.3 圖圖 的的 遍遍 歷歷 1.1.圖的遍歷的概念圖的遍歷的概念 從給定圖中任意指定的頂點從給定圖中任意指定的頂點( (稱為初始點稱為初始點) )出發(fā)出發(fā), ,按照某種按照某種搜索方法沿著圖的邊訪問圖中的所有頂點搜索方法沿著圖的邊訪問圖中的所有頂點, ,使每個頂點僅被訪使每個頂點僅被訪問一次問一次, ,這個過程稱為這個過程稱為圖的遍歷圖的遍歷。如果給定圖是連通的無向圖。如果給

25、定圖是連通的無向圖或者是強(qiáng)連通的有向圖或者是強(qiáng)連通的有向圖, ,則遍歷過程一次就能完成則遍歷過程一次就能完成, ,并可按訪問并可按訪問的先后順序得到由該圖所有頂點組成的一個序列。的先后順序得到由該圖所有頂點組成的一個序列。 根據(jù)搜索方法的不同根據(jù)搜索方法的不同, ,圖的遍歷方法有兩種：一種叫做圖的遍歷方法有兩種：一種叫做深深度優(yōu)先搜索法度優(yōu)先搜索法DFS(Depth-First Search)；另一種叫做另一種叫做廣度優(yōu)先廣度優(yōu)先搜索法搜索法BFS (Breadth-First Search)。 2.2.深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷 深度優(yōu)先搜索遍歷的過程是：從圖中某個初始頂點深度優(yōu)先搜索

26、遍歷的過程是：從圖中某個初始頂點v出發(fā)出發(fā), ,首先訪問初始頂點首先訪問初始頂點v, ,然后選擇一個與頂點然后選擇一個與頂點v相鄰且相鄰且沒被訪問過的頂點沒被訪問過的頂點w為初始頂點為初始頂點, ,再從再從w出發(fā)進(jìn)行深度優(yōu)出發(fā)進(jìn)行深度優(yōu)先搜索先搜索, ,直到圖中與當(dāng)前頂點直到圖中與當(dāng)前頂點v鄰接的所有頂點都被訪問鄰接的所有頂點都被訪問過為止。顯然過為止。顯然, ,這個遍歷過程是個遞歸過程。這個遍歷過程是個遞歸過程。 7.3.1 深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索是類似于樹的一種先序遍歷深度優(yōu)先搜索是類似于樹的一種先序遍歷v1v2v3v5v4v6v7v8圖可分為三部分圖可分為三部分:基結(jié)點基結(jié)

27、點第一個鄰接結(jié)點第一個鄰接結(jié)點導(dǎo)出的子圖導(dǎo)出的子圖其它鄰接頂點導(dǎo)其它鄰接頂點導(dǎo)出的子圖出的子圖深度優(yōu)先搜索順序深度優(yōu)先搜索順序: v1v2v4v8v5v3v6v7v1v2v3v5v4v6v7v8過程分析過程分析v1v2v3v4v6v8v5v7深度優(yōu)先搜索順序深度優(yōu)先搜索順序: v1v2v4v8v5v3v6v7棧實現(xiàn)深度優(yōu)先搜索棧實現(xiàn)深度優(yōu)先搜索v1v2v3v4v6v8v5v7深度優(yōu)先搜索順序深度優(yōu)先搜索順序: v1v2v4v8v5v3v6v7v1v2v4v8v5v3v6v7總是從?？偸菑臈ｍ敵霭l(fā)搜頂出發(fā)搜索！索！ 首先將圖中每個頂點的訪問標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個頂點，如果未被訪

28、問，則以該頂點為起始點，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。非連通圖的深度優(yōu)先搜索遍歷非連通圖的深度優(yōu)先搜索遍歷abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg訪問標(biāo)志訪問標(biāo)志: :訪問次序訪問次序: :例如例如:achdkfevoid DFSTraverse(Graph G) for(v=0;vG.vexnum;+v) visitedv = false; for(v=0;vadjvex=0) DFS(G, p-adjvex); /*若若p-adjvex頂

29、點未訪問頂點未訪問, ,遞歸訪問它遞歸訪問它*/ p=p-nextarc; /*p p指向頂點指向頂點v v的下一條弧的弧頭結(jié)點的下一條弧的弧頭結(jié)點*/ 算法分析算法分析l 圖中有圖中有 n 個頂點，個頂點，e 條邊。條邊。l 如果用鄰接表表示圖，沿如果用鄰接表表示圖，沿 firsarc鏈可以找到某個頂鏈可以找到某個頂點點 v 的所有鄰接頂點的所有鄰接頂點 w。由于總共有。由于總共有 2e 個邊結(jié)點，個邊結(jié)點，所以掃描邊的時間為所以掃描邊的時間為O(e)。所以遍歷圖的時間復(fù)雜。所以遍歷圖的時間復(fù)雜性為性為O(n+e)。l 如果用鄰接矩陣表示圖，則查找每一個頂點的所有如果用鄰接矩陣表示圖，則查找

30、每一個頂點的所有的邊，所需時間為的邊，所需時間為O(n)，則遍歷圖中所有的頂點所，則遍歷圖中所有的頂點所需的時間為需的時間為O(n2)。 1 3 0 2 4 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 從頂點從頂點2出發(fā)：出發(fā)：2,1,0,3,4A L M J B F C; D E;G K H I; 0 1 2 3 4 11 12 5 10 1 0 0 3 4 A B C D E F G H I J K L M 2 8 0 7 10 6 6 12 11 7 6 12 9 0 11 9 1 5 6 7 8 9 10 11 12

31、 q從圖中某頂點從圖中某頂點vivi出發(fā)：出發(fā)： 訪問頂點訪問頂點vi vi ； 訪問訪問vi vi 的所有未被訪問的鄰接點的所有未被訪問的鄰接點w w1 1 ,w ,w2 2 , w, wk k ； 依次從這些鄰接點（在步驟依次從這些鄰接點（在步驟中訪問的頂點）出發(fā)，訪問它們的中訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點所有未被訪問的鄰接點; ; 依此類推，直到圖中所有訪問過的頂點依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；的鄰接點都被訪問；q為實現(xiàn)為實現(xiàn)，需要保存在步驟，需要保存在步驟中訪問的頂點，而且中訪問的頂點，而且訪問這訪問這些頂點的些頂點的鄰接點鄰接點的順序為：先保存

32、的頂點，其鄰接點先被的順序為：先保存的頂點，其鄰接點先被訪問。訪問。l廣度優(yōu)先搜索廣度優(yōu)先搜索(BFS)7.3.2 廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索類似于樹的層次遍歷，廣度優(yōu)先搜索類似于樹的層次遍歷，廣度優(yōu)先搜索順序廣度優(yōu)先搜索順序: v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父輩結(jié)點只有父輩結(jié)點被訪問后才會被訪問后才會訪問子孫結(jié)點！訪問子孫結(jié)點！把圖人為的分層，把圖人為的分層，按層遍歷。按層遍歷。v1v2v3v5v4v6v7v8過程分析過程分析廣度優(yōu)先搜索順序廣度優(yōu)先搜索順序: v1v2v3v4v6v5v7v8v1v2v3v4v5v6v7v8Void BFSTr

33、averse(ALGraph G) for (v=0; vG.vexnum; +v) visitedv = FALSE ; InitQueue(Q); for(v=0; vadjvex) visitedp-adjvex=1; printf(%d , p-adjvex); EnQueue(Q, p-adjvex); /if p=p-nextarc; /while(p) /while(!Queue) /if(!visite) /for l圖中每個頂點至多入隊一次，因此外循環(huán)次數(shù)為圖中每個頂點至多入隊一次，因此外循環(huán)次數(shù)為n。l當(dāng)圖當(dāng)圖G采用鄰接表方式存儲，則當(dāng)結(jié)點采用鄰接表方式存儲，則當(dāng)結(jié)點v出隊

34、后，內(nèi)循環(huán)次數(shù)出隊后，內(nèi)循環(huán)次數(shù)等于結(jié)點等于結(jié)點v的度。由于訪問所有頂點的鄰接點的總的時間復(fù)雜的度。由于訪問所有頂點的鄰接點的總的時間復(fù)雜度為度為O(d0+d1+d2+dn-1)=O(e)， 因此圖采用鄰接表方式存儲，因此圖采用鄰接表方式存儲，廣度優(yōu)先搜索算法的時間復(fù)雜度為廣度優(yōu)先搜索算法的時間復(fù)雜度為O(n+e)；l當(dāng)圖當(dāng)圖G采用鄰接矩陣方式存儲，由于找每個頂點的鄰接點時，采用鄰接矩陣方式存儲，由于找每個頂點的鄰接點時，內(nèi)循環(huán)次數(shù)等于內(nèi)循環(huán)次數(shù)等于n，因此廣度優(yōu)先搜索算法的時間復(fù)雜度為，因此廣度優(yōu)先搜索算法的時間復(fù)雜度為O(n2)。 算法分析算法分析 1 3 0 2 4 0 1 2 3 4

35、1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 從頂點從頂點2出發(fā)：出發(fā)：2,1,3,4,0,A L F C B M J; D E;G K I H; 0 1 2 3 4 11 12 5 10 1 0 0 3 4 A B C D E F G H I J K L M 2 8 0 7 10 6 6 12 11 7 6 12 9 0 11 9 1 5 6 7 8 9 10 11 12 A L F C B M J隊列隊列7.4 圖的連通性圖的連通性q利用圖的遍歷運算求解圖的連通性問題利用圖的遍歷運算求解圖的連通性問題F無向圖是否連通、有幾個連通分量，求解無向

36、圖的所無向圖是否連通、有幾個連通分量，求解無向圖的所有連通分量有連通分量深度優(yōu)先生成樹、生成森林深度優(yōu)先生成樹、生成森林廣度優(yōu)先生成樹、生成森林廣度優(yōu)先生成樹、生成森林F有向圖是否是強(qiáng)連通、求解其強(qiáng)連通分量有向圖是否是強(qiáng)連通、求解其強(qiáng)連通分量q求無向網(wǎng)的最小代價生成樹求無向網(wǎng)的最小代價生成樹7.4 圖的連通性問題圖的連通性問題1. 無向圖的連通分量無向圖的連通分量 圖遍歷時，對于連通圖，無論是廣度優(yōu)先搜索還是深度優(yōu)圖遍歷時，對于連通圖，無論是廣度優(yōu)先搜索還是深度優(yōu)先搜索，僅需要調(diào)用一次搜索過程，即從任一個頂點出發(fā)，便先搜索，僅需要調(diào)用一次搜索過程，即從任一個頂點出發(fā)，便可以遍歷圖中的各個頂點。

37、對于非連通圖，則需要多次調(diào)用搜可以遍歷圖中的各個頂點。對于非連通圖，則需要多次調(diào)用搜索過程，而每次調(diào)用得到的頂點訪問序列恰為各連通分量中的索過程，而每次調(diào)用得到的頂點訪問序列恰為各連通分量中的頂點集。頂點集。j=0;for(v=0; v G.vernum; +v) if(!visitedv) DFS(G, v); j+; 1， 2， 4， 3， 9 5， 6， 78， 10 2. 無向圖的生成樹無向圖的生成樹 一個連通圖的生成樹是一個極小連通子圖一個連通圖的生成樹是一個極小連通子圖,它含有圖中它含有圖中全部頂點全部頂點,但只有構(gòu)成一棵樹的但只有構(gòu)成一棵樹的(n-1)條邊。條邊。 en-1 有回

38、路有回路 e=n-1 不一定都是圖的生成樹不一定都是圖的生成樹 設(shè)設(shè)G=(V,E)為連通圖為連通圖,則從圖中任一頂點出發(fā)遍歷圖時則從圖中任一頂點出發(fā)遍歷圖時,必定將必定將E(G)分成兩個集合分成兩個集合T和和B,其中其中T是遍歷圖過程中走過的邊的集是遍歷圖過程中走過的邊的集合合,B是剩余的邊的集合：是剩余的邊的集合：TB=,TB=E(G)。顯然。顯然,G=(V,T)是是G的極小連通子圖的極小連通子圖,即即G是是G的一棵的一棵生成樹生成樹。 由深度優(yōu)先遍歷得到的生成樹稱為由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹深度優(yōu)先生成樹；由廣；由廣度優(yōu)先遍歷得到的生成樹稱為度優(yōu)先遍歷得到的生成樹稱為廣度

39、優(yōu)先生成樹廣度優(yōu)先生成樹。這樣的生成樹。這樣的生成樹是由遍歷時訪問過的是由遍歷時訪問過的n個頂點和遍歷時經(jīng)歷的個頂點和遍歷時經(jīng)歷的n-1條邊組成。條邊組成。 對于非連通圖對于非連通圖,每個連通分量中的頂點集和遍歷時走過的邊每個連通分量中的頂點集和遍歷時走過的邊一起構(gòu)成一棵生成樹一起構(gòu)成一棵生成樹,各個連通分量的生成樹組成非連通圖的生各個連通分量的生成樹組成非連通圖的生成森林。成森林。問題：如何建立無向問題：如何建立無向圖的深度優(yōu)先生成森圖的深度優(yōu)先生成森林或廣度優(yōu)先生成森林或廣度優(yōu)先生成森林？林？ 0 1 2 3 4 11 12 5 10 1 0 0 3 4 A B C D E F G H I

40、 J K L M 2 8 0 7 10 6 6 12 11 7 6 12 9 0 11 9 1 5 6 7 8 9 10 11 12 A F C L M J B D E G K I H 深度優(yōu)先生成森林深度優(yōu)先生成森林 A F C L M J B D E G K I H 廣度優(yōu)先生成森林廣度優(yōu)先生成森林3 最小生成樹最小生成樹一個無向圖可以對應(yīng)多個生成樹。一個無向圖可以對應(yīng)多個生成樹。一個帶權(quán)無向圖一個帶權(quán)無向圖(無向網(wǎng)無向網(wǎng))同樣可以對應(yīng)多個生成樹。同樣可以對應(yīng)多個生成樹。一棵一棵生成樹的代價生成樹的代價定義為樹上各邊的權(quán)之總和。定義為樹上各邊的權(quán)之總和。代價最小的生成樹稱為代價最小的生成樹

41、稱為最小代價生成樹最小代價生成樹（Minimum Cost Spanning Tree），簡），簡稱為稱為最小生成樹最小生成樹(MST)。v1v2v3v5v4v61556536642v1v2v3v5v4v615342生成樹生成樹v1v2v3v5v4v653642Prim 算法算法思想：思想：重復(fù)執(zhí)行重復(fù)執(zhí)行:N = ( V , E ) 是具有是具有 n 個頂點的連通網(wǎng)，設(shè)個頂點的連通網(wǎng)，設(shè) U 是最小生成樹中頂是最小生成樹中頂點的集合，設(shè)點的集合，設(shè) TE 是最小生成樹中邊的集合；是最小生成樹中邊的集合； 初始，初始，U = u1 ，TE = ，在所有在所有 uU，vV- -U 的邊的邊 (

42、u , v ) 中尋找代價中尋找代價最小最小的邊的邊( u , v ) ，并納入集合并納入集合 TE 中；中；同時將同時將 v 納入集合納入集合 U 中；中；直至直至 U = V 為止。為止。集合集合 TE 中必有中必有 n- -1 條邊。條邊。 UV-U1957年由年由Prim提出提出從一個平凡圖開始，普利姆算法逐步增加從一個平凡圖開始，普利姆算法逐步增加U中的頂點，中的頂點， 可稱為可稱為“加點法加點法”。v1v2v3v5v4v61556536642例，例，v1v31v25v53v64v42初始初始: U = v1 ，V- -U = v2 , v3 , v4 , v5 , v6 TE =

43、U = v1 , v3 ，V- -U = v2 , v4 , v5 , v6 U = v1 , v3 , v6 ，V- -U = v2 , v4 , v5 重點重點: 邊一定存在于邊一定存在于 U 與與 V- -U 之間。之間。U = v1 , v3 , v4 , v6 ，V- -U = v2 , v5 U = v1 , v2 , v3 , v4 , v6 ，V- -U = v5 U = v1 , v2 , v3 , v4 , v5 , v6 ，V- -U = struct /記錄從記錄從U到到V-U具有最小代價的邊。具有最小代價的邊。 VertexType adjvex; /頂點名稱頂點名稱

44、 int lowcost; closedgeMAX_VERTEX_NUM; closedgei.lowcost = Min(cost(u, vi) | uU) lPrim算法的實現(xiàn)算法的實現(xiàn) 頂點集合如何表示？頂點集合如何表示？ 最小邊如何選擇？最小邊如何選擇？ 一個頂點加入一個頂點加入U集合如何表示？集合如何表示？closedgei.adjvex=kclosedgei.lowcost=0頂點頂點i與頂點與頂點k鄰接鄰接,頂點頂點k已經(jīng)在已經(jīng)在U集合中集合中頂點頂點i加入加入U集合時集合時V4V1V3V2V6V5165adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v

45、6323456UV-Uk 頂點頂點iclosedgeclosedge2.adjvex=1 .lowcost=6closedge3.adjvex=1 .lowcost=1closedge4.adjvex=1 .lowcost=5adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66V4V1V3V2V6V5656554V4V1V3V2V6V56565526adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4void MiniSpanTree_PRIM( MGraph G, VertexType u) k = LocateVex(G,

46、u); for(j=0; jG.vexnum; +j) if(j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; for(i=1; iG.vexnum; +i) k = minimun(closedge); printf(colsedgek.adjvex, G.vexsk); closedgek.lowcost = 0; for(j=0; jG.vexnum; +j) if(G.arcskj.adj closedgej.lowcost) colsedgej = G.vexsk, G.arcskj.adj ; Prim()算法中有

47、兩重算法中有兩重for循環(huán)循環(huán), ,所以時間復(fù)雜度為所以時間復(fù)雜度為O(n2)。 與網(wǎng)中的邊數(shù)無關(guān)，適用于求與網(wǎng)中的邊數(shù)無關(guān)，適用于求邊稠密的網(wǎng)邊稠密的網(wǎng)的最小生成樹。的最小生成樹。新頂點并入新頂點并入U，重新計，重新計算代價最小的邊算代價最小的邊struct int adjvex; double lowcost;closedgeMAX_VERTEX_NUM;Kruskal 算法算法思想：思想：重復(fù)執(zhí)行重復(fù)執(zhí)行:N = ( V , E ) 是是 n 頂點的連通網(wǎng)，設(shè)頂點的連通網(wǎng)，設(shè) E 是連通網(wǎng)中邊的集合；是連通網(wǎng)中邊的集合； 選取選取 E 中權(quán)值最小的邊中權(quán)值最小的邊 ( u , v ) ，

48、否，否，將邊將邊 ( u , v ) 納入納入 TE 中，并從中，并從 E 中刪除邊中刪除邊 ( u , v ) ；判斷邊判斷邊 ( u , v ) 與與 TE 中的邊是否構(gòu)成回路中的邊是否構(gòu)成回路 ？直至直至 E 為空為空 ；構(gòu)造最小生成樹構(gòu)造最小生成樹 N = ( V , TE )，TE 是最小生成樹中邊的集合，是最小生成樹中邊的集合，初始初始 TE = ；u 和和 v 一定一定不在同一個不在同一個連通分量中連通分量中考慮問題的出發(fā)點考慮問題的出發(fā)點: 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。中每一條邊的權(quán)值盡

49、可能地小。lKruskal于于1956年提出年提出v1v2v3v5v4v61556536642例，例，v1v2v3v5v4v615342初始初始 TE = 當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v1 , v3 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v4 , v6 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v2 , v5 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v3 , v6 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v1 , v4 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v3 , v4 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v2 , v3 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v1 , v2 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊

50、 ( v3 , v5 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v5 , v6 )從一個零圖開始，克魯斯卡爾算法逐步增加生成樹的邊，從一個零圖開始，克魯斯卡爾算法逐步增加生成樹的邊， 與普里姆算法相比，可稱為與普里姆算法相比，可稱為“加邊法加邊法”。 為了簡便為了簡便, ,在實現(xiàn)克魯斯卡爾算法在實現(xiàn)克魯斯卡爾算法Kruskal()時時, ,參數(shù)參數(shù)E存放圖存放圖G中的所有邊中的所有邊, ,假設(shè)它們是按權(quán)值從小到假設(shè)它們是按權(quán)值從小到大的順序排列的。大的順序排列的。n為圖為圖G的頂點個數(shù)的頂點個數(shù), ,e為圖為圖G的邊數(shù)。的邊數(shù)。 typedef struct int u; /*邊的起始頂點邊的起始頂

51、點*/ int v; /*邊的終止頂點邊的終止頂點*/ int w; /*邊的權(quán)值邊的權(quán)值*/ Edge; void Kruskal(Edge E, int n) int i,j,k; int vsetMAXV; for (i=0;in;i+) vseti=i; k=1; j=0; while (kn) /*生成的邊數(shù)小于生成的邊數(shù)小于n時循環(huán)時循環(huán)*/ if (vsetEj.u != vsetEj.v) printf(%d,%d):%dn,Ej.u,Ej.v,Ej.w); k+; sv=vsetEj.v;su=vsetEj.u; for (i=0;in;i+) /*兩個集合統(tǒng)一編號兩個集合統(tǒng)

52、一編號*/if (vseti=sv) vseti=su;j+; /*掃描下一條邊掃描下一條邊*/ 完整的克魯斯卡爾算法應(yīng)包括對邊按權(quán)值遞增完整的克魯斯卡爾算法應(yīng)包括對邊按權(quán)值遞增排序，上述算法假設(shè)邊已排序的情況下，時間復(fù)雜排序，上述算法假設(shè)邊已排序的情況下，時間復(fù)雜度為度為O(n2)。 如果給定的帶權(quán)連通無向圖如果給定的帶權(quán)連通無向圖G有有e條邊條邊, ,n個頂個頂點，采用堆排序點，采用堆排序( (在第在第1010章中介紹章中介紹) )對邊按權(quán)值遞增對邊按權(quán)值遞增排序，并且用排序，并且用6.56.5節(jié)的等價類判斷連通性，則克魯節(jié)的等價類判斷連通性，則克魯斯卡爾算法的時間復(fù)雜度降為斯卡爾算法的時

53、間復(fù)雜度降為O(eloge)。由于它與。由于它與n無關(guān)，只與無關(guān)，只與e有關(guān)，所以說克魯斯卡爾算法適合于有關(guān)，所以說克魯斯卡爾算法適合于求求邊稀疏的網(wǎng)邊稀疏的網(wǎng)的最小生成樹。的最小生成樹。作業(yè)：作業(yè)：7.5 7.7l AOV網(wǎng)、網(wǎng)、AOE網(wǎng)網(wǎng)l 拓?fù)渑判蛲負(fù)渑判騦 關(guān)鍵路徑關(guān)鍵路徑7.5 有向無環(huán)圖有向無環(huán)圖DAGq AOVAOV網(wǎng)網(wǎng)(Activity On Vertex net )(Activity On Vertex net )F用頂點表示用頂點表示活動活動，邊表示邊表示活動的順序關(guān)系活動的順序關(guān)系的有向圖稱為的有向圖稱為AOVAOV網(wǎng)網(wǎng). .例：某工程可分為例：某工程可分為7 7個子工程

54、個子工程，若用，若用頂點表示子工程（也稱頂點表示子工程（也稱活動），活動）， 用弧表示子工程間用弧表示子工程間的順序關(guān)系，的順序關(guān)系，工程的施工流程工程的施工流程可用如右的可用如右的AOVAOV網(wǎng)表示。網(wǎng)表示。 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V6工程能否順序進(jìn)行，即工程流程是否工程能否順序進(jìn)行，即工程流程是否“合理合理”？7.5 有向無環(huán)圖及其應(yīng)用有向無環(huán)圖及其應(yīng)用 1. 拓?fù)渑判颍ㄍ負(fù)渑判颍═opological Sort） 設(shè)設(shè)G=(V,E)是一個具有是一個具有n個頂點的有向圖個頂點的有向圖,V中頂點序列中頂點序列v1,v2,vn稱為一個稱為一個拓?fù)渫負(fù)?

55、有序有序)序列序列,當(dāng)且僅當(dāng)該頂點序列滿足下當(dāng)且僅當(dāng)該頂點序列滿足下列條件：若列條件：若是圖中的弧是圖中的弧(即從頂點即從頂點vi到到vj有一條路徑有一條路徑),則在則在序列中頂點序列中頂點vi必須排在頂點必須排在頂點vj之前。之前。 在一個有向圖中找一個拓?fù)湫蛄械倪^程稱為在一個有向圖中找一個拓?fù)湫蛄械倪^程稱為拓?fù)渑判蛲負(fù)渑判颉?C2C1C8C9C3C4C5C6C7拓?fù)湫蛄校和負(fù)湫蛄校?C1, C2, C3, C4, C5, C8, C9, C7, C6 。拓?fù)湫蛄校和負(fù)湫蛄校?C1, C2, C3, C8, C4, C5, C9, C7, C6 。C2C1C8C9C3C4C5C6C7 用頂點

56、表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖，用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖，稱為頂點表示活動的網(wǎng)稱為頂點表示活動的網(wǎng)(Activity On Vertex Network)，簡稱為，簡稱為AOV-網(wǎng)網(wǎng)。 如何進(jìn)行拓?fù)渑判?？如何進(jìn)行拓?fù)渑判?？方法一方法一：（從圖中頂點的入度考慮）：（從圖中頂點的入度考慮）從有向圖中選擇一個沒有前驅(qū)從有向圖中選擇一個沒有前驅(qū)( (即入度為即入度為0)0)的頂點并且輸出的頂點并且輸出它。它。從網(wǎng)中刪去該頂點和所有以它為尾的?。粡木W(wǎng)中刪去該頂點和所有以它為尾的??； 重復(fù)上述兩步重復(fù)上述兩步, ,直到圖全部頂點輸出；或當(dāng)前圖中不再存在直到圖全部頂點輸出

57、；或當(dāng)前圖中不再存在沒有前驅(qū)的頂點。沒有前驅(qū)的頂點。例，例，v1v2v4v3v6v5拓?fù)渑判蛲負(fù)渑判騰1v6v4v3v2v5v1v2v4v3v6v5例，例，拓?fù)渑判蛲負(fù)渑判騰1v3v2存在環(huán)存在環(huán)方法二方法二：（從圖中頂點的出度考慮，得到逆拓?fù)湫蛄校海◤膱D中頂點的出度考慮，得到逆拓?fù)湫蛄校挠邢驁D中選擇一個出度為從有向圖中選擇一個出度為0 0的頂點并且輸出它。的頂點并且輸出它。從網(wǎng)中刪去該頂點和所有以它為頭的弧；從網(wǎng)中刪去該頂點和所有以它為頭的弧； 重復(fù)上述兩步重復(fù)上述兩步, ,直到圖全部頂點輸出；或當(dāng)前圖中不再存在直到圖全部頂點輸出；或當(dāng)前圖中不再存在出度為出度為0 0的頂點。的頂點。方法

58、三方法三：當(dāng)有向圖中無環(huán)時，利用深度優(yōu)先遍歷進(jìn)行拓?fù)渑判颍寒?dāng)有向圖中無環(huán)時，利用深度優(yōu)先遍歷進(jìn)行拓?fù)渑判?從某點出發(fā)進(jìn)行從某點出發(fā)進(jìn)行DFSDFS遍歷時，最先退出遍歷時，最先退出DFSDFS函數(shù)的頂點即出函數(shù)的頂點即出度為度為0 0的頂點，是拓?fù)湫蛄兄凶詈笠粋€頂點。按退出的頂點，是拓?fù)湫蛄兄凶詈笠粋€頂點。按退出DFSDFS函數(shù)的函數(shù)的先后記錄下來的頂點序列即為逆拓?fù)湫蛄小Ｏ群笥涗浵聛淼捻旤c序列即為逆拓?fù)湫蛄?。Status TopologicalSort( ALGraph G) int StMAXV, top=-1; /*棧棧StSt的指針為的指針為toptop*/ FindInDegree(G

59、, indegree); /indegree頂點入度頂點入度 for (i=0; i-1) /*棧不為空時循環(huán)棧不為空時循環(huán)*/ i=Sttop; top-; printf(%d ,G.verticesi.data); +count; for( p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; if ( !(-indegreek) top+; Sttop=k; if(countG.vexnum) return ERROR; else return OK; void FindInDegree( ALGraph G, int *indegr

60、ee) int i; ArcNode *p; for(i=0; iG.vexnum; i+) indegreei = 0; for(i=0; inextarc) Indegreep-adjvex+; l 分析此拓?fù)渑判蛩惴芍?，如果分析此拓?fù)渑判蛩惴芍?，如果AOV網(wǎng)絡(luò)有網(wǎng)絡(luò)有n個頂點，個頂點，e條邊，條邊，求個頂點的入度的時間復(fù)雜度為求個頂點的入度的時間復(fù)雜度為O(e)，建立零入度頂點棧所需，建立零入度頂點棧所需要的時間是要的時間是O(n)。在拓?fù)渑判虻倪^程中在，有向圖有。在拓?fù)渑判虻倪^程中在，有向圖有n個頂點，個頂點，每個頂點進(jìn)一次棧，出一次棧，共輸出每個頂點進(jìn)一次棧，出一次棧，共輸出n次