




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、 2021年10月16日 2021年10月16日 線性結(jié)構(gòu)一個(gè)對(duì)一個(gè),如線性表、棧、隊(duì)列樹形結(jié)構(gòu)一個(gè)對(duì)多個(gè),如樹集合數(shù)據(jù)元素間除“同屬于一個(gè)集合”外,無(wú)其它關(guān)系圖形結(jié)構(gòu)多個(gè)對(duì)多個(gè),如圖邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 2021年10月16日 第第6 6章圖章圖6.16.1圖的定義和基本術(shù)語(yǔ)圖的定義和基本術(shù)語(yǔ)6.26.2圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)6.36.3圖的遍歷圖的遍歷6.46.4圖的應(yīng)用圖的應(yīng)用教學(xué)內(nèi)容教學(xué)內(nèi)容 2021年10月16日 1.1.掌握:圖的基本掌握:圖的基本概念及相關(guān)術(shù)語(yǔ)和性質(zhì)概念及相關(guān)術(shù)語(yǔ)和性質(zhì)2.2.熟練掌握:圖的熟練掌握:圖的鄰接矩陣和鄰接表鄰接矩陣和鄰接表兩種存儲(chǔ)表示方法兩種存儲(chǔ)表示方
2、法3.3.熟練掌握:圖的兩種遍歷方法熟練掌握:圖的兩種遍歷方法DFSDFS和和BFSBFS4.4.熟練掌握:最短路算法(熟練掌握:最短路算法(DijkstraDijkstra算法算法)5.5.掌握:掌握:最小生成樹最小生成樹的兩種算法及的兩種算法及拓?fù)渑判蛲負(fù)渑判蛩惴ǖ乃枷胨惴ǖ乃枷虢虒W(xué)目標(biāo)教學(xué)目標(biāo) 2021年10月16日 6.1 6.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ)V1V2V3V4G1V1V2V4V5G2V3圖:圖:Graph=(V,E) V:頂點(diǎn):頂點(diǎn)(數(shù)據(jù)元素?cái)?shù)據(jù)元素)的的有窮非空有窮非空集合;集合; E:邊的:邊的有窮有窮集合。集合。無(wú)向圖:無(wú)向圖:有向圖:有向圖:每條邊都是無(wú)方向的每
3、條邊都是無(wú)方向的每條邊都是有方向的每條邊都是有方向的 2021年10月16日 完全圖:完全圖:任意兩個(gè)點(diǎn)都有一條邊相連任意兩個(gè)點(diǎn)都有一條邊相連無(wú)向完全圖無(wú)向完全圖有向完全圖有向完全圖 2021年10月16日 稀疏圖稀疏圖:有很少邊或弧的圖。:有很少邊或弧的圖。稠密圖稠密圖:有較多邊或弧的圖。:有較多邊或弧的圖。網(wǎng)網(wǎng):邊:邊/弧帶權(quán)的圖?;?quán)的圖。鄰接鄰接:有邊:有邊/弧相連的兩個(gè)頂點(diǎn)之間的關(guān)系?;∠噙B的兩個(gè)頂點(diǎn)之間的關(guān)系。 存在存在(vi, vj),則稱,則稱vi和和vj互為互為鄰接點(diǎn)鄰接點(diǎn); 存在存在,則稱,則稱vi鄰接到鄰接到vj, vj鄰接于鄰接于vi 關(guān)聯(lián)關(guān)聯(lián)(依附依附):邊邊/弧與
4、頂點(diǎn)之間的關(guān)系?;∨c頂點(diǎn)之間的關(guān)系。 存在存在(vi, vj)/ , 則稱該邊則稱該邊/弧關(guān)聯(lián)于弧關(guān)聯(lián)于vi和和vj 2021年10月16日 頂點(diǎn)的度頂點(diǎn)的度:與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目,記為:與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目,記為TD(v)在在有向圖有向圖中中, 頂點(diǎn)的度等于該頂點(diǎn)的頂點(diǎn)的度等于該頂點(diǎn)的入度入度與與出度出度之和。之和。頂點(diǎn)頂點(diǎn) v 的入度的入度是以是以 v 為終點(diǎn)的有向邊的條數(shù)為終點(diǎn)的有向邊的條數(shù), 記作記作 ID(v) 頂點(diǎn)頂點(diǎn) v 的出度的出度是以是以 v 為始點(diǎn)的有向邊的條數(shù)為始點(diǎn)的有向邊的條數(shù), 記作記作OD(v)問(wèn):?jiǎn)枺寒?dāng)有向圖中僅當(dāng)有向圖中僅1 1個(gè)頂點(diǎn)的入度為個(gè)頂點(diǎn)的入度
5、為0,0,其其余頂點(diǎn)的入度均為余頂點(diǎn)的入度均為1 1,此時(shí)是何形狀?,此時(shí)是何形狀?答:答:是樹!而且是一棵有向樹!是樹!而且是一棵有向樹! 2021年10月16日 路徑路徑:接續(xù)的邊構(gòu)成的頂點(diǎn)序列。:接續(xù)的邊構(gòu)成的頂點(diǎn)序列。路徑長(zhǎng)度路徑長(zhǎng)度:路徑上邊或弧的數(shù)目:路徑上邊或弧的數(shù)目/權(quán)值之和。權(quán)值之和。回路回路(環(huán)環(huán)):第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。簡(jiǎn)單路徑:簡(jiǎn)單路徑:除路徑起點(diǎn)和終點(diǎn)可以相同外,其余頂點(diǎn)均不相同除路徑起點(diǎn)和終點(diǎn)可以相同外,其余頂點(diǎn)均不相同的路徑。的路徑。簡(jiǎn)單回路簡(jiǎn)單回路(簡(jiǎn)單環(huán)簡(jiǎn)單環(huán)):除路徑起點(diǎn)和終點(diǎn)相同外,其余頂點(diǎn)均不除路徑起點(diǎn)和
6、終點(diǎn)相同外,其余頂點(diǎn)均不相同的路徑。相同的路徑。 2021年10月16日 非連通圖非連通圖 連通圖連通圖 強(qiáng)連通圖強(qiáng)連通圖 非強(qiáng)連通圖非強(qiáng)連通圖 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4在無(wú)(有)向圖在無(wú)(有)向圖G=( V, E )G=( V, E )中,若對(duì)任何兩個(gè)頂中,若對(duì)任何兩個(gè)頂點(diǎn)點(diǎn) v v、u u 都存在從都存在從v v 到到 u u 的路徑,則稱的路徑,則稱G G是連通圖是連通圖(強(qiáng)連通圖)。(強(qiáng)連通圖)。 2021年10月16日 (
7、a)(a)(b)(b)(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖G=G=(V V,EE)、)、G1=G1=(V1V1,E1E1),),若若V1V1 V V,E1 E1 E E,則稱,則稱 G1G1是是G G的子圖。的子圖。例例:(b):(b)、(c) (c) 是是 (a) (a) 的子圖的子圖圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個(gè)頂圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。帶權(quán)的圖稱為帶權(quán)的圖稱
8、為。 2021年10月16日 非連通圖非連通圖 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4無(wú)向圖無(wú)向圖G G 的極大連通子圖稱為的極大連通子圖稱為G G的連通分量。的連通分量。極大連通子圖意思是:該子圖是極大連通子圖意思是:該子圖是 G G 連通子圖,將連通子圖,將G G 的任何不在該子圖中的頂點(diǎn)加入,子圖不再連通。的任何不在該子圖中的頂點(diǎn)加入,子圖不再連通。 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4連通分量連通分量 2021年10月16日 有向圖有向圖G G 的極大強(qiáng)連通子圖稱為的極大強(qiáng)連通子圖稱為G G的強(qiáng)連通分量。的強(qiáng)連通分量。極大強(qiáng)連通子圖意思是:該子
9、圖是極大強(qiáng)連通子圖意思是:該子圖是G G的強(qiáng)連通子圖的強(qiáng)連通子圖,將,將D D的任何不在該子圖中的頂點(diǎn)加入,子圖不再的任何不在該子圖中的頂點(diǎn)加入,子圖不再是強(qiáng)連通的。是強(qiáng)連通的。強(qiáng)連通分量強(qiáng)連通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 2021年10月16日 :該子圖是:該子圖是G G 的連通子圖,在該子圖的連通子圖,在該子圖中刪除任何一條邊,子圖不再連通。中刪除任何一條邊,子圖不再連通。包含無(wú)向圖包含無(wú)向圖G G 所有頂點(diǎn)的極小連通子圖。所有頂點(diǎn)的極小連通子圖。對(duì)非連通圖,由各個(gè)連通分量的生成樹對(duì)非連通圖,由各個(gè)連通分量的生成樹的集合。的集合。 連
10、通圖連通圖 G1G1G1G1的生成樹的生成樹 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 2021年10月16日 6.2 6.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)鄰接表鄰接表鄰接多重表鄰接多重表十字鏈表十字鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu):數(shù)組表示法(鄰接矩陣)數(shù)組表示法(鄰接矩陣)多重鏈表多重鏈表重點(diǎn)介紹:重點(diǎn)介紹: 2021年10月16日 , ),( , , .否否則則或或者者如如果果01AEjiEjijiEdgev建立一個(gè)建立一個(gè)頂點(diǎn)表頂點(diǎn)表(記錄各個(gè)頂點(diǎn)信息)(記
11、錄各個(gè)頂點(diǎn)信息)和一個(gè)和一個(gè)鄰接矩鄰接矩陣陣(表示各個(gè)頂點(diǎn)之間關(guān)系)(表示各個(gè)頂點(diǎn)之間關(guān)系)。v設(shè)圖設(shè)圖 A = (A = (V V, , E E) ) 有有 n n 個(gè)頂點(diǎn),則圖的鄰接矩陣是個(gè)頂點(diǎn),則圖的鄰接矩陣是一個(gè)二維數(shù)組一個(gè)二維數(shù)組 A.EdgennA.Edgenn ,定義為:,定義為:數(shù)組(鄰接矩陣)表示法數(shù)組(鄰接矩陣)表示法 2021年10月16日 鄰接矩陣:A.Edge =( v1 v2 v3 v4 v5 )v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析分析1 1:無(wú)向圖的鄰接矩陣是無(wú)向圖的鄰接矩陣是對(duì)稱對(duì)稱的
12、;的;分析分析2 2:頂點(diǎn)頂點(diǎn)i i 的的度度第第 i i 行行 ( (列列) ) 中中1 1 的個(gè)數(shù)的個(gè)數(shù);特別:特別:完全圖完全圖的鄰接矩陣中,對(duì)角元素為的鄰接矩陣中,對(duì)角元素為0 0,其余,其余1 1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點(diǎn)表:無(wú)向圖的鄰接矩陣表示法無(wú)向圖的鄰接矩陣表示法v1v2v3v5v4v4 2021年10月16日 有向圖的鄰接矩陣有向圖的鄰接矩陣可能是不對(duì)稱可能是不對(duì)稱的。的。頂點(diǎn)的頂點(diǎn)的出度出度= =第第i i行元素之和
13、行元素之和 頂點(diǎn)的頂點(diǎn)的入度入度= =第第i i列元素之和列元素之和 頂點(diǎn)的頂點(diǎn)的度度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和 v1v2v3v4鄰接矩陣:A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注:注:在有向圖的鄰接矩陣中,在有向圖的鄰接矩陣中, 第第i i行含義:以結(jié)點(diǎn)行含義:以結(jié)點(diǎn)v vi i為尾的弧為尾的弧( (即出度邊);即出度邊); 第第i i列含義:以結(jié)點(diǎn)列含義:以結(jié)點(diǎn)v vi i為頭的弧為頭的弧( (即入度邊)。即入度邊)。頂點(diǎn)表:0 1 1 00 0 0 0 0
14、0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 有向圖的鄰接矩陣表示法有向圖的鄰接矩陣表示法 2021年10月16日 定義為:定義為: A.Edge i j =Wij 或(或(vi, vj)VR 無(wú)邊(?。o(wú)邊(?。﹙1v2v3v4Nv5v65489755613鄰接矩陣: N.Edge =( v1 v2 v3 v4 v5 v6 )頂點(diǎn)表: 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 網(wǎng)(即有權(quán)圖)的鄰接矩陣表示法網(wǎng)(即有權(quán)圖)的鄰接矩陣表示法 2021年10月16日 優(yōu)點(diǎn):優(yōu)點(diǎn):容易實(shí)現(xiàn)圖的操作,如:求某頂點(diǎn)的度、判
15、容易實(shí)現(xiàn)圖的操作,如:求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊、找頂點(diǎn)的鄰接點(diǎn)等等。斷頂點(diǎn)之間是否有邊、找頂點(diǎn)的鄰接點(diǎn)等等。缺點(diǎn):缺點(diǎn):n n個(gè)頂點(diǎn)需要個(gè)頂點(diǎn)需要n n* *n n個(gè)單元存儲(chǔ)邊個(gè)單元存儲(chǔ)邊; ;空間效率為空間效率為O(nO(n2 2) )。 對(duì)稀疏圖而言尤其浪費(fèi)空間。對(duì)稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣表示法的特點(diǎn)鄰接矩陣表示法的特點(diǎn) 2021年10月16日 /用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#define MaxInt 32767 /表示極大值,即表示極大值,即#define MVNum 100 /最大頂點(diǎn)數(shù)最大頂點(diǎn)數(shù) typedef char V
16、erTexType; /假設(shè)頂點(diǎn)的數(shù)據(jù)類型為字符型假設(shè)頂點(diǎn)的數(shù)據(jù)類型為字符型 typedef int ArcType; /假設(shè)邊的權(quán)值類型為整型假設(shè)邊的權(quán)值類型為整型 typedef struct VerTexType vexsMVNum; /頂點(diǎn)表頂點(diǎn)表 ArcType arcsMVNumMVNum; /鄰接矩陣鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前點(diǎn)數(shù)和邊數(shù)圖的當(dāng)前點(diǎn)數(shù)和邊數(shù) AMGraph; 鄰接矩陣的存儲(chǔ)表示鄰接矩陣的存儲(chǔ)表示 2021年10月16日 (1 1)輸入)輸入總頂點(diǎn)數(shù)和總邊數(shù)總頂點(diǎn)數(shù)和總邊數(shù)。(2 2)依次輸入)依次輸入點(diǎn)的信息存入頂點(diǎn)表點(diǎn)的信息存入頂點(diǎn)
17、表中。中。(3 3)初始化鄰接矩陣初始化鄰接矩陣,使每個(gè)權(quán)值初始化為極大值。,使每個(gè)權(quán)值初始化為極大值。(4 4)構(gòu)造鄰接矩陣構(gòu)造鄰接矩陣。 【算法思想算法思想】采用鄰接矩陣表示法創(chuàng)建無(wú)向網(wǎng)采用鄰接矩陣表示法創(chuàng)建無(wú)向網(wǎng) 2021年10月16日 Status CreateUDN(AMGraph &G) /采用鄰接矩陣表示法,創(chuàng)建無(wú)向網(wǎng)采用鄰接矩陣表示法,創(chuàng)建無(wú)向網(wǎng)G cinG.vexnumG.arcnum; /輸入總頂點(diǎn)數(shù),總邊數(shù)輸入總頂點(diǎn)數(shù),總邊數(shù) for(i = 0; iG.vexsi; /依次輸入點(diǎn)的信息依次輸入點(diǎn)的信息 for(i = 0; iG.vexnum;+i) /初始化鄰接矩陣,
18、邊的權(quán)值均置為極大值初始化鄰接矩陣,邊的權(quán)值均置為極大值 for(j = 0; jG.vexnum;+j) G.arcsij = MaxInt; for(k = 0; kv1v2w; /輸入一條邊依附的頂點(diǎn)及權(quán)值輸入一條邊依附的頂點(diǎn)及權(quán)值 i = LocateVex(G, v1); j = LocateVex(G, v2); /確定確定v1和和v2在在G中的位置中的位置 G.arcsij = w; /邊邊的權(quán)值置為的權(quán)值置為w G.arcsji = G.arcsij; /置置的對(duì)稱邊的對(duì)稱邊的權(quán)值為的權(quán)值為w /for return OK; /CreateUDN 【算法描述算法描述】 2021
19、年10月16日 int LocateVex(MGraph G,VertexType u) /* 初始條件初始條件:圖圖G存在存在,u和和G中頂點(diǎn)有相同特征中頂點(diǎn)有相同特征 */ /* 操作結(jié)果操作結(jié)果:若若G中存在頂點(diǎn)中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中則返回該頂點(diǎn)在圖中位置位置;否則返回否則返回-1 */ int i; for(i=0;iG.vexnum;+i) if(u=G.vexsi) return i; return -1; 2021年10月16日 v 對(duì)每個(gè)頂點(diǎn)對(duì)每個(gè)頂點(diǎn)vi 建立一個(gè)建立一個(gè)單鏈表單鏈表,把與,把與vi有關(guān)聯(lián)的有關(guān)聯(lián)的邊的信息鏈接邊的信息鏈接起來(lái),每個(gè)結(jié)點(diǎn)設(shè)為起來(lái),每個(gè)
20、結(jié)點(diǎn)設(shè)為3個(gè)域;個(gè)域;adjvex nextarcinfodatafirstarc鄰接點(diǎn)域鄰接點(diǎn)域,表表示示vi一個(gè)鄰接一個(gè)鄰接點(diǎn)的位置點(diǎn)的位置鏈域鏈域,指向指向vi下一個(gè)邊下一個(gè)邊或弧的結(jié)點(diǎn)或弧的結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)域,與與邊有關(guān)信息邊有關(guān)信息(如權(quán)值)(如權(quán)值)數(shù)據(jù)域數(shù)據(jù)域,存存儲(chǔ)頂點(diǎn)儲(chǔ)頂點(diǎn)vi 信信息息鏈域鏈域,指向,指向單鏈表的第單鏈表的第一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)鄰接表(鏈?zhǔn)剑┍硎痉ㄠ徑颖恚ㄦ準(zhǔn)剑┍硎痉?2021年10月16日 0123413341420注:注:鄰接表不唯一鄰接表不唯一,因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的,因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的v1v2v3v4v5231420無(wú)向圖的鄰接表表示無(wú)
21、向圖的鄰接表表示空間效率為空間效率為O(n+2e)O(n+2e)。若是稀疏圖若是稀疏圖(en(eG.vexnumG.arcnum; /輸入總頂點(diǎn)數(shù),總邊數(shù)輸入總頂點(diǎn)數(shù),總邊數(shù) for(i = 0; i G.verticesi.data; /輸入頂點(diǎn)值輸入頂點(diǎn)值 G.verticesi.firstarc=NULL; /初始化表頭結(jié)點(diǎn)的指針域?yàn)槌跏蓟眍^結(jié)點(diǎn)的指針域?yàn)镹ULL /for for(k = 0; kv1v2; /輸入一條邊依附的兩個(gè)頂點(diǎn)輸入一條邊依附的兩個(gè)頂點(diǎn) i = LocateVex(G, v1); j = LocateVex(G, v2); p1=new ArcNode; /生成
22、一個(gè)新的邊結(jié)點(diǎn)生成一個(gè)新的邊結(jié)點(diǎn)*p1 p1-adjvex=j; /鄰接點(diǎn)序號(hào)為鄰接點(diǎn)序號(hào)為j p1-nextarc= G.verticesi.firstarc; G.verticesi.firstarc=p1; /將新結(jié)點(diǎn)將新結(jié)點(diǎn)*p1插入頂點(diǎn)插入頂點(diǎn)vi的邊表頭部的邊表頭部 p2=new ArcNode; /生成另一個(gè)對(duì)稱的新的邊結(jié)點(diǎn)生成另一個(gè)對(duì)稱的新的邊結(jié)點(diǎn)*p2 p2-adjvex=i; /鄰接點(diǎn)序號(hào)為鄰接點(diǎn)序號(hào)為i p2-nextarc= G.verticesj.firstarc; G.verticesj.firstarc=p2; /將新結(jié)點(diǎn)將新結(jié)點(diǎn)*p2插入頂點(diǎn)插入頂點(diǎn)vj的邊表頭
23、部的邊表頭部 /for return OK; /CreateUDG 【算法描述算法描述】 2021年10月16日 優(yōu)點(diǎn):優(yōu)點(diǎn):空間效率高,容易尋找頂點(diǎn)的鄰接點(diǎn);空間效率高,容易尋找頂點(diǎn)的鄰接點(diǎn);缺點(diǎn):缺點(diǎn):判斷兩頂點(diǎn)間是否有邊或弧,需搜索兩結(jié)判斷兩頂點(diǎn)間是否有邊或弧,需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表,沒(méi)有鄰接矩陣方便。點(diǎn)對(duì)應(yīng)的單鏈表,沒(méi)有鄰接矩陣方便。鄰接表表示法的特點(diǎn)鄰接表表示法的特點(diǎn) 2021年10月16日 v1v2v3v5v4v44321013341420v5v4v3v2v1231420( v1 v2 v3 v4 v5 )v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 0
24、0 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0鄰接矩陣與鄰接表表示法的關(guān)系鄰接矩陣與鄰接表表示法的關(guān)系1. 1. 聯(lián)系:聯(lián)系:鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行,鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行,鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。 2021年10月16日 2. 2. 區(qū)別:區(qū)別: 對(duì)于任一確定的無(wú)向圖,鄰接矩陣是對(duì)于任一確定的無(wú)向圖,鄰接矩陣是唯一唯一的(行列的(行列號(hào)與
25、頂點(diǎn)編號(hào)一致),但鄰接表號(hào)與頂點(diǎn)編號(hào)一致),但鄰接表不唯一不唯一(鏈接次序(鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān))。與頂點(diǎn)編號(hào)無(wú)關(guān))。 鄰接矩陣的空間復(fù)雜度為鄰接矩陣的空間復(fù)雜度為O(nO(n2 2),),而鄰接表的空間復(fù)而鄰接表的空間復(fù)雜度為雜度為O(n+eO(n+e) )。3. 3. 用途:用途:鄰接矩陣多用于鄰接矩陣多用于稠密圖稠密圖;而鄰接表多用于;而鄰接表多用于稀稀疏圖疏圖鄰接矩陣與鄰接表表示法的關(guān)系鄰接矩陣與鄰接表表示法的關(guān)系 2021年10月16日 遍歷定義:遍歷定義:從已給的連通圖中某一頂點(diǎn)出發(fā),沿著一從已給的連通圖中某一頂點(diǎn)出發(fā),沿著一些邊訪遍圖中所有的頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪些邊訪遍圖中
26、所有的頂點(diǎn),且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次,就叫做問(wèn)一次,就叫做圖的圖的基本運(yùn)算基本運(yùn)算。遍歷實(shí)質(zhì):遍歷實(shí)質(zhì):找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程。找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程。圖的特點(diǎn):圖的特點(diǎn):圖中可能存在圖中可能存在回路回路,且圖的任一頂點(diǎn)都可,且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通,在訪問(wèn)完某個(gè)頂點(diǎn)之后可能能與其它頂點(diǎn)相通,在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)6.3 6.3 圖的遍歷圖的遍歷 2021年10月16日 圖常用的遍歷:圖常用的遍歷:深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索解決思路:解決思路:設(shè)置設(shè)置輔助數(shù)組輔助數(shù)組 visitedv
27、isited n n ,用來(lái)標(biāo)記每,用來(lái)標(biāo)記每個(gè)被訪問(wèn)過(guò)的頂點(diǎn)。個(gè)被訪問(wèn)過(guò)的頂點(diǎn)。初始狀態(tài)為初始狀態(tài)為0 0i i 被訪問(wèn),改被訪問(wèn),改 visitedvisited i i 為為1 1,防止被多次訪問(wèn),防止被多次訪問(wèn)怎樣避免重復(fù)訪問(wèn)?怎樣避免重復(fù)訪問(wèn)? 2021年10月16日 基本思想:基本思想:仿樹的先序遍歷過(guò)程。仿樹的先序遍歷過(guò)程。v1v2v3v8v7v6v4v5起點(diǎn)起點(diǎn)深度優(yōu)先搜索深度優(yōu)先搜索( DFS ( DFS Depth_FirstDepth_First Search) Search) 2021年10月16日 深度優(yōu)先搜索的步驟深度優(yōu)先搜索的步驟簡(jiǎn)單歸納:簡(jiǎn)單歸納: 訪問(wèn)起訪問(wèn)起
28、始點(diǎn)始點(diǎn)v v; ; 若若v v的的第第1 1個(gè)個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò),鄰接點(diǎn)沒(méi)訪問(wèn)過(guò),深度遍歷深度遍歷此鄰接此鄰接點(diǎn);點(diǎn); 若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò),再找若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò),再找v v的第的第2 2個(gè)鄰接點(diǎn)個(gè)鄰接點(diǎn)重新遍歷。重新遍歷。 2021年10月16日 深度優(yōu)先搜索的步驟深度優(yōu)先搜索的步驟詳細(xì)歸納:詳細(xì)歸納:E在訪問(wèn)圖中某一起始頂點(diǎn)在訪問(wèn)圖中某一起始頂點(diǎn) v 后,后,由由 v 出發(fā),訪問(wèn)出發(fā),訪問(wèn)它的任一鄰接頂它的任一鄰接頂點(diǎn)點(diǎn) w1;E再?gòu)脑購(gòu)?w1 出發(fā),訪問(wèn)出發(fā),訪問(wèn)與與 w1鄰接鄰接但還但還未被訪問(wèn)未被訪問(wèn)過(guò)的頂點(diǎn)過(guò)的頂點(diǎn) w2;E然后再?gòu)娜缓笤購(gòu)?w2 出發(fā),進(jìn)行類似的出發(fā),進(jìn)行類似
29、的訪問(wèn),訪問(wèn), E如此進(jìn)行下去,直至到達(dá)所有如此進(jìn)行下去,直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn) u 為止。為止。起點(diǎn)起點(diǎn) 2021年10月16日 深度優(yōu)先搜索的步驟深度優(yōu)先搜索的步驟詳細(xì)歸納:詳細(xì)歸納:E接著,退回一步,接著,退回一步,退到前一次退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)剛訪問(wèn)過(guò)的頂點(diǎn),看是否還有其,看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。 如果有,如果有,則訪問(wèn)此頂點(diǎn),之后則訪問(wèn)此頂點(diǎn),之后再?gòu)拇隧旤c(diǎn)出發(fā),進(jìn)行與前述類再?gòu)拇隧旤c(diǎn)出發(fā),進(jìn)行與前述類似的訪問(wèn);似的訪問(wèn); 如果沒(méi)有,如果沒(méi)有,就就再退回一步再退回一步進(jìn)行進(jìn)行搜索。重復(fù)上述過(guò)程,直到連通
30、搜索。重復(fù)上述過(guò)程,直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。起點(diǎn)起點(diǎn) 2021年10月16日 討論討論1 1:計(jì)算機(jī)如何實(shí)現(xiàn):計(jì)算機(jī)如何實(shí)現(xiàn)DFSDFS?1 2345610 000000 0000030 0000040 0000050 0000060 00000000000123456010000100001000010101鄰鄰接接矩矩陣陣A輔助數(shù)組輔助數(shù)組 visited n 起點(diǎn)起點(diǎn)開輔助數(shù)組開輔助數(shù)組 visited n !1 23 456100000 00300 00400 005000060 0000 2021年10月16日 void DFS(AMGraph
31、 G, int v) /圖圖G為鄰接矩陣類型為鄰接矩陣類型 coutv; visitedv = true; /訪問(wèn)第訪問(wèn)第v個(gè)頂點(diǎn)個(gè)頂點(diǎn) for(w = 0; w G.vexnum; w+) /依次檢查鄰接矩陣依次檢查鄰接矩陣v所在的行所在的行 if(G.arcsvw!=0)& (!visitedw) DFS(G, w); /w是是v的鄰接點(diǎn),如果的鄰接點(diǎn),如果w未訪問(wèn),則遞歸調(diào)用未訪問(wèn),則遞歸調(diào)用DFS 可以用遞歸算法!可以用遞歸算法! 2021年10月16日 00000123輔助數(shù)組輔助數(shù)組 visited n 1000110011101111照樣借用照樣借用visited n !起點(diǎn)起點(diǎn)
32、0123 2021年10月16日 void DFS(ALGraph G, int v) /圖圖G為鄰接表類型為鄰接表類型 coutadjvex; /表示表示w是是v的鄰接點(diǎn)的鄰接點(diǎn) if(!visitedw) DFS(G, w); /如果如果w未訪問(wèn),則遞歸調(diào)用未訪問(wèn),則遞歸調(diào)用DFS p=p-nextarc; /p指向下一個(gè)邊結(jié)點(diǎn)指向下一個(gè)邊結(jié)點(diǎn) 仍可用遞歸算法仍可用遞歸算法 2021年10月16日 n用用鄰接矩陣鄰接矩陣來(lái)表示圖,遍歷圖中每一個(gè)頂點(diǎn)都要來(lái)表示圖,遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描從頭掃描該頂點(diǎn)所在行,時(shí)間復(fù)雜度為該頂點(diǎn)所在行,時(shí)間復(fù)雜度為O(O(n n2 2) )。n用用鄰接表
33、鄰接表來(lái)表示圖,雖然有來(lái)表示圖,雖然有 2 2e e 個(gè)表結(jié)點(diǎn),但只個(gè)表結(jié)點(diǎn),但只需掃描需掃描 e e 個(gè)結(jié)點(diǎn)即可完成遍歷,加上訪問(wèn)個(gè)結(jié)點(diǎn)即可完成遍歷,加上訪問(wèn) n n個(gè)個(gè)頭結(jié)點(diǎn)的時(shí)間,時(shí)間復(fù)雜度為頭結(jié)點(diǎn)的時(shí)間,時(shí)間復(fù)雜度為O(O(n n+ +e e) )。結(jié)論:結(jié)論:稠密圖稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷;適于在鄰接矩陣上進(jìn)行深度遍歷;稀疏圖稀疏圖適于在鄰接表上進(jìn)行深度遍歷。適于在鄰接表上進(jìn)行深度遍歷。DFSDFS算法效率分析算法效率分析 2021年10月16日 基本思想:基本思想:仿樹的層次遍歷過(guò)程仿樹的層次遍歷過(guò)程廣度優(yōu)先搜索廣度優(yōu)先搜索( BFS ( BFS Breadth_Firs
34、tBreadth_First Search) Search)v1v2v3v8v7v6v4v5起點(diǎn)起點(diǎn) 2021年10月16日 簡(jiǎn)單歸納:簡(jiǎn)單歸納: 在訪問(wèn)了在訪問(wèn)了起始點(diǎn)起始點(diǎn)v v之后,依次訪問(wèn)之后,依次訪問(wèn) v v的鄰接點(diǎn)的鄰接點(diǎn); 然后再依次訪問(wèn)然后再依次訪問(wèn)這些頂點(diǎn)中未被訪問(wèn)過(guò)的鄰接點(diǎn)這些頂點(diǎn)中未被訪問(wèn)過(guò)的鄰接點(diǎn); 直到所有頂點(diǎn)都被訪問(wèn)直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。過(guò)為止。廣度優(yōu)先搜索是一種廣度優(yōu)先搜索是一種分層分層的搜索過(guò)程,每向前的搜索過(guò)程,每向前走一步可能訪問(wèn)一批頂點(diǎn),不像深度優(yōu)先搜索走一步可能訪問(wèn)一批頂點(diǎn),不像深度優(yōu)先搜索那樣有回退的情況。那樣有回退的情況。因此,廣度優(yōu)先搜索因此
35、,廣度優(yōu)先搜索不是一個(gè)遞歸不是一個(gè)遞歸的過(guò)程,其的過(guò)程,其算法也不是遞歸的。算法也不是遞歸的。廣度優(yōu)先搜索的步驟廣度優(yōu)先搜索的步驟 2021年10月16日 討論討論1 1:計(jì)算機(jī)如何實(shí)現(xiàn):計(jì)算機(jī)如何實(shí)現(xiàn)BFSBFS?鄰接表鄰接表除輔助數(shù)組除輔助數(shù)組visited n 外,外,還需再開一輔助隊(duì)列還需再開一輔助隊(duì)列起點(diǎn)起點(diǎn)輔助隊(duì)列輔助隊(duì)列v2已訪問(wèn)過(guò)了已訪問(wèn)過(guò)了BFS BFS 遍歷結(jié)果遍歷結(jié)果入隊(duì)!入隊(duì)!初始初始f=n-1,r=0f=n-1,r=0 2021年10月16日 (1 1)從圖中某個(gè)頂點(diǎn))從圖中某個(gè)頂點(diǎn)v v出發(fā),訪問(wèn)出發(fā),訪問(wèn)v v,并置,并置visitedvisitedv v 的值為
36、的值為truetrue,然后將,然后將v v進(jìn)隊(duì)。進(jìn)隊(duì)。(2 2)只要隊(duì)列不空,則重復(fù)下述處理。)只要隊(duì)列不空,則重復(fù)下述處理。 隊(duì)頭頂點(diǎn)隊(duì)頭頂點(diǎn)u u出隊(duì)。出隊(duì)。 依次檢查依次檢查u u的所有鄰接點(diǎn)的所有鄰接點(diǎn)w w,如果,如果visitedvisitedw w 的值為的值為falsefalse,則訪問(wèn),則訪問(wèn)w w,并置,并置visitedvisitedw w 的值為的值為truetrue,然后將,然后將w w進(jìn)隊(duì)。進(jìn)隊(duì)?!舅惴ㄋ枷胨惴ㄋ枷搿?2021年10月16日 void BFS (Graph G, int v) /按廣度優(yōu)先非遞歸遍歷連通圖按廣度優(yōu)先非遞歸遍歷連通圖G cout=0;
37、 w = NextAdjVex(G, u, w) if(!visitedw) /w為為u的尚未訪問(wèn)的鄰接頂點(diǎn)的尚未訪問(wèn)的鄰接頂點(diǎn) coutw; visitedw = true;EnQueue(Q, w); /w進(jìn)隊(duì)進(jìn)隊(duì) /if /while /BFS 【算法描述算法描述】 2021年10月16日 如果使用鄰接矩陣,則如果使用鄰接矩陣,則BFS對(duì)于每一個(gè)被訪問(wèn)到的頂點(diǎn)對(duì)于每一個(gè)被訪問(wèn)到的頂點(diǎn),都要循環(huán)檢測(cè)矩陣中的整整一行(,都要循環(huán)檢測(cè)矩陣中的整整一行( n 個(gè)元素),總個(gè)元素),總的時(shí)間代價(jià)為的時(shí)間代價(jià)為O(n2)。 用鄰接表來(lái)表示圖,雖然有用鄰接表來(lái)表示圖,雖然有 2e 個(gè)表結(jié)點(diǎn),但只需掃描
38、個(gè)表結(jié)點(diǎn),但只需掃描 e 個(gè)結(jié)點(diǎn)即可完成遍歷,加上訪問(wèn)個(gè)結(jié)點(diǎn)即可完成遍歷,加上訪問(wèn) n個(gè)頭結(jié)點(diǎn)的時(shí)間,個(gè)頭結(jié)點(diǎn)的時(shí)間,時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n+e)。BFSBFS算法效率分析算法效率分析 2021年10月16日 空間復(fù)雜度相同,都是空間復(fù)雜度相同,都是O(nO(n) )( (借用了堆棧或隊(duì)列);借用了堆?;蜿?duì)列); 時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)(鄰接矩陣或鄰接表)(鄰接矩陣或鄰接表)有關(guān),有關(guān),而與搜索路徑無(wú)關(guān)。而與搜索路徑無(wú)關(guān)。DFSDFS與與BFSBFS算法效率比較算法效率比較 2021年10月16日 最小生成樹最小生成樹最短路徑最短路徑拓?fù)渑判蛲負(fù)渑判蜿P(guān)鍵路徑關(guān)鍵路
39、徑6.4 6.4 圖的應(yīng)用圖的應(yīng)用 2021年10月16日 :該子圖是該子圖是G G 的連通子圖,在該子圖中刪的連通子圖,在該子圖中刪除任何一條邊,子圖不再連通。除任何一條邊,子圖不再連通。包含圖包含圖G G所有頂點(diǎn)的極小連通子圖(所有頂點(diǎn)的極小連通子圖(n-1條邊)條邊)。G1G1的生成樹的生成樹連通圖連通圖 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小生成樹最小生成樹 2021年10月16日 DFSDFS生生成成樹樹鄰鄰接接表表0123413341420v4v3v2v1v0
40、231420v0v2v1v4v3BFSBFS生生成成樹樹v0v1v3v2v4無(wú)向連通圖無(wú)向連通圖畫出下圖的生成樹畫出下圖的生成樹v0v1v2v4v4v3 2021年10月16日 求最小生成樹求最小生成樹首先明確首先明確: 使用不同的遍歷圖的方法,可以得到不同的生成樹使用不同的遍歷圖的方法,可以得到不同的生成樹 從不同的頂點(diǎn)出發(fā),也可能得到不同的生成樹。從不同的頂點(diǎn)出發(fā),也可能得到不同的生成樹。 按照生成樹的定義,按照生成樹的定義,n n 個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)連通網(wǎng)絡(luò)的生成樹的生成樹有有 n n 個(gè)頂點(diǎn)、個(gè)頂點(diǎn)、n-n-1 1 條邊。條邊。目標(biāo):目標(biāo):在網(wǎng)的多個(gè)生成樹中,尋找一個(gè)在網(wǎng)的多個(gè)生
41、成樹中,尋找一個(gè)各邊各邊權(quán)值之和最小權(quán)值之和最小的生成樹的生成樹 2021年10月16日 v必須只使用該必須只使用該網(wǎng)中的邊網(wǎng)中的邊來(lái)構(gòu)造最小生成樹;來(lái)構(gòu)造最小生成樹;v必須使用且僅使用必須使用且僅使用n-1n-1條邊條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n n個(gè)個(gè)頂點(diǎn)頂點(diǎn)v不能使用產(chǎn)生不能使用產(chǎn)生回路回路的邊的邊構(gòu)造最小生成樹的準(zhǔn)則構(gòu)造最小生成樹的準(zhǔn)則 2021年10月16日 欲在欲在n n個(gè)城市間建立通信網(wǎng),則個(gè)城市間建立通信網(wǎng),則n n個(gè)城市應(yīng)鋪個(gè)城市應(yīng)鋪n-1n-1條條線路;但因?yàn)槊織l線路都會(huì)有對(duì)應(yīng)的經(jīng)濟(jì)成本,而線路;但因?yàn)槊織l線路都會(huì)有對(duì)應(yīng)的經(jīng)濟(jì)成本,而n n個(gè)個(gè)城市可能有城市可能有n(n
42、-1)/2 n(n-1)/2 條線路,那么,條線路,那么,如何選擇如何選擇n n1 1條條線路,使總費(fèi)用最少?線路,使總費(fèi)用最少?數(shù)學(xué)模型:數(shù)學(xué)模型:頂點(diǎn)頂點(diǎn)表示城市,有表示城市,有n n個(gè);個(gè);邊邊表示線路,有表示線路,有n n1 1條;條;邊的權(quán)值邊的權(quán)值表示線路的經(jīng)濟(jì)代價(jià);表示線路的經(jīng)濟(jì)代價(jià);連通網(wǎng)連通網(wǎng)表示表示n n個(gè)城市間通信網(wǎng)。個(gè)城市間通信網(wǎng)。顯然此連通網(wǎng)顯然此連通網(wǎng)是一個(gè)是一個(gè)生成樹生成樹!最小生成樹的典型用途最小生成樹的典型用途 2021年10月16日 v PrimPrim(普里姆)算法(普里姆)算法 v KruskalKruskal(克魯斯卡爾)算法(克魯斯卡爾)算法Prim
43、ePrime算法算法: : 歸并頂點(diǎn)歸并頂點(diǎn),與邊數(shù)無(wú)關(guān),適于,與邊數(shù)無(wú)關(guān),適于稠密網(wǎng)稠密網(wǎng)Kruskal算法:算法:歸并邊歸并邊,適于,適于稀疏網(wǎng)稀疏網(wǎng)如何求最小生成樹如何求最小生成樹 2021年10月16日 設(shè)連通網(wǎng)絡(luò)設(shè)連通網(wǎng)絡(luò) N = V, E 生成樹的頂點(diǎn)集合生成樹的頂點(diǎn)集合UU普里姆算法的基本思想普里姆算法的基本思想歸并頂點(diǎn)歸并頂點(diǎn) 2021年10月16日 應(yīng)用普里姆算法構(gòu)造最小生成樹的過(guò)程應(yīng)用普里姆算法構(gòu)造最小生成樹的過(guò)程 2021年10月16日 設(shè)連通網(wǎng)絡(luò)設(shè)連通網(wǎng)絡(luò) N = V, E 1. 構(gòu)造一個(gè)只有構(gòu)造一個(gè)只有 n 個(gè)頂點(diǎn),沒(méi)有邊的非連通圖個(gè)頂點(diǎn),沒(méi)有邊的非連通圖 T = V
44、, , 每個(gè)頂點(diǎn)自成一個(gè)連通分量每個(gè)頂點(diǎn)自成一個(gè)連通分量 2. 在在 E 中選最小權(quán)值的邊中選最小權(quán)值的邊,若該邊的兩個(gè)頂點(diǎn)落若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上,則加入在不同的連通分量上,則加入 T 中;否則舍去中;否則舍去,重新選擇,重新選擇 3. 重復(fù)下去,直到所有頂點(diǎn)在同一連通分量上重復(fù)下去,直到所有頂點(diǎn)在同一連通分量上為止為止克魯斯卡爾算法的基本思想克魯斯卡爾算法的基本思想歸并邊歸并邊 2021年10月16日 應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過(guò)程應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過(guò)程 2021年10月16日 用有向圖來(lái)描述一個(gè)工程或系統(tǒng)的進(jìn)行過(guò)程。用有向圖來(lái)描述一個(gè)工程或系統(tǒng)的進(jìn)行
45、過(guò)程。一個(gè)工程可以分為若干個(gè)子工程,只要完成了這些子工程一個(gè)工程可以分為若干個(gè)子工程,只要完成了這些子工程(活動(dòng)),就可以導(dǎo)致整個(gè)工程的完成。(活動(dòng)),就可以導(dǎo)致整個(gè)工程的完成。 AOVAOV網(wǎng)網(wǎng)(Activity On Vertices)(Activity On Vertices)用用頂點(diǎn)頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)表示活動(dòng)的網(wǎng)絡(luò) AOEAOE網(wǎng)網(wǎng)(Activity On Edges)(Activity On Edges)用用邊邊表示活動(dòng)的網(wǎng)絡(luò)表示活動(dòng)的網(wǎng)絡(luò)比如教學(xué)計(jì)劃的制定比如教學(xué)計(jì)劃的制定哪些課程是必須先修的,哪些課程是可以并行學(xué)習(xí)的。哪些課程是必須先修的,哪些課程是可以并行學(xué)習(xí)的。有向無(wú)環(huán)圖及其
46、應(yīng)用有向無(wú)環(huán)圖及其應(yīng)用 2021年10月16日 2021年10月16日 學(xué)生課程學(xué)習(xí)工程圖學(xué)生課程學(xué)習(xí)工程圖 對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?,得到的拓?fù)溆行蛐蛄袨閷?duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)溆行蛐蛄袨镃1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 2021年10月16日 1.輸入輸入AOV網(wǎng)絡(luò)。令網(wǎng)絡(luò)。令 n 為頂點(diǎn)個(gè)數(shù)。為頂點(diǎn)個(gè)數(shù)。2. 在在AOV網(wǎng)絡(luò)中網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn)選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn), 并輸出之并輸出之; 3. 從圖中刪去該頂點(diǎn)從圖
47、中刪去該頂點(diǎn), 同時(shí)刪去所有它發(fā)出的有向邊同時(shí)刪去所有它發(fā)出的有向邊;4. 重復(fù)以上重復(fù)以上 2、3 步步, 直到:直到:u全部頂點(diǎn)均已輸出,拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛉宽旤c(diǎn)均已輸出,拓?fù)溆行蛐蛄行纬?,拓?fù)渑判蛲瓿?;或:完成;或:u圖中還有未輸出的頂點(diǎn),但已跳出處理循環(huán)。這說(shuō)圖中還有未輸出的頂點(diǎn),但已跳出處理循環(huán)。這說(shuō)明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū),再也明圖中還剩下一些頂點(diǎn),它們都有直接前驅(qū),再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存網(wǎng)絡(luò)中必定存在有向環(huán)。在有向環(huán)。拓?fù)渑判蛩惴ǖ乃枷胪負(fù)渑判蛩惴ǖ乃枷胫貜?fù)選擇沒(méi)有直接前驅(qū)的頂點(diǎn)重復(fù)選擇沒(méi)有直接前驅(qū)的
48、頂點(diǎn) 2021年10月16日 拓?fù)渑判虻倪^(guò)程拓?fù)渑判虻倪^(guò)程 2021年10月16日 2021年10月16日 典型用途:典型用途:交通問(wèn)題。如:城市交通問(wèn)題。如:城市A A到城市到城市B B有多條線路,有多條線路,但每條線路的交通費(fèi)(或所需時(shí)間)不同,那么,但每條線路的交通費(fèi)(或所需時(shí)間)不同,那么,如何如何選擇一條線路,使總費(fèi)用(或總時(shí)間)最少?選擇一條線路,使總費(fèi)用(或總時(shí)間)最少?問(wèn)題抽象:?jiǎn)栴}抽象:在在帶權(quán)有向圖帶權(quán)有向圖中中A A點(diǎn)(源點(diǎn))到達(dá)點(diǎn)(源點(diǎn))到達(dá)B B點(diǎn)(終點(diǎn))點(diǎn)(終點(diǎn))的多條路徑中,尋找一條的多條路徑中,尋找一條各邊權(quán)值之和最小各邊權(quán)值之和最小的路徑,即的路徑,即最短路徑
49、。最短路徑。(注:最短路徑與最小生成樹不同,路徑上(注:最短路徑與最小生成樹不同,路徑上不一定包含不一定包含n n個(gè)頂點(diǎn))個(gè)頂點(diǎn))最短路徑最短路徑 2021年10月16日 一頂點(diǎn)到其一頂點(diǎn)到其余各頂點(diǎn)余各頂點(diǎn)兩種常見的最短路徑問(wèn)題:兩種常見的最短路徑問(wèn)題:一、一、 單源最短路徑單源最短路徑用用Dijkstra(迪杰斯特拉)(迪杰斯特拉)算法算法二、所有頂點(diǎn)間的最短路徑二、所有頂點(diǎn)間的最短路徑用用Floyd(弗洛伊德)(弗洛伊德)算法算法任意兩頂任意兩頂點(diǎn)之間點(diǎn)之間 2021年10月16日 目的:目的: 設(shè)一設(shè)一有向圖有向圖G=G=(V, EV, E),已知各邊的權(quán)值,以某),已知各邊的權(quán)值,以
50、某指定點(diǎn)指定點(diǎn)v v0 0為源點(diǎn),求從為源點(diǎn),求從v v0 0到圖的其余各點(diǎn)的最短路徑。到圖的其余各點(diǎn)的最短路徑。限定限定各邊上的權(quán)值大于或等于各邊上的權(quán)值大于或等于0 0。源點(diǎn)源點(diǎn)從從FAFA的路徑有的路徑有4 4條:條: FAFA: 2424 FBA FBA: 5 518=2318=23 FBCA FBCA:5+7+9=215+7+9=21 FDCAFDCA:25+12+9=3625+12+9=36又:又:從從FBFB的最短路徑是哪條?的最短路徑是哪條?從從FCFC的最短路徑是哪條?的最短路徑是哪條?單源最短路徑問(wèn)題(單源最短路徑問(wèn)題(DijkstraDijkstra算法)算法) 2021
51、年10月16日 v0(v0, v1)10源點(diǎn)源點(diǎn)終點(diǎn)終點(diǎn) 最最 短短路路 徑徑路徑長(zhǎng)度路徑長(zhǎng)度(v0, v1, v2) (v0, v3, v2)(v0, v3)30 v1 v2 v3 v4100(v0, v4)(v0, v3, v4)(v0, v3, v2, v4) 6001234 5090 70討論:計(jì)算機(jī)如何自動(dòng)求出這些最短路徑?討論:計(jì)算機(jī)如何自動(dòng)求出這些最短路徑?(v0, v1, v2, v4)60 2021年10月16日 先找出從源點(diǎn)先找出從源點(diǎn)v v0 0到各終點(diǎn)到各終點(diǎn)v vk k的直達(dá)路徑(的直達(dá)路徑(v v0 0,v,vk k),即),即通過(guò)一條弧到達(dá)的路徑。通過(guò)一條弧到達(dá)的
52、路徑。從這些路徑中找出一條長(zhǎng)度最短的路徑(從這些路徑中找出一條長(zhǎng)度最短的路徑(v v0 0,u,u), ,然后然后對(duì)其余各條路徑進(jìn)行適當(dāng)調(diào)整:對(duì)其余各條路徑進(jìn)行適當(dāng)調(diào)整:若在圖中存在?。ㄈ粼趫D中存在?。╱,vu,vk k),且(),且(v v0 0,u,u)+ +(u,vu,vk k) (v v0 0,v,vk k), ,則以路徑(則以路徑(v v0 0,u,v,u,vk k)代替()代替(v v0 0,v,vk k)。)。在調(diào)整后的各條路徑中,再找長(zhǎng)度最短的路徑,依此在調(diào)整后的各條路徑中,再找長(zhǎng)度最短的路徑,依此類推。類推。DijkstraDijkstra算法的思想算法的思想 2021年10
53、月16日 初始化:初始化:將源點(diǎn)將源點(diǎn)v0加到加到S中,即中,即Sv0 = true;將將v0到各個(gè)終點(diǎn)的最短路徑長(zhǎng)度初始化為權(quán)值,到各個(gè)終點(diǎn)的最短路徑長(zhǎng)度初始化為權(quán)值,即即Di = G.arcsv0vi,(viV S);如果如果v0和頂點(diǎn)和頂點(diǎn)vi之間有弧,則將之間有弧,則將vi的前驅(qū)置為的前驅(qū)置為v0,即即Pathi = v0,否則,否則Pathi = 1。 選擇下一條最短路徑的終點(diǎn)選擇下一條最短路徑的終點(diǎn)vk,使得:,使得:Dk = MinDi|viV S【算法思想算法思想】 2021年10月16日 將將vk加到加到S中,即中,即Svk = true。 更新從更新從v0出發(fā)到集合出發(fā)到集
54、合V S上任一頂點(diǎn)的最短路徑的上任一頂點(diǎn)的最短路徑的長(zhǎng)度,同時(shí)更改長(zhǎng)度,同時(shí)更改vi的前驅(qū)為的前驅(qū)為vk。若若Dk+G.arcskiDi,則,則Di=Dk+ G.arcski; Path i=k;。 重復(fù)重復(fù) n 1次,即可按照路徑長(zhǎng)度的遞增順序次,即可按照路徑長(zhǎng)度的遞增順序,逐個(gè)求得從,逐個(gè)求得從v0到圖上其余各頂點(diǎn)的最短路徑。到圖上其余各頂點(diǎn)的最短路徑?!舅惴ㄋ枷胨惴ㄋ枷搿?2021年10月16日 初始化各類結(jié)構(gòu)(輔助結(jié)構(gòu))依次求V o 到V i的最短距離i= 1i n找V j, D j = m in D j V j加入S 中修改其它頂點(diǎn)的最短路徑i+ +結(jié)束 2021年10月16日 (v0,v2)+ (v2,v3)(v0,v3)終終點(diǎn)點(diǎn) 從從v0到各終點(diǎn)的到各
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 小學(xué)部編版語(yǔ)文六年級(jí)下冊(cè)第二單元《習(xí)作:寫作品梗概》說(shuō)課課件(含教學(xué)反思)
- 安全防護(hù)措施采購(gòu)合同
- 油漆涂料銷售合同
- 小學(xué)生欺凌預(yù)防:和諧校園氛圍與互助教育
- 手動(dòng)叉車安全使用
- 阿克蘇職業(yè)技術(shù)學(xué)院《平面形態(tài)設(shè)計(jì)》2023-2024學(xué)年第一學(xué)期期末試卷
- 阿壩職業(yè)學(xué)院《移動(dòng)設(shè)備開發(fā)》2023-2024學(xué)年第一學(xué)期期末試卷
- 隴東學(xué)院《跨境電商》2023-2024學(xué)年第二學(xué)期期末試卷
- 陜西中醫(yī)藥大學(xué)《數(shù)據(jù)與情報(bào)》2023-2024學(xué)年第二學(xué)期期末試卷
- 陜西國(guó)防工業(yè)職業(yè)技術(shù)學(xué)院《油畫寫實(shí)技法》2023-2024學(xué)年第二學(xué)期期末試卷
- 2024年工商聯(lián)副會(huì)長(zhǎng)述職報(bào)告
- 0-3歲嬰幼兒保育與教育智慧樹知到期末考試答案章節(jié)答案2024年甘肅財(cái)貿(mào)職業(yè)學(xué)院
- 洗煤廠洗煤技術(shù)人員題庫(kù)
- 開展志愿服務(wù)培養(yǎng)奉獻(xiàn)精神三篇
- 新制定《公平競(jìng)爭(zhēng)審查條例》學(xué)習(xí)課件
- 山在虛無(wú)縹緲間三部合唱譜
- 【公司招聘與選拔中存在的問(wèn)題與優(yōu)化建議探析2500字(論文)】
- 2024年高考語(yǔ)文閱讀之魯迅小說(shuō)專練(解析版)
- SL 288-2014 水利工程施工監(jiān)理規(guī)范
- 《土木工程材料》課件 03水泥-土木工程材料
- 5WHY分析法培訓(xùn)課件
評(píng)論
0/150
提交評(píng)論