《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第9章 圖C語(yǔ)言描述（第2版）張乃孝編著

《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第9章 圖C語(yǔ)言描述（第2版）張乃孝編著》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第9章 圖C語(yǔ)言描述（第2版）張乃孝編著（106頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、9圖9.1 基本概念9.5 最短路徑9.2 圖的周游 9.6 拓?fù)渑判?.3 存儲(chǔ)表示 9.7 關(guān)鍵路徑9.4 最小生成樹重點(diǎn)內(nèi)容概述:圖的深度優(yōu)先搜索與廣度優(yōu)先搜索最小生成樹的Prim算法最小生成樹的Kruskal算法單源最短路徑Dijkstra算法所有頂點(diǎn)對(duì)之間最短路徑的Floyd算法圖的應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑9.1 9.1 圖的基本概念圖的基本概念: :圖圖是由頂點(diǎn)的有窮非空集合V和邊（頂點(diǎn)的偶對(duì)）的集合E組成，記為G = ( V ，E ) 。 v0v1v2G1v0v3v2v1G2v0v1v2v6v5v4v3G3V(G1) = v0,v1,v2E(G1) = ,V(G2) = v0,v

2、1,v2,v3E(G2) = (v0,v1),(v0,v2),(v0,v3),(v1,v2),(v1,v3),(v2,v3)V(G3) = v0,v1,v2,v3,v4,v5,v6E(G3) = (v0,v1),(v0,v2),(v1,v3),(v1,v4),(v2,v5),(v2,v6)有向圖和無(wú)向圖有向圖有向圖定義:若圖中的每條邊都是有方向的表示:有向圖中的邊是由兩個(gè)頂點(diǎn)組成的有序?qū)?，有序?qū)τ眉饫ㄌ?hào)表示如表示一條有向邊，vi是邊的始點(diǎn)，vj是邊的終點(diǎn)。和代表兩條不同的有向邊。無(wú)向圖無(wú)向圖定義:若圖中每條邊都是無(wú)方向的表示:無(wú)向圖中的邊是由兩個(gè)頂點(diǎn)組成的無(wú)序?qū)?，無(wú)序?qū)τ脠A括號(hào)表示無(wú)向圖中(v

3、i ,vj)和(vj ,vi)代表同一條邊。 在本章中，對(duì)所討論的圖加了以下兩個(gè)約束其一是不考慮頂點(diǎn)到其自身的邊，即若(vi ,vj)或是E(G)中的邊，則vi vj；其二是圖中不允許一條邊重復(fù)出現(xiàn)，即如果(vi ,vj)或是E(G)中的邊，則是唯一的。 圖G的頂點(diǎn)數(shù)n和邊數(shù)e滿足以下關(guān)系l若G是有向圖，則0en(n-1) 有向完全圖：有n(n-1)條邊的有向圖l若G是無(wú)向圖，則0en(n-1)/2。 無(wú)向完全圖：有n(n-1)/2條邊的無(wú)向圖完全圖具有最多的邊數(shù)。如圖G2就是一個(gè)具有4個(gè)頂點(diǎn)的無(wú)向完全圖，邊數(shù)為:4*(4-1)/2=12。相關(guān)概念完全圖有向完全圖l關(guān)聯(lián)與鄰接l若是一條有向邊，

4、則稱頂點(diǎn)vi鄰接到vj，或頂點(diǎn)vj鄰接于vi，邊與頂點(diǎn)vi，vj相關(guān)聯(lián)。l若(vi,vj)是一條無(wú)向邊，則vi和vj是相鄰頂點(diǎn)，(vi,vj)是與頂點(diǎn)vi和vj相關(guān)聯(lián)的邊。l度：與頂點(diǎn)v相關(guān)聯(lián)的邊數(shù)稱為頂點(diǎn)的度，記為D(v)。 如G2中頂點(diǎn)v0的度為3，l入度：若G是一個(gè)有向圖，則以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的入度，記為ID(v)；l出度：以v為始點(diǎn)的邊的數(shù)目稱為v的出度，記為OD(v)。有向圖中頂點(diǎn)v的度為其入度和出度之和，即D(v)=ID(v)+OD(v)。如圖G1中頂點(diǎn)v1的入度為1，出度為2，度為3度、入度和出度度、入度和出度無(wú)論是有向圖還是無(wú)向圖，頂點(diǎn)數(shù)無(wú)論是有向圖還是無(wú)向圖，頂點(diǎn)

5、數(shù)n n，邊數(shù)，邊數(shù)e e和度和度數(shù)之間滿足以下關(guān)系數(shù)之間滿足以下關(guān)系=n1ii)/2D(ve 設(shè)有圖G=(V，E)和G=(V，E)，如果V是V的子集，E是E的子集，則稱G是G的子圖。子圖子圖G1 如下圖給出了有向圖G1的若干子圖。143212431121243l路徑:圖G=(V，E)中，若存在頂點(diǎn)序列vi0, vi1, , vin，使得(vi0, vi1)，( vi1, vi2)， (vin-1, vin)都在E中(若是有向圖，則使得，都在E中)，則稱從頂點(diǎn)vi0到vin存在一條路徑l 路徑長(zhǎng)度:路徑上的邊數(shù)。l 簡(jiǎn)單路徑:若路徑上的頂點(diǎn)除vi0和vin可以相同外,其它頂點(diǎn)都不相同.l 回路

6、或環(huán):起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑l如圖G1中頂點(diǎn)序列v0,v1,v0是一長(zhǎng)度為2 的有向環(huán)；lG2中頂點(diǎn)序列v0,v1,v2,v3是一條從頂點(diǎn)v0到v3的長(zhǎng)度為3的路徑，頂點(diǎn)序列v0,v1,v3,v0,v2是一條從頂點(diǎn)v0到v2的長(zhǎng)度為4的路徑，但不是簡(jiǎn)單路徑，頂點(diǎn)序列v0,v1,v3,v0是一長(zhǎng)度為3的環(huán)。 v0 v0 v1 v1 v2 v2 v3 G1G2l有向圖中，若存在一頂點(diǎn)v，從該頂點(diǎn)有路徑可以到圖中其它所有頂點(diǎn)，則稱此有向圖為有根圖，v稱為圖的根。l有根圖中的根可能是不唯一的 l連通：圖G=(V，E)中，若從vi到vj有一條路徑(從vj到vi也一定有一條路徑)，則稱vi和vj是連通的

7、l連通圖：若V(G)中任意兩個(gè)不同的頂點(diǎn)vi和vj都是連通的(即有路徑)，則稱G為連通圖l連通分量：無(wú)向圖G中的最大連通子圖稱為G的連通分量l強(qiáng)連通圖：有向圖G=(V，E)中，若V(G)中任意兩個(gè)不同的頂點(diǎn)vi和vj都存在從vi到vj以及從vj和vi的路徑，則稱圖G是強(qiáng)連通圖l強(qiáng)連通分量：有向圖的最大強(qiáng)連通子圖稱為圖的強(qiáng)連通分量l如圖G2和G3都是連通圖l如圖G4是非連通圖，它的兩個(gè)連通分量H1和H2 H1 v0 H2 v0 v1 v2 v1 v2 v3 v3 G2G3G4 v0 v0 v1 v2 v1 v2 v3 v4 v5 v6 v3 如左圖G1是非強(qiáng)連通圖它的兩個(gè)強(qiáng)連通分量如右圖所示 v

8、0 v1 v2 v0 v2 v1 G1l若圖的每條邊都賦上一個(gè)權(quán)，則稱為帶權(quán)圖l帶權(quán)的連通圖稱為網(wǎng)絡(luò)。通常權(quán)是具有某種意義的數(shù)，下圖為一個(gè)網(wǎng)絡(luò)。 v0 3 v1 8 11 5 4 v4 6 10 v2 2 v3 9.1.2 抽象數(shù)據(jù)類型ADT Graph isoperation創(chuàng)建一個(gè)空?qǐng)D Graph createGraph ( )判斷圖g是否空?qǐng)D，是則返回1，否則返回0int isNullGraph ( g )找圖中的第一個(gè)頂點(diǎn)，如果圖是空?qǐng)D則返回NULLVertex firstVertex ( g )找圖中頂點(diǎn)vi的下一個(gè)頂點(diǎn)Vertex nextVertex ( g , vi )查找圖中

9、值為value的頂點(diǎn)Vertex searchVertex ( g , value )在圖g中增加一個(gè)值為value的頂點(diǎn)Graph addVertex ( g , value )在圖g中刪除一個(gè)頂點(diǎn)和與該頂點(diǎn)相關(guān)聯(lián)的所有邊Graph deleteVertex ( g , vertex )在圖g中刪除一條邊e（ 或者(vi,vj) ）Graph deleteEdge ( g , vi , vj )在圖g中增加一條邊或者(vi,vj) Graph addEdge ( g , vi , vj )判斷圖g中是否存在一條指定邊或者(vi,vj) int findEdge ( g , vi , vj )

10、找圖g中與頂點(diǎn)v相鄰的第一個(gè)頂點(diǎn) Vertex firstAdjacent ( g , v ) /v與返回頂點(diǎn)構(gòu)成的邊也稱為與v相關(guān)聯(lián)的第一條邊。找圖g中與vi相鄰的，相對(duì)相鄰頂點(diǎn)vj的，下一個(gè)相鄰頂點(diǎn)Vertex nextAdjacent ( g , vi , vj ) /vi與返回值構(gòu)成的邊也稱為是vi與vj構(gòu)成的邊的下一條邊end ADT Graph9.2 圖的周游圖的周游是從圖中某個(gè)頂點(diǎn)出發(fā)，按照某種方式系統(tǒng)地訪問(wèn)圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問(wèn)一次。也稱圖的遍歷。連通圖或強(qiáng)連通圖：則從圖中任意一頂點(diǎn)出發(fā)都可以訪問(wèn)圖中所有頂點(diǎn)。由于圖中每個(gè)頂點(diǎn)都可能與圖中其它多個(gè)頂點(diǎn)鄰接并存在回路，

11、為了避免重復(fù)訪問(wèn)已訪問(wèn)過(guò)的頂點(diǎn)，在圖的周游中，通常對(duì)已訪問(wèn)的頂點(diǎn)作標(biāo)記。圖的遍歷通常有兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。它們對(duì)有向圖和無(wú)向圖都適用。深度優(yōu)先周游(Depth_First Traversal)的策略又稱為深度優(yōu)先搜索（Depth_first Search），具體思想是 從圖的指定頂點(diǎn)v出發(fā)，先訪問(wèn)頂點(diǎn)v，并將其標(biāo)記為已訪問(wèn)過(guò)，然后依次從v未被訪問(wèn)過(guò)的鄰接頂點(diǎn)w出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中與v相連通的所有頂點(diǎn)都被訪問(wèn)過(guò)。如果圖中還有未被訪問(wèn)的頂點(diǎn)，則從另一未被訪問(wèn)過(guò)的頂點(diǎn)出發(fā)重復(fù)上述過(guò)程，直到圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。 l對(duì)圖進(jìn)行深度優(yōu)先周游時(shí)，按訪問(wèn)頂點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先周

12、游時(shí)，按訪問(wèn)頂點(diǎn)的先后次序所得到的頂點(diǎn)序列，稱為該的先后次序所得到的頂點(diǎn)序列，稱為該圖的深度優(yōu)先周游序列，簡(jiǎn)稱圖的深度優(yōu)先周游序列，簡(jiǎn)稱DFSDFS。l從上述的搜索方法可知，周游過(guò)程是一從上述的搜索方法可知，周游過(guò)程是一個(gè)遞歸的過(guò)程。個(gè)遞歸的過(guò)程。V7V7V6V6V3V3V2V2V5V5V1V1V8V8V4V4例子：例子：v1v2 v4 v8v5v3v6v7void dft ( Graph g )Vertex v ;for ( v =firstVertex ( g ) ; v != NULL ; v = nextVertex ( g , v ) ) if ( v.mark = FALSE )

13、dfs ( g , v ) ;void dfs ( Graph g , Vertex v )Vertex v1;v.mark = TRUE ;for ( v1 = firstAdjacent ( g , v ); v1 != NULL ; v1=nextAdjacent ( g ,v, v1 ) ) if (v1.mark=FALSE) dfs ( g ,v1 );廣度優(yōu)先周游廣度優(yōu)先周游(Breadth_First Traversal)的策略又稱為廣度優(yōu)先搜索（Breadth_First Search），具體思想是 從圖的指定頂點(diǎn)v出發(fā)，先訪問(wèn)頂點(diǎn)v，并將其標(biāo)記為已訪問(wèn)過(guò)，接著依次訪問(wèn)v的所

14、有相鄰結(jié)點(diǎn)w1，w2，wx，然后，再依次訪問(wèn)與w1，w2，wx鄰接的所有未被訪問(wèn)過(guò)的頂點(diǎn)，以此類推，直到所有已訪問(wèn)頂點(diǎn)的相鄰結(jié)點(diǎn)都被訪問(wèn)過(guò)為止。如果圖中還有未被訪問(wèn)過(guò)的頂點(diǎn)，則從某個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索，直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。 廣度優(yōu)先周游得到的頂點(diǎn)序列稱為廣度優(yōu)先周游序列，簡(jiǎn)稱BFS序列V7V7V6V6V3V3V2V2V5V5V1V1V8V8V4V4例子：例子：V1v2 v3 v4v5v6v7v8void bft ( Graph g )Vertex v ;for ( v =firstVertex ( g ) ; v != NULL ; v = nextVertex (

15、g , v ) ) if ( v.mark = FALSE ) bfs ( g , v ) ;void bfs ( Graph g , Vertex v )Vertex v1 , v2;Queue q ;/* 隊(duì)列元素的類型為Vertex* */q = createEmptyQueue ( ) ;enQueue ( q ,v ) ;v.mark=TRUE;while ( !isEmptyQueue(q) ) v1 =frontQueue ( q ) ;deQueue ( q ); v1.mark = TRUE;v2 =firstAdjacent ( g ,v1 );while ( v2!=NU

16、LL ) if ( v2.mark = FALSE ) enQueue ( q, v2 ); v2 = nextAdjacent ( g , v1 , v2 ) ;l圖的結(jié)構(gòu)較復(fù)雜，任意兩個(gè)頂點(diǎn)間都可能存在聯(lián)系，因而圖的存儲(chǔ)方法也很多，應(yīng)根據(jù)具體的應(yīng)用和施加的操作選擇圖的存儲(chǔ)表示法 9.3圖的存儲(chǔ)鄰接矩陣表示法鄰接表表示法鄰接多重表表示法、圖的十字鏈表等9.3.1 鄰接矩陣是表示頂點(diǎn)間相鄰關(guān)系的矩陣設(shè)G=(V，E)為具有n個(gè)頂點(diǎn)的圖，其鄰接矩陣為具有以下性質(zhì)的n階方陣。=的邊不是圖或若的邊是圖或若GvvvvGvvvvwjiAjijijijiij,),(,),(,下圖帶權(quán)圖的兩種鄰接矩陣分別為A

17、3和A4=01011100248206511460385303A v0 3 v1 8 11 5 4 v4 6 10 v2 2 v3 l無(wú)向圖的鄰接矩陣一定是一對(duì)稱矩陣無(wú)向圖的鄰接矩陣一定是一對(duì)稱矩陣l無(wú)向圖的鄰接矩陣的第無(wú)向圖的鄰接矩陣的第i i行行( (或第或第i i列列) )非零元素非零元素( (或非或非 元素元素) )個(gè)數(shù)為第個(gè)數(shù)為第i i個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的度度D(vD(vi i) )。l有向圖的鄰接矩陣的第有向圖的鄰接矩陣的第i i行非零元素行非零元素( (或非或非 元元素素) )個(gè)數(shù)為第個(gè)數(shù)為第i i個(gè)頂點(diǎn)的出個(gè)頂點(diǎn)的出度度OD(vOD(vi i) )，第，第i i列非零列非零元素元素

18、( (或非或非 元素元素) )個(gè)數(shù)就是第個(gè)數(shù)就是第i i個(gè)頂點(diǎn)的入度個(gè)頂點(diǎn)的入度ID(vID(vi i) )。l鄰接矩陣表示圖，很容易確定圖中任意兩個(gè)頂鄰接矩陣表示圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。點(diǎn)之間是否有邊相連。l需要存儲(chǔ)一個(gè)包括n結(jié)點(diǎn)的順序表來(lái)保存結(jié)點(diǎn)的數(shù)據(jù)或指向結(jié)點(diǎn)的數(shù)據(jù)指針l 需存儲(chǔ)一個(gè)nn的相鄰矩陣來(lái)指示結(jié)點(diǎn)間的關(guān)系有向圖：需nn個(gè)單元來(lái)存儲(chǔ)相鄰矩陣無(wú)向圖：由于相鄰矩陣是對(duì)稱的只需存儲(chǔ)相鄰矩陣的下三角部分9.3.2 1、順序存儲(chǔ)的頂點(diǎn)表存放頂點(diǎn)本身的數(shù)據(jù)信息，表中每個(gè)表目對(duì)應(yīng)于圖的一個(gè)頂點(diǎn)，包括兩個(gè)字段：頂點(diǎn)字段(vertex)存放頂點(diǎn)vi的信息指針字段(edgel

19、ist)存放與vi相關(guān)聯(lián)的邊表中的第一個(gè)邊結(jié)點(diǎn)的地址由順序存儲(chǔ)的頂點(diǎn)表, n個(gè)鏈?zhǔn)酱鎯?chǔ)的邊表兩部分組成vertexedgelist 2、 n個(gè)鏈?zhǔn)酱鎯?chǔ)的邊表，邊表中每個(gè)邊結(jié)點(diǎn)包括三個(gè)字段 相鄰頂點(diǎn)字段(endvex)存放通過(guò)本邊與頂點(diǎn)vi相鄰接的頂點(diǎn)vj在頂點(diǎn)表中的位置j權(quán)字段(weight)存放邊結(jié)點(diǎn)所代表的邊的權(quán)值(可選項(xiàng))鏈字段(nextedge)指向邊表的下一個(gè)邊結(jié)點(diǎn)endvexnextedgeweight每條邊每條邊(v(vi i,v,vj j) )在兩個(gè)頂點(diǎn)在兩個(gè)頂點(diǎn)v vi i，v vj j的邊表中都占一個(gè)的邊表中都占一個(gè)結(jié)點(diǎn)，因此，每條邊在邊表中存儲(chǔ)兩次。頂點(diǎn)結(jié)點(diǎn)，因此，每條邊

20、在邊表中存儲(chǔ)兩次。頂點(diǎn)v vi i的的邊表中結(jié)點(diǎn)個(gè)數(shù)為頂點(diǎn)邊表中結(jié)點(diǎn)個(gè)數(shù)為頂點(diǎn)v vi i的度的度v0v1v2v310002211330123 v0 v3 v1 v2 3 l頂點(diǎn)頂點(diǎn)v vi i的邊表中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的是以的邊表中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的是以v vi i為為始點(diǎn)的一條邊，因此，將有向圖鄰接表始點(diǎn)的一條邊，因此，將有向圖鄰接表的邊表稱為出邊表。頂點(diǎn)的邊表稱為出邊表。頂點(diǎn)v vi i的邊表中結(jié)的邊表中結(jié)點(diǎn)個(gè)數(shù)為頂點(diǎn)點(diǎn)個(gè)數(shù)為頂點(diǎn)v vi i的出度。的出度。l也可表示為入邊表。也可表示為入邊表。v0v1v2v310104v0v1v2v41023241v3v433(a)(b) v0 v3 v0 v1

21、 v2 v1 v2 v4 v3 鄰接表表示法的存儲(chǔ)結(jié)構(gòu)定義如下鄰接表表示法的存儲(chǔ)結(jié)構(gòu)定義如下 struct EdgeNodestruct EdgeNode; ;typedef struct EdgeNode typedef struct EdgeNode * * PEdgeNode PEdgeNode; ;typedef struct EdgeNode typedef struct EdgeNode * * EdgeList EdgeList; ;struct EdgeNodestruct EdgeNode int endvexint endvex; ;/ /* * 相鄰頂點(diǎn)字段相鄰頂點(diǎn)字段

22、* */ /AdjTypeAdjType weight; weight;/ /* * 邊的權(quán)邊的權(quán) * */ /PEdgeNode nextedgePEdgeNode nextedge; ; / /* * 鏈字段鏈字段 * */ /; ;/ /* * 邊表邊表 * */ /typedef structtypedef struct VexTypeVexType vertex; vertex;/ /* * 頂點(diǎn)信息頂點(diǎn)信息 * */ /EdgeList edgelistEdgeList edgelist; ;/ /* * 邊表頭指針邊表頭指針 * */ / VexNode VexNode; ;/

23、/* * 頂點(diǎn)表頂點(diǎn)表 * */ /typedef structtypedef struct VexNodeVexNode * *vexsvexs; ;intint n; n;/ /* * 圖的頂點(diǎn)個(gè)數(shù)圖的頂點(diǎn)個(gè)數(shù) * */ /GraphListGraphList; ;若圖G是無(wú)向圖，則圖的鄰接表表示的空間代價(jià)為O(n+2e)；若圖G是有向圖，則圖的鄰接表表示的空間代價(jià)為O(n+e)9.3.3 兩種表示的比較空間開銷操作的實(shí)現(xiàn)l鄰接矩陣表示很容易判斷兩個(gè)頂點(diǎn)之間是否有邊相連。l求無(wú)向圖中頂點(diǎn)的度，兩種表示都容易；求有向圖中頂點(diǎn)的度，鄰接矩陣容易，求出度，鄰接表表示容易。鄰接矩陣表示的空間代價(jià)只

24、與圖的頂點(diǎn)數(shù)有關(guān)。若圖中邊的數(shù)目小于頂點(diǎn)的數(shù)目，則用鄰接表表示圖比較節(jié)省空間，如果e達(dá)到n2數(shù)量級(jí)時(shí)，由于鄰接表中增加了輔助的鏈域，采用鄰接矩陣表示圖更節(jié)省空間，特別對(duì)于無(wú)權(quán)圖而言，鄰接矩陣的每個(gè)元素只要一個(gè)位就可以表示。9.4 9.4 基本概念： 生成樹DFS生成樹BFS生成樹 最小生成樹Prim 算法 Kruskal算法 對(duì)于連通的無(wú)向圖或強(qiáng)連通的有向圖，從任一頂點(diǎn)出發(fā)周游，或是對(duì)于有根的有向圖，從圖的根頂點(diǎn)出發(fā)周游，可以訪問(wèn)到所有的頂點(diǎn)。周游時(shí)經(jīng)過(guò)的邊加上所有頂點(diǎn)構(gòu)成了圖的一個(gè)連通子圖，稱為圖的一棵生成樹 構(gòu)造生成樹的過(guò)程可以按深度優(yōu)先周游，也可以按廣度優(yōu)先周游，周游中記錄訪問(wèn)的所有頂點(diǎn)

25、以及經(jīng)過(guò)的邊，得到的是深度優(yōu)先生成樹或廣度優(yōu)先生成樹，簡(jiǎn)稱為DFSDFS生成樹或BFSBFS生成樹。 無(wú)向圖 v0 v1 v2 v3 v4 v5 v6 v7 v0 v0 v1 v2 v1 v2 v3 v4 v5 v6 v3 v4 v5 v6 v7 v7 DFS生成樹BFS生成樹 v0 v0 v0 v1 v3 v4 v5 v1 v3 v4 v5 v1 v3 v4 v5 v2 v6 v2 v6 v2 v6 有向圖DFS生成樹BFS生成樹 對(duì)于非連通的無(wú)向圖和非強(qiáng)連通的有向圖,從任一頂點(diǎn)出發(fā)無(wú)法訪問(wèn)到所有的頂點(diǎn)，只能得到各連通分量的生成樹所組成的生成樹林 圖的生成樹不唯一，從不同頂點(diǎn)出發(fā)，或從同一頂

26、點(diǎn)出發(fā)，但周游的路徑不一樣，則得到的生成樹都不同 對(duì)于網(wǎng)絡(luò)，其生成樹中的邊也帶權(quán)，將生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)值最小的生成樹稱為最小生成樹(Minimum Spanning Tree)應(yīng)用：城市中利用最小生成樹建立通訊網(wǎng)絡(luò)花費(fèi)最小的方案MST性質(zhì)設(shè)設(shè)G=(VG=(V，E)E)是一個(gè)網(wǎng)絡(luò)，是一個(gè)網(wǎng)絡(luò)，UU是頂點(diǎn)集合是頂點(diǎn)集合V V的一個(gè)真子集。如果邊的一個(gè)真子集。如果邊(u,v)(u,v)的頂點(diǎn)的頂點(diǎn)u uUU，v vV-UV-U，且邊，且邊(u,v)(u,v)是圖是圖GG中所中所有一個(gè)端點(diǎn)在有一個(gè)端點(diǎn)在UU里，另一端點(diǎn)在里，另一端點(diǎn)在V-UV-U里的里的邊中權(quán)值最小的邊，則一定

27、存在邊中權(quán)值最小的邊，則一定存在GG的一棵的一棵最小生成樹包括此邊最小生成樹包括此邊(u,v)(u,v)注注 ：MSTMST性質(zhì)可以用反證法證明性質(zhì)可以用反證法證明9.4.2 9.4.2 最小生成樹的構(gòu)造最小生成樹的構(gòu)造 利用利用MSTMST性質(zhì)，一條一條地選擇將要性質(zhì)，一條一條地選擇將要加入的邊。加入的邊。算法：算法：l primprim算法算法l kruskalkruskal算法算法 prim算法的基本思想是首先從集合V中任取一頂點(diǎn)(例如取頂點(diǎn)v0)放入集合U中，這時(shí)U=v0，TE=NULL，然后在所有一個(gè)頂點(diǎn)在集合U里，另一個(gè)頂點(diǎn)在集合V-U里的邊中，找出權(quán)值最小的邊(u,v)(uU，v

28、V-U)，將邊加入TE，并將頂點(diǎn)v加入集合U。重復(fù)上述操作直到U=V為止。這時(shí)TE中有n-1條邊，T=(U，TE)就是G的一棵最小生成樹例1654326513566425131163141643142116432142516543214253Kruskal算法的基本思想是 設(shè)G=(V，E)是網(wǎng)絡(luò)，最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V，)，T中每個(gè)頂點(diǎn)自成為一個(gè)連通分量。將集合E中的邊按遞增順序排列，從小到大依次選擇頂點(diǎn)分別在兩個(gè)連通分量中的邊加入圖T，則原來(lái)的兩個(gè)連通分量由于該邊的連接而成為一個(gè)連通分量。依次類推，直到T中所有頂點(diǎn)都在同一個(gè)連通分量上為止，該連通分量就是G

29、的一棵最小生成樹KruskalKruskal算法算法例165432651356642516543212345T=(V,)While(T中所含邊數(shù)n-1) 從E中選取當(dāng)前最短邊(u,v)； 從E中刪去邊(u,v)； if( (u,v)加入T中后不產(chǎn)生回路) 將邊(u,v)加入T中；算法描述：9.5 9.5 最短路徑最短路徑基本概念：路徑：如果圖中從一個(gè)頂點(diǎn)可以到達(dá)另一個(gè)頂點(diǎn)，則這兩個(gè)頂點(diǎn)間存在一條路徑。(從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)間可能存在多條路徑，而每條路徑上經(jīng)過(guò)的邊數(shù)并不一定相同)路徑長(zhǎng)度：如果圖是一個(gè)帶權(quán)圖，則路徑長(zhǎng)度為路徑上各邊的權(quán)值的總和。最短路徑長(zhǎng)度：兩個(gè)頂點(diǎn)間路徑長(zhǎng)度最短的那條路徑稱為

30、兩個(gè)頂點(diǎn)間的最短路徑，其路徑長(zhǎng)度稱為最短路徑長(zhǎng)度。9.5.1 9.5.1 Dijkstra算法 設(shè)圖G中有n個(gè)頂點(diǎn)，設(shè)置一個(gè)集合U，存放已求出最短路徑的頂點(diǎn)，V-U是尚未確定最短路徑的頂點(diǎn)集合。 每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值，集合U中頂點(diǎn)的距離值是從頂點(diǎn)v0到該頂點(diǎn)的最短路徑長(zhǎng)度，集合V-U中頂點(diǎn)的距離值是從頂點(diǎn)v0到該頂點(diǎn)的只包括集合U中頂點(diǎn)為中間頂點(diǎn)的最短路徑長(zhǎng)度。l初始時(shí)，集合U中只有頂點(diǎn)v0，頂點(diǎn)v0對(duì)應(yīng)的距離值為0，集合V-U中頂點(diǎn)vi的距離值為邊(v0, vi)的權(quán)值(i=1,2,n-1)，如果v0和vi間無(wú)邊直接相連，則vi的距離值為l在集合V-U中選擇距離值最小的頂點(diǎn)vmin加入集合

31、Ul對(duì)集合V-U中各頂點(diǎn)的距離值進(jìn)行修正，如果加入頂點(diǎn)vmin為中間頂點(diǎn)后，使v0到vi的距離值比原來(lái)的距離值更小，則修改vi的距離值l反復(fù)操作，直到從v0出發(fā)可以到達(dá)的所有頂點(diǎn)都在集合U中為止1383032V2:813-133032V1:13-13302220V3:13-192220V4:19終點(diǎn) 從V0到各終點(diǎn)的最短路徑及其長(zhǎng)度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329DijkstraDijkstra算法時(shí)間復(fù)雜度：算法中的初始化部分的時(shí)間復(fù)雜度為O(n)，求最短路徑部分由一個(gè)大循環(huán)組成，其中外循環(huán)運(yùn)行n-1次，內(nèi)循環(huán)為兩個(gè)，均運(yùn)行n-1次算

32、法的時(shí)間復(fù)雜度為O(n2)Floyd算法基本思想：設(shè)圖G=(V，E)，有n個(gè)頂點(diǎn)，圖采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)。如果邊(vi，vj)E，則從頂點(diǎn)vi到頂點(diǎn)vj存在一條長(zhǎng)度為arcsij的路徑，該路徑并不一定是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑，因?yàn)榭赡艽嬖趶膙i到vj并且包含其它頂點(diǎn)為中間頂點(diǎn)的路徑。因此，應(yīng)該在所有從vi到vj允許其它頂點(diǎn)為中間頂點(diǎn)的路徑中，找出長(zhǎng)度最短的路徑9.5.2 9.5.2 Floyd算法例ACB2643110 4 116 0 23 0初始：路徑：AB ACBA BCCA0 4 66 0 23 7 0加入V2：路徑：AB ABCBA BCCA CAB0 4 116 0 23

33、 7 0加入V1：路徑：AB ACBA BCCA CAB0 4 65 0 23 7 0加入V3：路徑：AB ABCBCA BCCA CAB時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：Floyd算法中初始化部分由一個(gè)循環(huán)組成，其中外循環(huán)運(yùn)行n次，內(nèi)循環(huán)也運(yùn)行n次，初始化部分的時(shí)間復(fù)雜度為O(n2)。迭代生成矩陣A和路徑nextvex的部分為三個(gè)循環(huán)的嵌套，其時(shí)間復(fù)雜度為O(n3)Floyd算法的時(shí)間復(fù)雜度為O(n3)9.6 拓?fù)渑判?9.6.1 AOV網(wǎng) 9.6.2 拓?fù)渑判?.6.1 AOV9.6.1 AOV網(wǎng)網(wǎng)基本概念：基本概念：AOV網(wǎng)：如果用圖中的頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)間的先后關(guān)系，則這樣的有向圖稱為頂點(diǎn)

34、活動(dòng)網(wǎng)(Activity On Vertex network，簡(jiǎn)稱AOV網(wǎng))AOV網(wǎng)中的弧表示活動(dòng)之間存在的制約關(guān)系例子：計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)，這時(shí)工程就是完成給定的學(xué)習(xí)計(jì)劃，而活動(dòng)就是學(xué)習(xí)課程，這些課程的名稱與代號(hào)如表所示在AOV網(wǎng)中，用頂點(diǎn)表示課程，有向邊表示課程之間的優(yōu)先關(guān)系，如果課程Ci是課程Cj的先修課，則在AOV網(wǎng)中必定存在一條有向邊。表中各課程的AOV網(wǎng)如下圖所示 C0 C7 C8 C6 C2 C3 C5 C1 C4 9.6.2 9.6.2 拓?fù)渑判蛲負(fù)渑判?對(duì)于一個(gè)AOV網(wǎng)，其所有頂點(diǎn)可以排成一個(gè)線性序列vi1，vi2，vin，該線性序列具

35、有以下性質(zhì)如果在AOV網(wǎng)中，從頂點(diǎn)vi到頂點(diǎn)vj存在一條路徑，則在線性序列中，頂點(diǎn)vi一定排在頂點(diǎn)vj之前。具有這種性質(zhì)的線性序列稱為拓?fù)湫蛄?，?gòu)造拓?fù)湫蛄械牟僮鞣Q為拓?fù)渑判蚶簩?duì)下圖中的AOV網(wǎng)進(jìn)行拓?fù)渑判虻玫降囊粋€(gè)拓?fù)湫蛄校旱玫降囊粋€(gè)拓?fù)湫蛄校篊0,C1,C2,C4,C3,C5,C7,C8,C6，另外一個(gè)拓?fù)湫蛄辛硗庖粋€(gè)拓?fù)湫蛄?C0,C7,C8,C1,C4,C2,C3,C6,C5如果一個(gè)學(xué)生一學(xué)期只能選修一門課，則他必須按照某一個(gè)拓?fù)湫蛄械拇涡驅(qū)W習(xí)，才能保證學(xué)習(xí)任何一門課時(shí)，其先修課程已學(xué)過(guò)。 C0 C7 C8 C6 C2 C3 C5 C1 C4 注意：1、一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁灰欢ㄊ?/p>

36、唯一的。2、假設(shè)AOV網(wǎng)代表一個(gè)工程，如果條件限制只能串行工作，則AOV網(wǎng)某一拓?fù)湫蛄芯褪钦麄€(gè)工程得以順利完成的一種可行方案。 AOV網(wǎng)中一定不能出現(xiàn)回路(因?yàn)槌霈F(xiàn)回路意味著，某些活動(dòng)的開工是以自己工作的完成作為先決條件，這種現(xiàn)象稱為死鎖)如圖所示的AOV網(wǎng)，就無(wú)法把頂點(diǎn)排成滿足拓?fù)湫蛄袟l件的線性序列。 v0 v1 v2 任何無(wú)回路的AOV網(wǎng)，其頂點(diǎn)都可以排成一個(gè)拓?fù)湫蛄?，方法如下?) 從AOV網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)將其輸出。2) 在AOV網(wǎng)中刪除此頂點(diǎn)及其所有的出邊。3) 反復(fù)執(zhí)行以上兩步，直到所有頂點(diǎn)都已經(jīng)輸出為止，此時(shí)整個(gè)拓?fù)渑判蛲瓿桑换蛘咧钡绞Ｏ碌捻旤c(diǎn)的入度都不為0為止，此時(shí)說(shuō)明

37、AOV網(wǎng)中存在回路，拓?fù)渑判驘o(wú)法再進(jìn)行。 C1C5C3C6C2C4C1C5C3C6C2C4C1,C5C3C6C2C4C1,C5C3C6C2C4C1,C5C3C6C2C4C1,C5C3C6C2C4C1,C4,C5C3C6C2C1,C4,C5C3C6C2C1,C4,C5C3C6C2C1,C4,C5C3C6C2C1,C4,C2,C5C3C6C1,C4,C2,C5C3C6C1,C4,C2,C5C3C6C1,C4,C2,C3,C5C6C1,C4,C2,C3,C5C6C1,C4,C2,C3,C5C6C1,C4,C2,C3,C5,C6C1,C4,C2,C3,C5,C6C1,C4,C2,C3,C5,C6C1,

38、C4,C2,C3,C5,C6C1,C4,C2,C3,C5,C6拓?fù)渑判蛩惴ǎ?設(shè)AOV網(wǎng)采用鄰接表表示，邊表為出邊表。算法中定義一個(gè)indegree數(shù)組，存放各頂點(diǎn)的入度。設(shè)置一個(gè)鏈棧存儲(chǔ)入度為0的頂點(diǎn)。拓?fù)渑判蚯?，先得到所有結(jié)點(diǎn)的入度，然后將所有入度為0的頂點(diǎn)壓棧。從棧頂取出一個(gè)頂點(diǎn)將其輸出，由它的出邊表可以得到以該頂點(diǎn)為起點(diǎn)的出邊，將這些邊終點(diǎn)的入度減1，即刪除這些邊。如果某條邊終點(diǎn)的入度為0，則將該頂點(diǎn)入棧。反復(fù)進(jìn)行上述操作，直到棧為空，如果這時(shí)輸出的頂點(diǎn)個(gè)數(shù)小于n，則說(shuō)明該AOV網(wǎng)中存在回路，否則，拓?fù)渑判蛘＝Y(jié)束。算法結(jié)束后，拓?fù)湫蛄写娣旁谧兞縫topo中。具體實(shí)現(xiàn)時(shí)，鏈?？梢岳庙?/p>

39、點(diǎn)表中值為0的indegree字段實(shí)現(xiàn)例子：AOV網(wǎng)的鄰接表表示如圖所示。按上述算法進(jìn)行拓?fù)渑判?C0C1C2225736C3C4C5C6C7843500221221C861拓?fù)湫蛄袨?C1, C4, C0, C7, C8, C2, C3, C6, C5設(shè)AOV網(wǎng)有n個(gè)頂點(diǎn)，e條邊，算法最初首先檢查入度為零的頂點(diǎn)，并將這些頂點(diǎn)壓棧，花費(fèi)的時(shí)間為O(n)。下面進(jìn)行拓?fù)渑判驎r(shí)，每個(gè)頂點(diǎn)都入棧一次，且每個(gè)頂點(diǎn)邊表中的邊結(jié)點(diǎn)都被檢查一遍，運(yùn)行時(shí)間為O(n+e)。因此，拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為O(n+e)算法復(fù)雜度：9.7 9.7 關(guān)鍵路徑關(guān)鍵路徑 9.7.1 AOE網(wǎng) 9.7.2 關(guān)鍵路徑 AOE網(wǎng)

40、：如果在帶權(quán)的有向圖中，用頂點(diǎn)表示事件，用有向邊表示活動(dòng)，邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間，則此帶權(quán)的有向圖稱為AOE網(wǎng)(Activity on edge network)。頂點(diǎn)所表示的事件實(shí)際上就是它的入邊所表示的活動(dòng)都已完成，它的出邊所表示的活動(dòng)可以開始這樣一種狀態(tài)。9.7.1 AOE網(wǎng)9.7.2 關(guān)鍵路徑問(wèn)題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始例例 設(shè)一個(gè)工程有設(shè)一個(gè)工程有1111項(xiàng)活動(dòng)，項(xiàng)活動(dòng)，9 9個(gè)事件個(gè)

41、事件事件事件 V1V1表示整個(gè)工程開始表示整個(gè)工程開始事件事件V9V9表示整個(gè)工程結(jié)束表示整個(gè)工程結(jié)束問(wèn)題：（問(wèn)題：（1 1）完成整項(xiàng)工程至少需要多少時(shí)間？）完成整項(xiàng)工程至少需要多少時(shí)間？ （2 2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4定義lAOE網(wǎng)(Activity On Edge)也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間l路徑長(zhǎng)度路徑上各活動(dòng)持續(xù)時(shí)間之和l關(guān)鍵路徑路徑長(zhǎng)度最長(zhǎng)的路徑叫l(wèi)Ve(j)表

42、示事件Vj的最早發(fā)生時(shí)間lVl(j)表示事件Vj的最遲發(fā)生時(shí)間le(i)表示活動(dòng)ai的最早開始時(shí)間ll(i)表示活動(dòng)ai的最遲開始時(shí)間ll(i)-e(i)表示完成活動(dòng)ai的時(shí)間余量l關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)叫，即l(i)=e(i)的活動(dòng)問(wèn)題分析l如何找e(i)=l(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)設(shè)活動(dòng)ai用弧用弧表示，其持續(xù)時(shí)間記為：表示，其持續(xù)時(shí)間記為：dut()則有：（則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkail如何求Ve(j)和Vl(j)？(1)從從Ve(1)=0開始向前遞推開始向前遞推為頭的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei=

43、求關(guān)鍵路徑步驟l求Ve(i)l求Vl(j)l求e(i)l求l(i)l計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn) Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng) e l l-e00002266046258377077071031616014140033例：AOE網(wǎng)包括11項(xiàng)活動(dòng)，9個(gè)事件，事件v0表示整個(gè)工程可以開始這樣一個(gè)狀態(tài)；事件v4表示活動(dòng)a3、a4已經(jīng)完成，活動(dòng)a6、a7可以開始這個(gè)狀態(tài)，事件v

44、8表示整個(gè)工程結(jié)束。如果權(quán)所表示的時(shí)間單位是天，則活動(dòng)a0需要6天完成，活動(dòng)a1需要4天完成，等等。整個(gè)工程一開始，活動(dòng)a0、a1、a2就可以并行進(jìn)行，而活動(dòng)a3、a4、a5只有當(dāng)事件v1、v2、v3分別發(fā)生后才能進(jìn)行，當(dāng)活動(dòng)a9、a10完成時(shí)，整個(gè)工程也就完成 v1 v6 a0 a3 v4 a6 a9 v8 v0 a1 a4 a10 4 v2 a7 a2 5 a8 v7 v3 a5 v5 6 1 1 2 9 7 4 2 4 關(guān)鍵路徑算法 計(jì)算ee(j)必須在頂點(diǎn)vj所有前驅(qū)頂點(diǎn)的最早發(fā)生時(shí)間都已經(jīng)求出的前提下進(jìn)行，而計(jì)算le(i)必須在頂點(diǎn)vi所有后繼頂點(diǎn)的最遲發(fā)生時(shí)間都已經(jīng)求出的前提下進(jìn)行，因此，頂點(diǎn)序列必須是一個(gè)拓?fù)湫蛄?算法復(fù)雜度：設(shè)AOE網(wǎng)有n個(gè)頂點(diǎn)，e條邊，在求事件可能的最早發(fā)生時(shí)間及允許的最遲發(fā)生時(shí)間，以及活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間時(shí)，都要對(duì)圖中所有頂點(diǎn)及每個(gè)頂點(diǎn)邊表中所有的邊結(jié)點(diǎn)進(jìn)行檢查，時(shí)間花費(fèi)為O(n+e)。因此，求關(guān)鍵路徑算法的時(shí)間復(fù)雜度為O(n+e)小結(jié)小結(jié)圖是一種復(fù)雜的非線性結(jié)構(gòu)。本章介紹了圖的基本概念，圖的相鄰矩陣和鄰接表兩種常用的存儲(chǔ)表示方法，討論了圖的周游、 最小生成樹、最短路徑、*拓?fù)渑判蚣?關(guān)鍵路徑等問(wèn)題，并給出了相應(yīng)的算法。重點(diǎn)是掌握?qǐng)D的存儲(chǔ)表示和各種算法的基本思想。lP.317復(fù)習(xí)題39l網(wǎng)絡(luò)課堂：9 圖l上機(jī)實(shí)驗(yàn)：7.1 7.2