圖的定義和術(shù)語

1、第第7 7章章 圖圖目錄目錄v圖的定義和術(shù)語v圖的存儲結(jié)構(gòu)v圖的遍歷v圖的連通性問題v有向無環(huán)圖及其應用v最短路徑245136G17.1 圖的定義和術(shù)語圖的定義和術(shù)語v圖被廣泛地用于模擬真實事件或抽象問題。在語言學、邏輯學、物理、化學、電訊工程、計算機、數(shù)學等學科領(lǐng)域得到了廣泛的應用。網(wǎng)絡(luò)連接圖例網(wǎng)絡(luò)連接圖例v圖是由頂點集合V及頂點間的關(guān)系集合E組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph( V, E ) 任意一對頂點間都可以有關(guān)系；圖是最基本的數(shù)據(jù)結(jié)構(gòu)，樹和線性表可看作受限圖。7.1 圖的定義和術(shù)語圖的定義和術(shù)語245136G17.1 圖的定義和術(shù)語圖的定義和術(shù)語v有向圖與無向圖 在有向圖中，頂點對是有

2、序的。在無向圖中，頂點對(x, y)是無序的。例例245136G1例例157324G267.1 圖的定義和術(shù)語圖的定義和術(shù)語v完全圖 若有 n 個頂點的無向圖有 n(n-1)/2 條邊, 則此圖為完全無向圖。有 n 個頂點的有向圖有n(n-1) 條邊, 則此圖為完全有向圖。213有向完全圖有向完全圖213無向完全圖無向完全圖7.1 圖的定義和術(shù)語圖的定義和術(shù)語v鄰接頂點 如果 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點。v頂點 v 的入度 是以 v 為終點的有向邊的條數(shù)頂點 v 的出度 是以 v 為始點的有向邊的條數(shù)2451367.1 圖的定義和術(shù)語圖的定義和術(shù)語v

3、權(quán)某些圖的邊具有與它相關(guān)的數(shù), 稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。7.1 圖的定義和術(shù)語圖的定義和術(shù)語v子圖設(shè)有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 則稱 圖G 是 圖G 的子圖。7.1 圖的定義和術(shù)語圖的定義和術(shù)語v簡單路徑若路徑上各頂點 v1,v2,.,vm 均不互相重復, 則稱這樣的路徑為簡單路徑。v回路若路徑上第一個頂點 v1 與最后一個頂點vm 重合, 則稱這樣的路徑為回路或環(huán)。7.1 圖的定義和術(shù)語圖的定義和術(shù)語連通圖 圖中任意兩個頂點都有路徑強連通圖 在有向圖中, 每一對頂點vi和vj, 都存在一條從vi到vj和從vj到vi的路徑連通圖連通圖例例2451

4、36強連通圖強連通圖356例例7.1 圖的定義和術(shù)語圖的定義和術(shù)語連通分量 非連通圖的極大連通子圖7.1 圖的定義和術(shù)語圖的定義和術(shù)語v生成樹 一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。但有向圖則可能得到它的由若干有向樹組成的生成森林。7.1 圖的定義和術(shù)語圖的定義和術(shù)語v圖的基本操作CreateGraph(&G,V,VR); / 按V和VR的定義構(gòu)造圖G。DestroyGraph(&G); / 銷毀圖G。 LocateVex(G, u); / 查找頂點u GetVex(G, v); / 返回v的值。PutVex(&G, v, value)

5、; / 對v賦值value。FirstAdjVex(G, v); / 返回v的第一個鄰接點 NextAdjVex(G, v, w); /返回v的下一個鄰接點。 245136 7.1 圖的定義和術(shù)語圖的定義和術(shù)語v圖的基本操作(續(xù)）InsertVex(&G, v); / 在圖G中增添新頂點v。DeleteVex(&G, v); / 刪除G中頂點v及其相關(guān)的弧。 InsertArc(&G, v, w); / 在G中增添弧， DeleteArc(&G, v, w); /在G中刪除弧， DFSTraverse(G, v, Visit(); / 從頂點v起深度優(yōu)先遍歷圖

6、BFSTraverse(G, v, Visit(); / 從頂點v起廣度優(yōu)先遍歷圖245136 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)v圖的數(shù)組（鄰接矩陣）存儲表示圖的數(shù)組（鄰接矩陣）存儲表示 用一個矩陣表示圖結(jié)構(gòu)用一個矩陣表示圖結(jié)構(gòu)，其它0E(G)v,v或)v,(v若1,jijijiA例例G1241300011000000001107.2.1 圖數(shù)組表示法圖數(shù)組表示法v網(wǎng)絡(luò)的鄰接矩陣網(wǎng)絡(luò)的鄰接矩陣 ),( , ,),( .jijiEjiEjijijiWjiEdge=! !0=A對角線但是否則,或且如果7.2.1 圖數(shù)組表示法圖數(shù)組表示法v在有向圖中在有向圖中, , 統(tǒng)計第統(tǒng)計第 i i 行行 1

7、1 的個數(shù)可得頂點的個數(shù)可得頂點 i i 的的出度，統(tǒng)計第出度，統(tǒng)計第 j j 行行 1 1 的個數(shù)可得頂點的個數(shù)可得頂點 j j 的入度。的入度。v在無向圖中在無向圖中, , 統(tǒng)計統(tǒng)計1 1 的個數(shù)可得的個數(shù)可得邊的個數(shù)的兩倍。邊的個數(shù)的兩倍。7.2.1 圖數(shù)組表示法圖數(shù)組表示法v無向圖的鄰接矩陣是對稱矩陣無向圖的鄰接矩陣是對稱矩陣7.2.1 圖數(shù)組表示法圖數(shù)組表示法v鄰接矩陣存儲結(jié)構(gòu)鄰接矩陣存儲結(jié)構(gòu)#define INF INT_MAX /最大值#define MAX_VER_NUM 20 /頂點個數(shù)typedef struct ElemType vexsMAX_VER_NUM; /頂點向

8、量 int arcsMAX_VER_NUMMAX_VER_NUM ;/鄰接矩陣 int vexnum, arcnum; /圖的頂點數(shù)和邊數(shù) int kind; /圖的種類MGraph;7.2.1 圖數(shù)組表示法圖數(shù)組表示法v基本操作的實現(xiàn)基本操作的實現(xiàn)構(gòu)造圖構(gòu)造圖輸入：邊輸入：邊a,b 輸出：鄰接矩陣表示輸出：鄰接矩陣表示算法：算法：初始化鄰接矩陣為初始化鄰接矩陣為0 0； 輸入一條邊輸入一條邊a,b ； 令頂點令頂點a a的序號為的序號為i,i,設(shè)頂點設(shè)頂點b b的序號為的序號為j;j; 鄰接矩陣的元素鄰接矩陣的元素ijij=1=1； 重復重復-步，直到輸入全部的邊步，直到輸入全部的邊7.2

9、圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)v鄰接表鄰接表用數(shù)組存儲所有結(jié)點每個頂點采用一鏈表存儲對應的所有鄰接點7.2.2 圖的鄰接表圖的鄰接表v在有向圖的鄰接表中易于計算頂點的出度；在有向圖的鄰接表中易于計算頂點的出度；v計算頂點的入度，可采用逆連接表計算頂點的入度，可采用逆連接表7.2.2 圖的鄰接表圖的鄰接表v網(wǎng)絡(luò)（帶權(quán)圖）的鄰接表網(wǎng)絡(luò)（帶權(quán)圖）的鄰接表7.3 圖的遍歷圖的遍歷v從圖中某一頂點出發(fā)訪遍圖中其余頂點，且從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程就叫使每一個頂點僅被訪問一次。這一過程就叫做做圖的遍歷圖的遍歷。v通常有兩條遍歷圖的路徑通常有兩條遍歷圖的路徑深度優(yōu)先搜

10、索遍歷深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷7.3 圖的遍歷圖的遍歷7.3 圖的遍歷圖的遍歷v解決回路問題解決回路問題7.3 圖的遍歷圖的遍歷v解決不可到達問題解決不可到達問題7.3.1 圖的深度優(yōu)先搜索圖的深度優(yōu)先搜索v深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是類似于樹的先根遍歷，是樹的先根遍歷的推廣樹的先根遍歷的推廣v思路：思路：從圖中某個頂點從圖中某個頂點V出發(fā)，訪問此頂點出發(fā)，訪問此頂點；然后依次從然后依次從V的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和直至圖中所有和V有路徑有路徑的頂點都被訪問到的頂點都被訪問到；

11、若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起點，重復上述過程，直至圖中所有頂點訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止都被訪問為止。7.3.1 圖的深度優(yōu)先搜索圖的深度優(yōu)先搜索7.3.1 圖的深度優(yōu)先搜索圖的深度優(yōu)先搜索DFS ( G, v) / 從第從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。 visitedv = TRUE; /訪問訪問 for (w=FirstAdjVex(v); w!=0; w=NextAdjVex(v) ) if (!visitedw) DFS (G, w)

12、; / 對對v的尚未訪問的鄰接頂點的尚未訪問的鄰接頂點w遞歸調(diào)用遞歸調(diào)用DFS7.3.1 圖的深度優(yōu)先搜索圖的深度優(yōu)先搜索DFSTrav（）（） / 深度優(yōu)先遍歷。深度優(yōu)先遍歷。for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問標志數(shù)組初始化訪問標志數(shù)組初始化for (v=0; vvexnum; +v) / 從每個頂點出發(fā)調(diào)用從每個頂點出發(fā)調(diào)用DFS if (!visitedv) DFS (v, L);為不連通的圖也能訪問所有頂點，為不連通的圖也能訪問所有頂點，要從每個頂點出發(fā)，做深度優(yōu)先要從每個頂點出發(fā)，做深度優(yōu)先搜索，即調(diào)用搜索，即調(diào)用DFS(

13、).DFS( ).7.3.2 圖的廣度優(yōu)先搜索圖的廣度優(yōu)先搜索v度優(yōu)先搜索遍歷度優(yōu)先搜索遍歷類似于樹的層次遍歷類似于樹的層次遍歷 使用廣度優(yōu)先搜索在訪問了起始頂點使用廣度優(yōu)先搜索在訪問了起始頂點 v v 之后，由之后，由 v v 出發(fā)，依次訪問出發(fā)，依次訪問 v v 的各個未曾被訪問過的鄰接頂點的各個未曾被訪問過的鄰接頂點 w w1, 1, w w2, 2, , , wtwt，然后再順序訪問，然后再順序訪問 w w1, 1, w w2, 2, , , wt wt 的所有還的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還

14、未被訪問過的鄰接頂點，訪問它們的所有還未被訪問過的鄰接頂點， 如此做下如此做下去，直到圖中所有頂點都被訪問到為止。去，直到圖中所有頂點都被訪問到為止。7.3.2 圖的廣度優(yōu)先搜索圖的廣度優(yōu)先搜索v算法算法為了實現(xiàn)逐層訪問，算法中使用了一個隊列，以為了實現(xiàn)逐層訪問，算法中使用了一個隊列，以記憶正在訪問的頂點，以便于向下一層訪問。記憶正在訪問的頂點，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復訪問，需與深度優(yōu)先搜索過程一樣，為避免重復訪問，需要一個輔助數(shù)組要一個輔助數(shù)組 visited ，給被訪問過的頂點加，給被訪問過的頂點加標記標記V1V2V4V5V3V7V6V87.3.2 圖的廣度優(yōu)

15、先搜索圖的廣度優(yōu)先搜索 for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化初始化 for ( v=0; vG.vexnum; +v ) /從每個頂點出發(fā)從每個頂點出發(fā) if ( !visitedv) / v尚未訪問尚未訪問 visitedu = TRUE; EnQueue(Q,v); / v入隊列入隊列 while (!Q.queueEmpty( ) DeQueue(Q,u ); / 隊頭元素出隊并賦給隊頭元素出隊并賦給u for (w=FirstAdjVex(u); w!=0; w=NextAdjVex(u) ) /所有鄰接點所有鄰接點 if (

16、! visitedw) / u的尚未訪問的鄰接頂點的尚未訪問的鄰接頂點w入隊列入隊列Q visitedu = TRUE; EnQueue(Q,w); 7.3 圖的遍歷圖的遍歷v當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在的最大連通子圖點，只能訪問到該頂點所在的最大連通子圖( (連通分量連通分量) )的所的所有頂點。有頂點。v若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷，若從無向圖的每一個連通分量中的一個

17、頂點出發(fā)進行遍歷，可求得無向圖的所有連通分量。可求得無向圖的所有連通分量。v在算法中，需要對圖的每一個頂點進行檢測：若已被訪問過，在算法中，需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量7.4 最小生成樹最小生成樹v問題：假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？ 7.4 最小生成樹v該問題等價于： 構(gòu)造網(wǎng)的一棵最小生成樹，

18、即：在e條帶權(quán)的邊中選取n-1條（不構(gòu)成回路），使“權(quán)值之和”為最小。 7.4 最小生成樹v最小生成樹（MST）性質(zhì)假設(shè)G=(V, E)是一個無向連通網(wǎng)，U是頂點集V的一個非空子集。若(u, v)是一條具有最小權(quán)值的邊，其中uU，vVU，則必存在一棵包含邊(u, v)的最小生成樹頂點集合頂點集合U-V頂點集合頂點集合U7.4 最小生成樹v普里姆算法的基本思想： 從連通網(wǎng)絡(luò) N = V, E 中的某一頂點 u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，將其頂點加入到生成樹的頂點集合U中。 以后每一步從一個頂點在U中，而另一個頂點在V-U中的各條邊中選擇權(quán)值最小的邊(u, v),把它的

19、頂點加入到集合U中。 如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U中為止。普里姆算法構(gòu)造最小生成樹的過程普里姆算法構(gòu)造最小生成樹的過程24543424554347245543477普里姆算法構(gòu)造最小生成樹的過程（普里姆算法構(gòu)造最小生成樹的過程（ 續(xù)）續(xù)）245543472455434724554347v輸入：無向聯(lián)通圖G=(V, E)v輸出：最小生成樹TE(U, TE)v算法：1.初始時任取一個頂點v，從v出發(fā)；此時U=v,TE= ;2.從頂點集U中取一頂點u0,從V-U集合中取一頂點v0,使邊(u0,v0）權(quán)值最??；3.將該邊加入到集合TE，并將u0并入U集合； 重復2、3步n

20、-1次。7.4.1 最小生成樹Prim算法7.4 最小生成樹vPrim算法的實現(xiàn)圖的存儲結(jié)構(gòu)采用鄰接矩陣7.4 最小生成樹vPrim算法的實現(xiàn)(續(xù))設(shè)置一個輔助數(shù)組closedge , 用于存放集合VU中的各頂點到集合中頂點的最小交叉邊及其權(quán)值.typedef struct VertexType adjvex; /頂點 int lowcost; /邊的權(quán)值 closedgeNUM; 0 1 2 3 4 5 6下標作為下標作為邊的另一邊的另一個端點個端點0,00,28 0, 0, 0, 0, 10 0, 0 1 2 3 4 5 6vPrim算法實現(xiàn)舉例算法實現(xiàn)舉例初始時，從初始時，從頂點頂點0出

21、發(fā)出發(fā)輔助數(shù)組closedge ：vPrim算法實現(xiàn)舉例(續(xù)1)選一個最小選一個最小權(quán)值的邊權(quán)值的邊0,00,28 0, 0, 0, 0, 10 0, 0 1 2 3 4 5 6輔助數(shù)組closedge ：0輸出邊輸出邊(0,5),并將頂并將頂點點5加入加入U集合集合0,00,28 0, 0, 0, 0, 10 0, 0 1 2 3 4 5 60輔助數(shù)組closedge ：vPrim算法實現(xiàn)舉例(續(xù)2)05更新數(shù)據(jù)：存儲頂點更新數(shù)據(jù)：存儲頂點0和和5出發(fā)的邊中的小者出發(fā)的邊中的小者0,00,28 0, 0, 0, 0, 00, 0 1 2 3 4 5 65,2505vPrim算法實現(xiàn)舉例(續(xù)3

22、)又選一個最小的權(quán)值又選一個最小的權(quán)值0,00,28 0, 0, 5, 25 0, 00, 0 1 2 3 4 5 6vPrim算法實現(xiàn)舉例(續(xù)4)05輸出邊輸出邊(5,4),并將并將頂點頂點4加入集合加入集合U0,00,28 0, 0, 5, 25 0, 00, 0 1 2 3 4 5 60054vPrim算法實現(xiàn)舉例(續(xù)5)0,00,28 0, 0, 5, 00, 00, 0 1 2 3 4 5 6更新數(shù)據(jù)：增加頂點更新數(shù)據(jù)：增加頂點4出發(fā)的權(quán)值小的邊出發(fā)的權(quán)值小的邊4,224,24054vPrim算法實現(xiàn)舉例(續(xù)6)0,00,28 0, 4, 22 5, 00, 04, 24 0 1 2

23、 3 4 5 6選一個最小的權(quán)值選一個最小的權(quán)值054vPrim算法實現(xiàn)舉例(續(xù)7)0,00,28 0, 4, 22 5, 00, 04, 24 0 1 2 3 4 5 6輸出邊輸出邊(4,3),并將并將頂點頂點3加入集合加入集合U0vPrim算法實現(xiàn)舉例(續(xù)8)05430,00,28 0, 4, 05, 00, 04, 24 0 1 2 3 4 5 6更新數(shù)據(jù)：增加頂點更新數(shù)據(jù)：增加頂點3出發(fā)的權(quán)值小的邊出發(fā)的權(quán)值小的邊3,123,180543vPrim算法實現(xiàn)舉例(續(xù)9)0,00,28 3, 12 4, 05, 00, 03, 18 0 1 2 3 4 5 6選最小的權(quán)值選最小的權(quán)值vPr

24、im算法實現(xiàn)舉例(續(xù)10)05430,00,28 3, 12 4, 05, 00, 03, 18 0 1 2 3 4 5 6輸出邊輸出邊(3,2),并將并將頂點頂點2加入集合加入集合U00543vPrim算法實現(xiàn)舉例(續(xù)11)2054320,00, 28 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6更新數(shù)據(jù)：增加頂點更新數(shù)據(jù)：增加頂點2出發(fā)的權(quán)值小的邊出發(fā)的權(quán)值小的邊2,16vPrim算法實現(xiàn)舉例(續(xù)12)0,02, 16 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6選最小的權(quán)值選最小的權(quán)值05432vPrim算法實現(xiàn)舉例(續(xù)13)0,02,

25、 16 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6輸出邊輸出邊(2,1),并將并將頂點頂點1加入集合加入集合U0vPrim算法實現(xiàn)舉例(續(xù)14)0543210,02, 03, 04, 05, 00, 03, 18 0 1 2 3 4 5 6更新數(shù)據(jù)：增加頂點更新數(shù)據(jù)：增加頂點1出發(fā)的權(quán)值小的邊出發(fā)的權(quán)值小的邊1,14054321vPrim算法實現(xiàn)舉例(續(xù)15)0,02, 03, 04, 05, 00, 01, 14 0 1 2 3 4 5 6最后，最小的權(quán)值為最后，最小的權(quán)值為邊邊(1,6)，輸出該邊，輸出該邊0543216vPrim算法實現(xiàn)舉例(續(xù)16)7.4.1

26、 最小生成樹Prim算法v1. 1. 初始化輔助數(shù)組初始化輔助數(shù)組closedge ；v2. 2. 輸出頂點輸出頂點v v，將頂點，將頂點v v加入集合加入集合U U中；中；v3. 3. 重復執(zhí)行下列操作重復執(zhí)行下列操作n-1n-1次次 在在lowcostlowcost中選取最短邊，取中選取最短邊，取adjvexadjvex中對應的頂中對應的頂點序號點序號k k； 輸出頂點輸出頂點k k和對應的權(quán)值；和對應的權(quán)值； 將頂點將頂點k k加入集合加入集合U U中；中； 調(diào)整數(shù)組調(diào)整數(shù)組lowcostlowcost和和adjvexadjvex；7.4.1 最小生成樹Prim算法 k = Locate

27、Vex ( G, u ); / / 頂點頂點u u為構(gòu)造生成樹的起始點為構(gòu)造生成樹的起始點 for ( j=0; jG.vexnum; +j ) / / 輔助數(shù)組初始化輔助數(shù)組初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / / 初始，初始，U Uuu for (i=0; iG.vexnum; +i) /在其余頂點中選擇在其余頂點中選擇 k = minimum(closedge); / / 選最小邊選最小邊 printf(closedgek.adjvex, G.vexsk); / / 輸出該邊輸出該邊 cl

28、osedgek.lowcost = 0; /并將頂并將頂k k加入加入U U集集 for (j=0; jG.vexnum; +j) /更新輔助數(shù)組更新輔助數(shù)組 if (G.arcskj.adj closedgej.lowcost) / / 新頂點并入新頂點并入U U后重新選擇最小邊更新輔助數(shù)組后重新選擇最小邊更新輔助數(shù)組 closedgej = G.vexsk, G.arcskj.adj ; 時間復雜度O(n2)7.4.1 最小生成樹Kruskal算法v基本思想基本思想 每次選不屬于同一連通分量每次選不屬于同一連通分量( (保證不產(chǎn)生回路保證不產(chǎn)生回路) )且權(quán)值最小的邊，加入且權(quán)值最小的邊，

29、加入MSTMST。并將所在的。并將所在的2 2個連通分個連通分量合并，直到只剩一個連通分量量合并，直到只剩一個連通分量時間復雜度時間復雜度O(elogeO(eloge) )KruskalKruskal算法最小生成樹的過程算法最小生成樹的過程7.5 有向無環(huán)圖及其應用v有向無環(huán)圖（有向無環(huán)圖（DAG)DAG) 不存在回路的有向圖不存在回路的有向圖vAOVAOV網(wǎng)網(wǎng)一個表示工程或系統(tǒng)的一個表示工程或系統(tǒng)的DAGDAG，用頂點表示活動，用頂點表示活動，用弧表示活動之間的優(yōu)先關(guān)系，稱為用弧表示活動之間的優(yōu)先關(guān)系，稱為AOVAOV網(wǎng)。網(wǎng)。vAOVAOV網(wǎng)的特點網(wǎng)的特點AOV網(wǎng)中的弧表示活動之間存在的某種

30、制約關(guān)系。網(wǎng)中的弧表示活動之間存在的某種制約關(guān)系。AOV網(wǎng)中不能出現(xiàn)回路網(wǎng)中不能出現(xiàn)回路 。7.5 有向無環(huán)圖及其應用vAOVAOV網(wǎng)舉例網(wǎng)舉例一個課程安排系統(tǒng)一個課程安排系統(tǒng)7.5 有向無環(huán)圖及其應用v拓撲排序拓撲排序 問題問題: : 1.1.假設(shè)以有向圖表示一個工程的施工圖或程序的數(shù)假設(shè)以有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。據(jù)流圖，則圖中不允許出現(xiàn)回路。 2. 2. 檢查有向圖中是否存在回路的方法之一，是對檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。有向圖進行拓撲排序。 7.5.1 拓撲排序何謂何謂“拓撲排序拓撲排序”？ 按照有向圖給出的次序關(guān)

31、系，將圖中頂點排成按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意的次序關(guān)系。頂點，則可以人為加上任意的次序關(guān)系。 AOV網(wǎng)拓撲排序7.5.1 7.5.1 拓撲排序拓撲排序v如何進行拓撲排序？如何進行拓撲排序？ 1.1.從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之; ; 2. 2.從有向圖中刪去該頂點出發(fā)的所有邊從有向圖中刪去該頂點出發(fā)的所有邊; ; 重復上述兩步，直至圖空，或者找不到無前驅(qū)重復上述兩步，直至圖空，或者找不到無前驅(qū)的頂點為止。的頂點為止

32、。7.5.1 拓撲排序拓撲排序v拓撲排序算法實現(xiàn)拓撲排序算法實現(xiàn) 1.1.從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之; ; 2. 2.從有向圖中刪去該頂點出發(fā)的所有邊從有向圖中刪去該頂點出發(fā)的所有邊; ; 重復上述兩步，直至圖空，或者找不到無前驅(qū)重復上述兩步，直至圖空，或者找不到無前驅(qū)的頂點為止。的頂點為止。入度為入度為0 0的頂點的頂點鄰接點的入度減鄰接點的入度減1degreefirstarcvexsdata7.5.1 拓撲排序拓撲排序v拓撲排序算法拓撲排序算法1.1.計算頂點的入度計算頂點的入度degree ;degree ;2.2.統(tǒng)計輸出的頂點

33、數(shù)統(tǒng)計輸出的頂點數(shù)count=0;count=0;3. 3. whilewhile（有入度為零的頂點）（有入度為零的頂點） 選一個入度為零的頂點選一個入度為零的頂點k;k; 輸出輸出k;k; 刪除頂點刪除頂點k;k; count+; count+; for (k for (k的所有鄰接點的所有鄰接點) ) 入度減入度減1 1； 4.if (count4.if (count頂點數(shù)頂點數(shù)) ) 存在環(huán)；存在環(huán)；時間復雜度為時間復雜度為 O(e+n)7.5.1 拓撲排序拓撲排序 Status Top-Sort(ALGraph G) /對圖對圖G G進行拓撲排序進行拓撲排序 FindInDegree(

34、G，indegree)； /計算頂點入度計算頂點入度indegree indegree count=0; /統(tǒng)計輸出的頂點統(tǒng)計輸出的頂點 for(i=0；iG.vexnum； +i) if (degreei=0) break; /選入度為零的頂點選入度為零的頂點 while (inext) k=p-vexs； /i/i的鄰接點的鄰接點k k -indegreek /入度減入度減1 1 if (countG.vexnum) return ERROR； /有回路有回路 else return OK； 7.5.1 拓撲排序拓撲排序v拓撲排序的用途拓撲排序的用途1.1.將有向無環(huán)圖中的頂點線性化將有向

35、無環(huán)圖中的頂點線性化2.2.檢測一個有向圖中是否存在環(huán)檢測一個有向圖中是否存在環(huán)7.5.2 關(guān)鍵路徑關(guān)鍵路徑v 問題問題: : 假設(shè)以有向網(wǎng)表示一個施工流圖（假設(shè)以有向網(wǎng)表示一個施工流圖（AOEAOE網(wǎng)），網(wǎng)）， 頂點表示事件，弧表示活動，弧上的權(quán)值表示完成頂點表示事件，弧表示活動，弧上的權(quán)值表示完成該項活動所需時間，該項活動所需時間， 問問: :1.1. 完成整個工程至少需要多少時間完成整個工程至少需要多少時間? ?2. 2. 為縮短完成工程所需的時間為縮短完成工程所需的時間, , 應當加快哪些活動應當加快哪些活動? ?7.5.2 關(guān)鍵路徑關(guān)鍵路徑v整個工程完成的時間整個工程完成的時間 從有

36、向圖的源點到匯點的最長路徑。從有向圖的源點到匯點的最長路徑。v 關(guān)鍵活動關(guān)鍵活動 最長路徑上的活動最長路徑上的活動 7.5.2 關(guān)鍵路徑關(guān)鍵路徑v如何求關(guān)鍵活動？如何求關(guān)鍵活動？ 活動的最早開始時間活動的最早開始時間 e e(i(i) ) 活動的最遲開始時間活動的最遲開始時間 l l(i(i) ) 關(guān)鍵活動為：關(guān)鍵活動為： e(ie(i)=l(i)=l(i)如：如：e(a4)=6, l(a4)=6e(a4)=6, l(a4)=6 e(a9)=7, l(a9)=6+3 e(a9)=7, l(a9)=6+3 jkai987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9

37、a8=7a10=2a11=47.5.2 關(guān)鍵路徑關(guān)鍵路徑v如何求關(guān)鍵活動（續(xù)如何求關(guān)鍵活動（續(xù)1）？）？計算各個活動的計算各個活動的e(i)與與 l(i)，以判別是否，以判別是否l(i)= e(i).為求為求e(i)與與l(i)，需要先求得各頂點最早發(fā)生時間，需要先求得各頂點最早發(fā)生時間Ve( ) 和最晚發(fā)生時間和最晚發(fā)生時間Vl( )顯然，顯然，e(i)=ve(j)；l(i)=vl(k)-dutai的權(quán)值的權(quán)值jkai7.5.2 關(guān)鍵路徑關(guān)鍵路徑v如何求關(guān)鍵活動（續(xù)如何求關(guān)鍵活動（續(xù)2）？）？ 如何計算如何計算veve( )( )和和 vlvl( )?( )? 從從Ve(0)=0開始向前遞推

38、開始向前遞推 ve(k) = Maxve(j) + dut() 從從Vl(n)=Ve(n)開始向后遞推開始向后遞推 vl(j) = Minvl(k) dut() jkjj. jkkk這兩個遞推公式必須分別在拓撲有序及拓撲逆序下進行。這兩個遞推公式必須分別在拓撲有序及拓撲逆序下進行。7.5.2 關(guān)鍵路徑關(guān)鍵路徑v求關(guān)鍵活動的實現(xiàn)要點求關(guān)鍵活動的實現(xiàn)要點按拓撲有序計算ve;按拓撲逆序計算vl;為求拓撲逆序序列，應在拓撲排序時，用 “棧棧”存儲拓撲有序序列。 7.6 最短路徑最短路徑v問題的提出問題的提出 要在計算機上建立一個交通咨詢系統(tǒng)（圖結(jié)構(gòu)）要在計算機上建立一個交通咨詢系統(tǒng)（圖結(jié)構(gòu)）頂點表示城

39、市頂點表示城市邊表示兩個城市的交通聯(lián)系邊表示兩個城市的交通聯(lián)系v最短路徑問題最短路徑問題 從一個頂點到達另一個頂點，從一個頂點到達另一個頂點，如何找到一條最短的路徑？如何找到一條最短的路徑？7.6 最短路徑最短路徑v問題解決問題解決單源點最短路徑問題單源點最短路徑問題 頂點對之間的最短路徑頂點對之間的最短路徑 Floyd Floyd算法算法7.6.1 單源點問題單源點問題v問題的提法問題的提法 從某一頂點出發(fā)，到其它各頂點的最短路徑從某一頂點出發(fā)，到其它各頂點的最短路徑7.6.1 單源點問題單源點問題vDijkstraDijkstra算法算法 按按路徑長度遞增路徑長度遞增的次序求從源點到其余各

40、點最的次序求從源點到其余各點最短路徑的算法短路徑的算法首先求出長度最短的一條最短路徑首先求出長度最短的一條最短路徑再參照它求出長度次短的一條最短路徑再參照它求出長度次短的一條最短路徑依次類推，直到從頂點依次類推，直到從頂點v v到其它各頂點的最短路徑全部求到其它各頂點的最短路徑全部求出為止出為止7.6.1 單源點問題單源點問題vDijkstraDijkstra算法算法 假設(shè)圖中所示為從源點到其余各點之間的最短路徑，假設(shè)圖中所示為從源點到其余各點之間的最短路徑，則在這些路徑中，必然存在一條長度最短者則在這些路徑中，必然存在一條長度最短者 在這條路徑上，必定只含一條權(quán)值最小弧。由此，只要在這條路徑

41、上，必定只含一條權(quán)值最小弧。由此，只要在所有從源點出發(fā)的弧中查找權(quán)值最小者在所有從源點出發(fā)的弧中查找權(quán)值最小者; ; 長度次短的路徑可能有兩種情況長度次短的路徑可能有兩種情況: : 它可能是從源點直接到該點的路徑它可能是從源點直接到該點的路徑; ; 也可能是，從源點到也可能是，從源點到a, a, 再從再從a a到該點到該點 其余依次類推其余依次類推源點源點a7.6.1 單源點問題單源點問題vDijkstraDijkstra算法的基本過程算法的基本過程1.1.初始時，初始時，S S只包含源點只包含源點v v。U U包含除包含除v v外的其他頂點。外的其他頂點。2.2.從從U U中選取一個距離中選

42、取一個距離v v最小的頂點最小的頂點k k，把，把k k加入加入S S中（該中（該選定的距離就是選定的距離就是v v到到k k的最短路徑長度）。的最短路徑長度）。3.3.以以k k為新考慮的中間點，修改為新考慮的中間點，修改U U中各頂點的距離中各頂點的距離: :若從若從源點源點v v到頂點到頂點u u（u u U U）的距離（經(jīng)過頂點）的距離（經(jīng)過頂點k k）比原來距）比原來距離（不經(jīng)過頂點離（不經(jīng)過頂點k k）短，則修改頂點）短，則修改頂點u u的距離值。的距離值。 重復步驟重復步驟2.2.和和3.3.直到所有頂點都包含在直到所有頂點都包含在S S中。中。路徑長度遞增的次序路徑長度遞增的次序7.6.1 單源點問題單源點問題vDijkstra算法的實現(xiàn)算法的實現(xiàn)引入一個輔助數(shù)組引入一個輔助數(shù)組distdist。它的每一個分量。它的每一個分量distidisti 表表示當前所確定的從源點示當前所確定的從源點v v0 0到終點到終點vivi 的最短路徑的長度的最短路徑的長度 顯然，顯然， DistiDisti = = 或者或者 = = + + 初始