9圖9.1 基本概念9.5 最短路徑9.2 圖的周游 9.6 拓?fù)渑判?.3 存儲(chǔ)表示 9.7 關(guān)鍵路徑9.4 最小生成樹(shù)重點(diǎn)內(nèi)容概述:圖的深度優(yōu)先搜索與廣度優(yōu)先搜索最小生成樹(shù)的Prim算法最小生成樹(shù)的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,v1,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ú)向圖中(vi ,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若是一條有向邊，則稱頂點(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)數(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 回路或環(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是連通的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)連通分量如右圖所示 v0 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 )查找圖中值為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 )找圖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)鄰接并存在回路，為了避免重復(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)先周游時(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 ) 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的所有相鄰結(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 ( 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!=NULL ) 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)圖的兩種鄰接矩陣分別為A3和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列非零列非零元素元素( (或非或非 元素元素) )個(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的信息指針字段(edgelist)存放與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)，因此，每條邊在邊表中存儲(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 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)字段 * */ /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; ;/ /* * 頂點(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 兩種表示的比較空間開(kāi)銷操作的實(shí)現(xiàn)l鄰接矩陣表示很容易判斷兩個(gè)頂點(diǎn)之間是否有邊相連。l求無(wú)向圖中頂點(diǎn)的度，兩種表示都容易；求有向圖中頂點(diǎn)的度，鄰接矩陣容易，求出度，鄰接表表示容易。鄰接矩陣表示的空間代價(jià)只與圖的頂點(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 基本概念： 生成樹(shù)DFS生成樹(shù)BFS生成樹(shù) 最小生成樹(shù)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è)連通子圖，稱為圖的一棵生成樹(shù) 構(gòu)造生成樹(shù)的過(guò)程可以按深度優(yōu)先周游，也可以按廣度優(yōu)先周游，周游中記錄訪問(wèn)的所有頂點(diǎn)以及經(jīng)過(guò)的邊，得到的是深度優(yōu)先生成樹(shù)或廣度優(yōu)先生成樹(shù)，簡(jiǎn)稱為DFSDFS生成樹(shù)或BFSBFS生成樹(shù)。 無(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生成樹(shù)BFS生成樹(shù) v0 v0 v0 v1 v3 v4 v5 v1 v3 v4 v5 v1 v3 v4 v5 v2 v6 v2 v6 v2 v6 有向圖DFS生成樹(shù)BFS生成樹(shù) 對(duì)于非連通的無(wú)向圖和非強(qiáng)連通的有向圖,從任一頂點(diǎn)出發(fā)無(wú)法訪問(wèn)到所有的頂點(diǎn)，只能得到各連通分量的生成樹(shù)所組成的生成樹(shù)林 圖的生成樹(shù)不唯一，從不同頂點(diǎn)出發(fā)，或從同一頂點(diǎn)出發(fā)，但周游的路徑不一樣，則得到的生成樹(shù)都不同 對(duì)于網(wǎng)絡(luò)，其生成樹(shù)中的邊也帶權(quán)，將生成樹(shù)各邊的權(quán)值總和稱為生成樹(shù)的權(quán)，并把權(quán)值最小的生成樹(shù)稱為最小生成樹(shù)(Minimum Spanning Tree)應(yīng)用：城市中利用最小生成樹(shù)建立通訊網(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)值最小的邊，則一定存在邊中權(quán)值最小的邊，則一定存在GG的一棵的一棵最小生成樹(shù)包括此邊最小生成樹(shù)包括此邊(u,v)(u,v)注注 ：MSTMST性質(zhì)可以用反證法證明性質(zhì)可以用反證法證明9.4.2 9.4.2 最小生成樹(shù)的構(gòu)造最小生成樹(shù)的構(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，vV-U)，將邊加入TE，并將頂點(diǎn)v加入集合U。重復(fù)上述操作直到U=V為止。這時(shí)TE中有n-1條邊，T=(U，TE)就是G的一棵最小生成樹(shù)例1654326513566425131163141643142116432142516543214253Kruskal算法的基本思想是 設(shè)G=(V，E)是網(wǎng)絡(luò)，最小生成樹(shù)的初始狀態(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的一棵最小生成樹(shù)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)度最短的那條路徑稱為兩個(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加入集合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次算法的時(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 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)活動(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，該線性序列具有以下性質(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é)期只能選修一門(mén)課，則他必須按照某一個(gè)拓?fù)湫蛄械拇涡驅(qū)W習(xí)，才能保證學(xué)習(xí)任何一門(mén)課時(shí)，其先修課程已學(xué)過(guò)。 C0 C7 C8 C6 C2 C3 C5 C1 C4 注意：1、一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁灰欢ㄊ俏ㄒ坏摹?、假設(shè)AOV網(wǎng)代表一個(gè)工程，如果條件限制只能串行工作，則AOV網(wǎng)某一拓?fù)湫蛄芯褪钦麄€(gè)工程得以順利完成的一種可行方案。 AOV網(wǎng)中一定不能出現(xiàn)回路(因?yàn)槌霈F(xiàn)回路意味著，某些活動(dòng)的開(kāi)工是以自己工作的完成作為先決條件，這種現(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ō)明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,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ù)渑判蚯埃鹊玫剿薪Y(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í)，鏈棧可以利用頂點(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)：如果在帶權(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)可以開(kāi)始這樣一種狀態(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)可以開(kāi)始每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開(kāi)始例例 設(shè)一個(gè)工程有設(shè)一個(gè)工程有1111項(xiàng)活動(dòng)，項(xiàng)活動(dòng)，9 9個(gè)事件個(gè)事件事件事件 V1V1表示整個(gè)工程開(kāi)始表示整個(gè)工程開(kāi)始事件事件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)表示事件Vj的最早發(fā)生時(shí)間lVl(j)表示事件Vj的最遲發(fā)生時(shí)間le(i)表示活動(dòng)ai的最早開(kāi)始時(shí)間ll(i)表示活動(dòng)ai的最遲開(kāi)始時(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開(kāi)始向前遞推開(kāi)始向前遞推為頭的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei=求關(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è)工程可以開(kāi)始這樣一個(gè)狀態(tài)；事件v4表示活動(dòng)a3、a4已經(jīng)完成，活動(dòng)a6、a7可以開(kāi)始這個(gè)狀態(tài)，事件v8表示整個(gè)工程結(jié)束。如果權(quán)所表示的時(shí)間單位是天，則活動(dòng)a0需要6天完成，活動(dòng)a1需要4天完成，等等。整個(gè)工程一開(kāi)始，活動(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)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(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ǔ)表示方法，討論了圖的周游、 最小生成樹(shù)、最短路徑、*拓?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