圖的定義和術(shù)語(yǔ)

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

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

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

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

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

6、BFSTraverse(G, v, Visit(); / 從頂點(diǎn)v起廣度優(yōu)先遍歷圖245136 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)v圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示 用一個(gè)矩陣表示圖結(jié)構(gòu)用一個(gè)矩陣表示圖結(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對(duì)角線但是否則,或且如果7.2.1 圖數(shù)組表示法圖數(shù)組表示法v在有向圖中在有向圖中, , 統(tǒng)計(jì)第統(tǒng)計(jì)第 i i 行行 1

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

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

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

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

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

12、; / 對(duì)對(duì)v的尚未訪問的鄰接頂點(diǎn)的尚未訪問的鄰接頂點(diǎn)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; / 訪問標(biāo)志數(shù)組初始化訪問標(biāo)志數(shù)組初始化for (v=0; vvexnum; +v) / 從每個(gè)頂點(diǎn)出發(fā)調(diào)用從每個(gè)頂點(diǎn)出發(fā)調(diào)用DFS if (!visitedv) DFS (v, L);為不連通的圖也能訪問所有頂點(diǎn)，為不連通的圖也能訪問所有頂點(diǎn)，要從每個(gè)頂點(diǎn)出發(fā)，做深度優(yōu)先要從每個(gè)頂點(diǎn)出發(fā)，做深度優(yōu)先搜索，即調(diào)用搜索，即調(diào)用DFS(

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

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

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

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

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

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

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

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

21、發(fā)出發(fā)輔助數(shù)組closedge ：vPrim算法實(shí)現(xiàn)舉例(續(xù)1)選一個(gè)最小選一個(gè)最小權(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),并將頂并將頂點(diǎn)點(diǎn)5加入加入U(xiǎn)集合集合0,00,28 0, 0, 0, 0, 10 0, 0 1 2 3 4 5 60輔助數(shù)組closedge ：vPrim算法實(shí)現(xiàn)舉例(續(xù)2)05更新數(shù)據(jù)：存儲(chǔ)頂點(diǎn)更新數(shù)據(jù)：存儲(chǔ)頂點(diǎn)0和和5出發(fā)的邊中的小者出發(fā)的邊中的小者0,00,28 0, 0, 0, 0, 00, 0 1 2 3 4 5 65,2505vPrim算法實(shí)現(xiàn)舉例(續(xù)3

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

23、 3 4 5 6選一個(gè)最小的權(quán)值選一個(gè)最小的權(quán)值054vPrim算法實(shí)現(xiàn)舉例(續(xù)7)0,00,28 0, 4, 22 5, 00, 04, 24 0 1 2 3 4 5 6輸出邊輸出邊(4,3),并將并將頂點(diǎn)頂點(diǎn)3加入集合加入集合U0vPrim算法實(shí)現(xiàn)舉例(續(xù)8)05430,00,28 0, 4, 05, 00, 04, 24 0 1 2 3 4 5 6更新數(shù)據(jù)：增加頂點(diǎn)更新數(shù)據(jù)：增加頂點(diǎn)3出發(fā)的權(quán)值小的邊出發(fā)的權(quán)值小的邊3,123,180543vPrim算法實(shí)現(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算法實(shí)現(xiàn)舉例(續(xù)10)05430,00,28 3, 12 4, 05, 00, 03, 18 0 1 2 3 4 5 6輸出邊輸出邊(3,2),并將并將頂點(diǎn)頂點(diǎn)2加入集合加入集合U00543vPrim算法實(shí)現(xiàn)舉例(續(xù)11)2054320,00, 28 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6更新數(shù)據(jù)：增加頂點(diǎn)更新數(shù)據(jù)：增加頂點(diǎn)2出發(fā)的權(quán)值小的邊出發(fā)的權(quán)值小的邊2,16vPrim算法實(shí)現(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算法實(shí)現(xiàn)舉例(續(xù)13)0,02,

25、 16 3, 04, 05, 00, 03, 18 0 1 2 3 4 5 6輸出邊輸出邊(2,1),并將并將頂點(diǎn)頂點(diǎn)1加入集合加入集合U0vPrim算法實(shí)現(xiàn)舉例(續(xù)14)0543210,02, 03, 04, 05, 00, 03, 18 0 1 2 3 4 5 6更新數(shù)據(jù)：增加頂點(diǎn)更新數(shù)據(jù)：增加頂點(diǎn)1出發(fā)的權(quán)值小的邊出發(fā)的權(quán)值小的邊1,14054321vPrim算法實(shí)現(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算法實(shí)現(xiàn)舉例(續(xù)16)7.4.1

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

27、Vex ( G, u ); / / 頂點(diǎn)頂點(diǎn)u u為構(gòu)造生成樹的起始點(diǎn)為構(gòu)造生成樹的起始點(diǎn) 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) /在其余頂點(diǎn)中選擇在其余頂點(diǎn)中選擇 k = minimum(closedge); / / 選最小邊選最小邊 printf(closedgek.adjvex, G.vexsk); / / 輸出該邊輸出該邊 cl

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

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

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

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

32、。7.5.1 拓?fù)渑判蛲負(fù)渑判騰拓?fù)渑判蛩惴▽?shí)現(xiàn)拓?fù)渑判蛩惴▽?shí)現(xiàn) 1.1.從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出之從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出之; ; 2. 2.從有向圖中刪去該頂點(diǎn)出發(fā)的所有邊從有向圖中刪去該頂點(diǎn)出發(fā)的所有邊; ; 重復(fù)上述兩步，直至圖空，或者找不到無(wú)前驅(qū)重復(fù)上述兩步，直至圖空，或者找不到無(wú)前驅(qū)的頂點(diǎn)為止。的頂點(diǎn)為止。入度為入度為0 0的頂點(diǎn)的頂點(diǎn)鄰接點(diǎn)的入度減鄰接點(diǎn)的入度減1degreefirstarcvexsdata7.5.1 拓?fù)渑判蛲負(fù)渑判騰拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴?.1.計(jì)算頂點(diǎn)的入度計(jì)算頂點(diǎn)的入度degree ;degree ;2.2.統(tǒng)計(jì)輸出的頂點(diǎn)

33、數(shù)統(tǒng)計(jì)輸出的頂點(diǎn)數(shù)count=0;count=0;3. 3. whilewhile（有入度為零的頂點(diǎn)）（有入度為零的頂點(diǎn)） 選一個(gè)入度為零的頂點(diǎn)選一個(gè)入度為零的頂點(diǎn)k;k; 輸出輸出k;k; 刪除頂點(diǎn)刪除頂點(diǎn)k;k; count+; count+; for (k for (k的所有鄰接點(diǎn)的所有鄰接點(diǎn)) ) 入度減入度減1 1； 4.if (count4.if (count頂點(diǎn)數(shù)頂點(diǎn)數(shù)) ) 存在環(huán)；存在環(huán)；時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(e+n)7.5.1 拓?fù)渑判蛲負(fù)渑判?Status Top-Sort(ALGraph G) /對(duì)圖對(duì)圖G G進(jìn)行拓?fù)渑判蜻M(jìn)行拓?fù)渑判?FindInDegree(

34、G，indegree)； /計(jì)算頂點(diǎn)入度計(jì)算頂點(diǎn)入度indegree indegree count=0; /統(tǒng)計(jì)輸出的頂點(diǎn)統(tǒng)計(jì)輸出的頂點(diǎn) for(i=0；iG.vexnum； +i) if (degreei=0) break; /選入度為零的頂點(diǎn)選入度為零的頂點(diǎn) while (inext) k=p-vexs； /i/i的鄰接點(diǎn)的鄰接點(diǎn)k k -indegreek /入度減入度減1 1 if (countG.vexnum) return ERROR； /有回路有回路 else return OK； 7.5.1 拓?fù)渑判蛲負(fù)渑判騰拓?fù)渑判虻挠猛就負(fù)渑判虻挠猛?.1.將有向無(wú)環(huán)圖中的頂點(diǎn)線性化將有向

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

36、向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。v 關(guān)鍵活動(dòng)關(guān)鍵活動(dòng) 最長(zhǎng)路徑上的活動(dòng)最長(zhǎng)路徑上的活動(dòng) 7.5.2 關(guān)鍵路徑關(guān)鍵路徑v如何求關(guān)鍵活動(dòng)？如何求關(guān)鍵活動(dòng)？ 活動(dòng)的最早開始時(shí)間活動(dòng)的最早開始時(shí)間 e e(i(i) ) 活動(dòng)的最遲開始時(shí)間活動(dòng)的最遲開始時(shí)間 l l(i(i) ) 關(guān)鍵活動(dòng)為：關(guān)鍵活動(dòng)為： 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)鍵活動(dòng)（續(xù)如何求關(guān)鍵活動(dòng)（續(xù)1）？）？計(jì)算各個(gè)活動(dòng)的計(jì)算各個(gè)活動(dòng)的e(i)與與 l(i)，以判別是否，以判別是否l(i)= e(i).為求為求e(i)與與l(i)，需要先求得各頂點(diǎn)最早發(fā)生時(shí)間，需要先求得各頂點(diǎn)最早發(fā)生時(shí)間Ve( ) 和最晚發(fā)生時(shí)間和最晚發(fā)生時(shí)間Vl( )顯然，顯然，e(i)=ve(j)；l(i)=vl(k)-dutai的權(quán)值的權(quán)值jkai7.5.2 關(guān)鍵路徑關(guān)鍵路徑v如何求關(guān)鍵活動(dòng)（續(xù)如何求關(guān)鍵活動(dòng)（續(xù)2）？）？ 如何計(jì)算如何計(jì)算veve( )( )和和 vlvl( )?( )? 從從Ve(0)=0開始向前遞推

38、開始向前遞推 ve(k) = Maxve(j) + dut() 從從Vl(n)=Ve(n)開始向后遞推開始向后遞推 vl(j) = Minvl(k) dut() jkjj. jkkk這兩個(gè)遞推公式必須分別在拓?fù)溆行蚣巴負(fù)淠嫘蛳逻M(jìn)行。這兩個(gè)遞推公式必須分別在拓?fù)溆行蚣巴負(fù)淠嫘蛳逻M(jìn)行。7.5.2 關(guān)鍵路徑關(guān)鍵路徑v求關(guān)鍵活動(dòng)的實(shí)現(xiàn)要點(diǎn)求關(guān)鍵活動(dòng)的實(shí)現(xiàn)要點(diǎn)按拓?fù)溆行蛴?jì)算ve;按拓?fù)淠嫘蛴?jì)算vl;為求拓?fù)淠嫘蛐蛄?，?yīng)在拓?fù)渑判驎r(shí)，用 “棧?！贝鎯?chǔ)拓?fù)溆行蛐蛄小?7.6 最短路徑最短路徑v問題的提出問題的提出 要在計(jì)算機(jī)上建立一個(gè)交通咨詢系統(tǒng)（圖結(jié)構(gòu)）要在計(jì)算機(jī)上建立一個(gè)交通咨詢系統(tǒng)（圖結(jié)構(gòu)）頂點(diǎn)表示城

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

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

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

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