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

1、9圖9.1 基本概念9.5 最短路徑9.2 圖的周游 9.6 拓?fù)渑判?.3 存儲表示 9.7 關(guān)鍵路徑9.4 最小生成樹重點內(nèi)容概述:圖的深度優(yōu)先搜索與廣度優(yōu)先搜索最小生成樹的Prim算法最小生成樹的Kruskal算法單源最短路徑Dijkstra算法所有頂點對之間最短路徑的Floyd算法圖的應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑9.1 9.1 圖的基本概念圖的基本概念: :圖圖是由頂點的有窮非空集合V和邊（頂點的偶對）的集合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)有向圖和無向圖有向圖有向圖定義:若圖中的每條邊都是有方向的表示:有向圖中的邊是由兩個頂點組成的有序?qū)?，有序?qū)τ眉饫ㄌ柋硎救绫硎疽粭l有向邊，vi是邊的始點，vj是邊的終點。和代表兩條不同的有向邊。無向圖無向圖定義:若圖中每條邊都是無方向的表示:無向圖中的邊是由兩個頂點組成的無序?qū)?，無序?qū)τ脠A括號表示無向圖中(v

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

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

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)中，若存在頂點序列vi0, vi1, , vin，使得(vi0, vi1)，( vi1, vi2)， (vin-1, vin)都在E中(若是有向圖，則使得，都在E中)，則稱從頂點vi0到vin存在一條路徑l 路徑長度:路徑上的邊數(shù)。l 簡單路徑:若路徑上的頂點除vi0和vin可以相同外,其它頂點都不相同.l 回路

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

7、l連通圖：若V(G)中任意兩個不同的頂點vi和vj都是連通的(即有路徑)，則稱G為連通圖l連通分量：無向圖G中的最大連通子圖稱為G的連通分量l強連通圖：有向圖G=(V，E)中，若V(G)中任意兩個不同的頂點vi和vj都存在從vi到vj以及從vj和vi的路徑，則稱圖G是強連通圖l強連通分量：有向圖的最大強連通子圖稱為圖的強連通分量l如圖G2和G3都是連通圖l如圖G4是非連通圖，它的兩個連通分量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是非強連通圖它的兩個強連通分量如右圖所示 v

8、0 v1 v2 v0 v2 v1 G1l若圖的每條邊都賦上一個權(quán)，則稱為帶權(quán)圖l帶權(quán)的連通圖稱為網(wǎng)絡(luò)。通常權(quán)是具有某種意義的數(shù)，下圖為一個網(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)建一個空圖 Graph createGraph ( )判斷圖g是否空圖，是則返回1，否則返回0int isNullGraph ( g )找圖中的第一個頂點，如果圖是空圖則返回NULLVertex firstVertex ( g )找圖中頂點vi的下一個頂點Vertex nextVertex ( g , vi )查找圖中

9、值為value的頂點Vertex searchVertex ( g , value )在圖g中增加一個值為value的頂點Graph addVertex ( g , value )在圖g中刪除一個頂點和與該頂點相關(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中與頂點v相鄰的第一個頂點 Vertex firstAdjacent ( g , v ) /v與返回頂點構(gòu)成的邊也稱為與v相關(guān)聯(lián)的第一條邊。找圖g中與vi相鄰的，相對相鄰頂點vj的，下一個相鄰頂點Vertex nextAdjacent ( g , vi , vj ) /vi與返回值構(gòu)成的邊也稱為是vi與vj構(gòu)成的邊的下一條邊end ADT Graph9.2 圖的周游圖的周游是從圖中某個頂點出發(fā)，按照某種方式系統(tǒng)地訪問圖中的所有頂點，使每個頂點僅被訪問一次。也稱圖的遍歷。連通圖或強連通圖：則從圖中任意一頂點出發(fā)都可以訪問圖中所有頂點。由于圖中每個頂點都可能與圖中其它多個頂點鄰接并存在回路，

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

12、游時，按訪問頂點的先后次序所得到的頂點序列，稱為該的先后次序所得到的頂點序列，稱為該圖的深度優(yōu)先周游序列，簡稱圖的深度優(yōu)先周游序列，簡稱DFSDFS。l從上述的搜索方法可知，周游過程是一從上述的搜索方法可知，周游過程是一個遞歸的過程。個遞歸的過程。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），具體思想是 從圖的指定頂點v出發(fā)，先訪問頂點v，并將其標(biāo)記為已訪問過，接著依次訪問v的所

14、有相鄰結(jié)點w1，w2，wx，然后，再依次訪問與w1，w2，wx鄰接的所有未被訪問過的頂點，以此類推，直到所有已訪問頂點的相鄰結(jié)點都被訪問過為止。如果圖中還有未被訪問過的頂點，則從某個未被訪問過的頂點出發(fā)進(jìn)行廣度優(yōu)先搜索，直到所有頂點都被訪問過為止。 廣度優(yōu)先周游得到的頂點序列稱為廣度優(yōu)先周游序列，簡稱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 ;/* 隊列元素的類型為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ù)雜，任意兩個頂點間都可能存在聯(lián)系，因而圖的存儲方法也很多，應(yīng)根據(jù)具體的應(yīng)用和施加的操作選擇圖的存儲表示法 9.3圖的存儲鄰接矩陣表示法鄰接表表示法鄰接多重表表示法、圖的十字鏈表等9.3.1 鄰接矩陣是表示頂點間相鄰關(guān)系的矩陣設(shè)G=(V，E)為具有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無向圖的鄰接矩陣一定是一對稱矩陣無向圖的鄰接矩陣一定是一對稱矩陣l無向圖的鄰接矩陣的第無向圖的鄰接矩陣的第i i行行( (或第或第i i列列) )非零元素非零元素( (或非或非 元素元素) )個數(shù)為第個數(shù)為第i i個頂點的個頂點的度度D(vD(vi i) )。l有向圖的鄰接矩陣的第有向圖的鄰接矩陣的第i i行非零元素行非零元素( (或非或非 元元素素) )個數(shù)為第個數(shù)為第i i個頂點的出個頂點的出度度OD(vOD(vi i) )，第，第i i列非零列非零元素元素

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

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

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

21、 v2 v1 v2 v4 v3 鄰接表表示法的存儲結(jié)構(gòu)定義如下鄰接表表示法的存儲結(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; ;/ /* * 相鄰頂點字段相鄰頂點字段

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

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

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

25、以及經(jīng)過的邊，得到的是深度優(yōu)先生成樹或廣度優(yōu)先生成樹，簡稱為DFSDFS生成樹或BFSBFS生成樹。 無向圖 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生成樹 對于非連通的無向圖和非強連通的有向圖,從任一頂點出發(fā)無法訪問到所有的頂點，只能得到各連通分量的生成樹所組成的生成樹林 圖的生成樹不唯一，從不同頂點出發(fā)，或從同一頂

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

28、V-U)，將邊加入TE，并將頂點v加入集合U。重復(fù)上述操作直到U=V為止。這時TE中有n-1條邊，T=(U，TE)就是G的一棵最小生成樹例1654326513566425131163141643142116432142516543214253Kruskal算法的基本思想是 設(shè)G=(V，E)是網(wǎng)絡(luò)，最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V，)，T中每個頂點自成為一個連通分量。將集合E中的邊按遞增順序排列，從小到大依次選擇頂點分別在兩個連通分量中的邊加入圖T，則原來的兩個連通分量由于該邊的連接而成為一個連通分量。依次類推，直到T中所有頂點都在同一個連通分量上為止，該連通分量就是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 最短路徑最短路徑基本概念：路徑：如果圖中從一個頂點可以到達(dá)另一個頂點，則這兩個頂點間存在一條路徑。(從一個頂點到另一個頂點間可能存在多條路徑，而每條路徑上經(jīng)過的邊數(shù)并不一定相同)路徑長度：如果圖是一個帶權(quán)圖，則路徑長度為路徑上各邊的權(quán)值的總和。最短路徑長度：兩個頂點間路徑長度最短的那條路徑稱為

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

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

32、法的時間復(fù)雜度為O(n2)Floyd算法基本思想：設(shè)圖G=(V，E)，有n個頂點，圖采用鄰接矩陣作為存儲結(jié)構(gòu)。如果邊(vi，vj)E，則從頂點vi到頂點vj存在一條長度為arcsij的路徑，該路徑并不一定是從頂點vi到頂點vj的最短路徑，因為可能存在從vi到vj并且包含其它頂點為中間頂點的路徑。因此，應(yīng)該在所有從vi到vj允許其它頂點為中間頂點的路徑中，找出長度最短的路徑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時間復(fù)雜度：時間復(fù)雜度：Floyd算法中初始化部分由一個循環(huán)組成，其中外循環(huán)運行n次，內(nèi)循環(huán)也運行n次，初始化部分的時間復(fù)雜度為O(n2)。迭代生成矩陣A和路徑nextvex的部分為三個循環(huán)的嵌套，其時間復(fù)雜度為O(n3)Floyd算法的時間復(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)：如果用圖中的頂點表示活動，邊表示活動間的先后關(guān)系，則這樣的有向圖稱為頂點

34、活動網(wǎng)(Activity On Vertex network，簡稱AOV網(wǎng))AOV網(wǎng)中的弧表示活動之間存在的制約關(guān)系例子：計算機專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)，這時工程就是完成給定的學(xué)習(xí)計劃，而活動就是學(xué)習(xí)課程，這些課程的名稱與代號如表所示在AOV網(wǎng)中，用頂點表示課程，有向邊表示課程之間的優(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ù)渑判?對于一個AOV網(wǎng)，其所有頂點可以排成一個線性序列vi1，vi2，vin，該線性序列具

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

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

37、AOV網(wǎng)中存在回路，拓?fù)渑判驘o法再進(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)采用鄰接表表示，邊表為出邊表。算法中定義一個indegree數(shù)組，存放各頂點的入度。設(shè)置一個鏈棧存儲入度為0的頂點。拓?fù)渑判蚯?，先得到所有結(jié)點的入度，然后將所有入度為0的頂點壓棧。從棧頂取出一個頂點將其輸出，由它的出邊表可以得到以該頂點為起點的出邊，將這些邊終點的入度減1，即刪除這些邊。如果某條邊終點的入度為0，則將該頂點入棧。反復(fù)進(jìn)行上述操作，直到棧為空，如果這時輸出的頂點個數(shù)小于n，則說明該AOV網(wǎng)中存在回路，否則，拓?fù)渑判蛘＝Y(jié)束。算法結(jié)束后，拓?fù)湫蛄写娣旁谧兞縫topo中。具體實現(xiàn)時，鏈棧可以利用頂

39、點表中值為0的indegree字段實現(xiàn)例子：AOV網(wǎng)的鄰接表表示如圖所示。按上述算法進(jìn)行拓?fù)渑判?C0C1C2225736C3C4C5C6C7843500221221C861拓?fù)湫蛄袨?C1, C4, C0, C7, C8, C2, C3, C6, C5設(shè)AOV網(wǎng)有n個頂點，e條邊，算法最初首先檢查入度為零的頂點，并將這些頂點壓棧，花費的時間為O(n)。下面進(jìn)行拓?fù)渑判驎r，每個頂點都入棧一次，且每個頂點邊表中的邊結(jié)點都被檢查一遍，運行時間為O(n+e)。因此，拓?fù)渑判蛩惴ǖ臅r間復(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)的有向圖中，用頂點表示事件，用有向邊表示活動，邊上的權(quán)值表示活動持續(xù)的時間，則此帶權(quán)的有向圖稱為AOE網(wǎng)(Activity on edge network)。頂點所表示的事件實際上就是它的入邊所表示的活動都已完成，它的出邊所表示的活動可以開始這樣一種狀態(tài)。9.7.1 AOE網(wǎng)9.7.2 關(guān)鍵路徑問題提出把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始每個事件表示在它之前的活動已完成，在它之后的活動可以開始例例 設(shè)一個工程有設(shè)一個工程有1111項活動，項活動，9 9個事件個

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

42、示事件Vj的最早發(fā)生時間lVl(j)表示事件Vj的最遲發(fā)生時間le(i)表示活動ai的最早開始時間ll(i)表示活動ai的最遲開始時間ll(i)-e(i)表示完成活動ai的時間余量l關(guān)鍵活動關(guān)鍵路徑上的活動叫，即l(i)=e(i)的活動問題分析l如何找e(i)=l(i)的關(guān)鍵活動？設(shè)活動設(shè)活動ai用弧用弧表示，其持續(xù)時間記為：表示，其持續(xù)時間記為：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計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動 e l l-e00002266046258377077071031616014140033例：AOE網(wǎng)包括11項活動，9個事件，事件v0表示整個工程可以開始這樣一個狀態(tài)；事件v4表示活動a3、a4已經(jīng)完成，活動a6、a7可以開始這個狀態(tài)，事件v

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