數(shù)據(jù)結(jié)構(gòu)第6章圖

1、 2022年6月27日 2022年6月27日 線性結(jié)構(gòu)一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)一個對多個，如樹集合數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系圖形結(jié)構(gòu)多個對多個，如圖邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 2022年6月27日 第第6 6章圖章圖6.16.1圖的定義和基本術(shù)語圖的定義和基本術(shù)語6.26.2圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)6.36.3圖的遍歷圖的遍歷6.46.4圖的應(yīng)用圖的應(yīng)用教學(xué)內(nèi)容教學(xué)內(nèi)容 2022年6月27日 1.1.掌握：圖的基本掌握：圖的基本概念及相關(guān)術(shù)語和性質(zhì)概念及相關(guān)術(shù)語和性質(zhì)2.2.熟練掌握：圖的熟練掌握：圖的鄰接矩陣和鄰接表鄰接矩陣和鄰接表兩種存儲表示方法兩種存儲表示方法3.3

2、.熟練掌握：圖的兩種遍歷方法熟練掌握：圖的兩種遍歷方法DFSDFS和和BFSBFS4.4.熟練掌握：最短路算法（熟練掌握：最短路算法（DijkstraDijkstra算法算法）5.5.掌握：掌握：最小生成樹最小生成樹的兩種算法及的兩種算法及拓?fù)渑判蛲負(fù)渑判蛩惴ǖ乃枷胨惴ǖ乃枷虢虒W(xué)目標(biāo)教學(xué)目標(biāo) 2022年6月27日 6.1 6.1 圖的定義和術(shù)語圖的定義和術(shù)語V1V2V3V4G1V1V2V4V5G2V3圖：圖：Graph=(V,E) V：頂點：頂點(數(shù)據(jù)元素數(shù)據(jù)元素)的的有窮非空有窮非空集合；集合； E：邊的：邊的有窮有窮集合。集合。無向圖：無向圖：有向圖：有向圖：每條邊都是無方向的每條邊都是無

3、方向的每條邊都是有方向的每條邊都是有方向的 2022年6月27日 完全圖：完全圖：任意兩個點都有一條邊相連任意兩個點都有一條邊相連無向完全圖無向完全圖有向完全圖有向完全圖 2022年6月27日 稀疏圖稀疏圖：有很少邊或弧的圖。：有很少邊或弧的圖。稠密圖稠密圖：有較多邊或弧的圖。：有較多邊或弧的圖。網(wǎng)網(wǎng)：邊：邊/弧帶權(quán)的圖?；?quán)的圖。鄰接鄰接：有邊：有邊/弧相連的兩個頂點之間的關(guān)系?；∠噙B的兩個頂點之間的關(guān)系。 存在存在(vi, vj)，則稱，則稱vi和和vj互為互為鄰接點鄰接點； 存在存在，則稱，則稱vi鄰接到鄰接到vj， vj鄰接于鄰接于vi 關(guān)聯(lián)關(guān)聯(lián)(依附依附)：邊邊/弧與頂點之間的關(guān)系

4、。弧與頂點之間的關(guān)系。 存在存在(vi, vj)/ ， 則稱該邊則稱該邊/弧關(guān)聯(lián)于弧關(guān)聯(lián)于vi和和vj 2022年6月27日 頂點的度頂點的度：與該頂點相關(guān)聯(lián)的邊的數(shù)目，記為：與該頂點相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)在在有向圖有向圖中中, 頂點的度等于該頂點的頂點的度等于該頂點的入度入度與與出度出度之和。之和。頂點頂點 v 的入度的入度是以是以 v 為終點的有向邊的條數(shù)為終點的有向邊的條數(shù), 記作記作 ID(v) 頂點頂點 v 的出度的出度是以是以 v 為始點的有向邊的條數(shù)為始點的有向邊的條數(shù), 記作記作OD(v)問：問：當(dāng)有向圖中僅當(dāng)有向圖中僅1 1個頂點的入度為個頂點的入度為0,0,其其余

5、頂點的入度均為余頂點的入度均為1 1，此時是何形狀？，此時是何形狀？答：答：是樹！而且是一棵有向樹！是樹！而且是一棵有向樹！ 2022年6月27日 路徑路徑：接續(xù)的邊構(gòu)成的頂點序列。：接續(xù)的邊構(gòu)成的頂點序列。路徑長度路徑長度：路徑上邊或弧的數(shù)目：路徑上邊或弧的數(shù)目/權(quán)值之和。權(quán)值之和?；芈坊芈?環(huán)環(huán))：第一個頂點和最后一個頂點相同的路徑。第一個頂點和最后一個頂點相同的路徑。簡單路徑：簡單路徑：除路徑起點和終點可以相同外，其余頂點均不相同除路徑起點和終點可以相同外，其余頂點均不相同的路徑。的路徑。簡單回路簡單回路(簡單環(huán)簡單環(huán))：除路徑起點和終點相同外，其余頂點均不除路徑起點和終點相同外，其余頂

6、點均不相同的路徑。相同的路徑。 2022年6月27日 非連通圖非連通圖 連通圖連通圖 強(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在無（有）向圖在無（有）向圖G=( V, E )G=( V, E )中，若對任何兩個頂中，若對任何兩個頂點點 v v、u u 都存在從都存在從v v 到到 u u 的路徑，則稱的路徑，則稱G G是連通圖是連通圖（強(qiáng)連通圖）。（強(qiáng)連通圖）。 2022年6月27日 (a)(a)(b)(b)

7、(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2設(shè)有兩個圖設(shè)有兩個圖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)。表明從一個頂圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個頂點到另一個頂點的距離或耗費。點到另一個頂點的距離或耗費。帶權(quán)的圖稱為帶權(quán)的圖稱為。 2022年6月2

8、7日 非連通圖非連通圖 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4無向圖無向圖G G 的極大連通子圖稱為的極大連通子圖稱為G G的連通分量。的連通分量。極大連通子圖意思是：該子圖是極大連通子圖意思是：該子圖是 G G 連通子圖，將連通子圖，將G G 的任何不在該子圖中的頂點加入，子圖不再連通。的任何不在該子圖中的頂點加入，子圖不再連通。 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4連通分量連通分量 2022年6月27日 有向圖有向圖G G 的極大強(qiáng)連通子圖稱為的極大強(qiáng)連通子圖稱為G G的強(qiáng)連通分量。的強(qiáng)連通分量。極大強(qiáng)連通子圖意思是：該子圖是極大強(qiáng)連通子圖意思是：

9、該子圖是G G的強(qiáng)連通子圖的強(qiáng)連通子圖，將，將D D的任何不在該子圖中的頂點加入，子圖不再的任何不在該子圖中的頂點加入，子圖不再是強(qiáng)連通的。是強(qiáng)連通的。強(qiáng)連通分量強(qiáng)連通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 2022年6月27日 ：該子圖是：該子圖是G G 的連通子圖，在該子圖的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。中刪除任何一條邊，子圖不再連通。包含無向圖包含無向圖G G 所有頂點的極小連通子圖。所有頂點的極小連通子圖。對非連通圖，由各個連通分量的生成樹對非連通圖，由各個連通分量的生成樹的集合。的集合。 連通圖連通圖 G1G1G1G1

10、的生成樹的生成樹 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 2022年6月27日 6.2 6.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)鄰接表鄰接表鄰接多重表鄰接多重表十字鏈表十字鏈表鏈?zhǔn)酱鎯Y(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)：順序存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）數(shù)組表示法（鄰接矩陣）多重鏈表多重鏈表重點介紹：重點介紹： 2022年6月27日 , ),( , , .否否則則或或者者如如果果01AEjiEjijiEdgev建立一個建立一個頂點表頂點表（記錄各個頂點信息）（記錄各個頂點信息）和一個和一個鄰接

11、矩鄰接矩陣陣（表示各個頂點之間關(guān)系）（表示各個頂點之間關(guān)系）。v設(shè)圖設(shè)圖 A = (A = (V V, , E E) ) 有有 n n 個頂點，則圖的鄰接矩陣是個頂點，則圖的鄰接矩陣是一個二維數(shù)組一個二維數(shù)組 A.EdgennA.Edgenn，定義為：，定義為：數(shù)組（鄰接矩陣）表示法數(shù)組（鄰接矩陣）表示法 2022年6月27日 鄰接矩陣：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：無向圖的鄰接矩陣是無向圖的鄰接矩陣是對稱對稱的；的；分析分析2 2：頂點頂點i i

12、 的的度度第第 i i 行行 ( (列列) ) 中中1 1 的個數(shù)的個數(shù)；特別：特別：完全圖完全圖的鄰接矩陣中，對角元素為的鄰接矩陣中，對角元素為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頂點表：無向圖的鄰接矩陣表示法無向圖的鄰接矩陣表示法v1v2v3v5v4v4 2022年6月27日 有向圖的鄰接矩陣有向圖的鄰接矩陣可能是不對稱可能是不對稱的。的。頂點的頂點的出度出度= =第第i i行元素之和行元素之和 頂點的頂點的入度入度= =

13、第第i i列元素之和列元素之和 頂點的頂點的度度= =第第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é)點行含義：以結(jié)點v vi i為尾的弧為尾的弧( (即出度邊）；即出度邊）； 第第i i列含義：以結(jié)點列含義：以結(jié)點v vi i為頭的弧為頭的弧( (即入度邊）。即入度邊）。頂點表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1

14、 00 0 0 0 0 0 0 1 1 0 0 0 有向圖的鄰接矩陣表示法有向圖的鄰接矩陣表示法 2022年6月27日 定義為：定義為： A.Edge i j =Wij 或（或（vi, vj）VR 無邊（?。o邊（弧）v1v2v3v4Nv5v65489755613鄰接矩陣： N.Edge =( v1 v2 v3 v4 v5 v6 )頂點表： 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)圖）的鄰接矩陣表示法 2022年6月27日 優(yōu)點：優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂

15、點之間是否有邊、找頂點的鄰接點等等。斷頂點之間是否有邊、找頂點的鄰接點等等。缺點：缺點：n n個頂點需要個頂點需要n n* *n n個單元存儲邊個單元存儲邊; ;空間效率為空間效率為O(nO(n2 2) )。 對稀疏圖而言尤其浪費空間。對稀疏圖而言尤其浪費空間。鄰接矩陣表示法的特點鄰接矩陣表示法的特點 2022年6月27日 /用兩個數(shù)組分別存儲頂點表和鄰接矩陣用兩個數(shù)組分別存儲頂點表和鄰接矩陣#define MaxInt 32767 /表示極大值，即表示極大值，即#define MVNum 100 /最大頂點數(shù)最大頂點數(shù) typedef char VerTexType; /假設(shè)頂點的數(shù)據(jù)類型為

16、字符型假設(shè)頂點的數(shù)據(jù)類型為字符型 typedef int ArcType; /假設(shè)邊的權(quán)值類型為整型假設(shè)邊的權(quán)值類型為整型 typedef struct VerTexType vexsMVNum; /頂點表頂點表 ArcType arcsMVNumMVNum; /鄰接矩陣鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前點數(shù)和邊數(shù)圖的當(dāng)前點數(shù)和邊數(shù) AMGraph; 鄰接矩陣的存儲表示鄰接矩陣的存儲表示 2022年6月27日 （1 1）輸入）輸入總頂點數(shù)和總邊數(shù)總頂點數(shù)和總邊數(shù)。（2 2）依次輸入）依次輸入點的信息存入頂點表點的信息存入頂點表中。中。（3 3）初始化鄰接矩陣初始化鄰接矩

17、陣，使每個權(quán)值初始化為極大值。，使每個權(quán)值初始化為極大值。（4 4）構(gòu)造鄰接矩陣構(gòu)造鄰接矩陣。 【算法思想算法思想】采用鄰接矩陣表示法創(chuàng)建無向網(wǎng)采用鄰接矩陣表示法創(chuàng)建無向網(wǎng) 2022年6月27日 Status CreateUDN(AMGraph &G) /采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng)采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng)G cinG.vexnumG.arcnum; /輸入總頂點數(shù)，總邊數(shù)輸入總頂點數(shù)，總邊數(shù) for(i = 0; iG.vexsi; /依次輸入點的信息依次輸入點的信息 for(i = 0; iG.vexnum;+i) /初始化鄰接矩陣，邊的權(quán)值均置為極大值初始化鄰接矩陣，邊的權(quán)值均置

18、為極大值 for(j = 0; jG.vexnum;+j) G.arcsij = MaxInt; for(k = 0; kv1v2w; /輸入一條邊依附的頂點及權(quá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; /置置的對稱邊的對稱邊的權(quán)值為的權(quán)值為w /for return OK; /CreateUDN 【算法描述算法描述】 2022年6月27日 int LocateVex(MGr

19、aph G,VertexType u) /* 初始條件初始條件:圖圖G存在存在,u和和G中頂點有相同特征中頂點有相同特征 */ /* 操作結(jié)果操作結(jié)果:若若G中存在頂點中存在頂點u,則返回該頂點在圖中則返回該頂點在圖中位置位置;否則返回否則返回-1 */ int i; for(i=0;iG.vexnum;+i) if(u=G.vexsi) return i; return -1; 2022年6月27日 v 對每個頂點對每個頂點vi 建立一個建立一個單鏈表單鏈表，把與，把與vi有關(guān)聯(lián)的有關(guān)聯(lián)的邊的信息鏈接邊的信息鏈接起來，每個結(jié)點設(shè)為起來，每個結(jié)點設(shè)為3個域；個域；adjvex nextarci

20、nfodatafirstarc鄰接點域鄰接點域，表表示示vi一個鄰接一個鄰接點的位置點的位置鏈域鏈域，指向指向vi下一個邊下一個邊或弧的結(jié)點或弧的結(jié)點數(shù)據(jù)域數(shù)據(jù)域，與與邊有關(guān)信息邊有關(guān)信息（如權(quán)值）（如權(quán)值）數(shù)據(jù)域數(shù)據(jù)域，存存儲頂點儲頂點vi 信信息息鏈域鏈域，指向，指向單鏈表的第單鏈表的第一個結(jié)點一個結(jié)點鄰接表（鏈?zhǔn)剑┍硎痉ㄠ徑颖恚ㄦ準(zhǔn)剑┍硎痉?2022年6月27日 0123413341420注：注：鄰接表不唯一鄰接表不唯一，因各個邊結(jié)點的鏈入順序是任意的，因各個邊結(jié)點的鏈入順序是任意的v1v2v3v4v5231420無向圖的鄰接表表示無向圖的鄰接表表示空間效率為空間效率為O(n+2e)O(

21、n+2e)。若是稀疏圖若是稀疏圖(en(eG.vexnumG.arcnum; /輸入總頂點數(shù)，總邊數(shù)輸入總頂點數(shù)，總邊數(shù) for(i = 0; i G.verticesi.data; /輸入頂點值輸入頂點值 G.verticesi.firstarc=NULL; /初始化表頭結(jié)點的指針域為初始化表頭結(jié)點的指針域為NULL /for for(k = 0; kv1v2; /輸入一條邊依附的兩個頂點輸入一條邊依附的兩個頂點 i = LocateVex(G, v1); j = LocateVex(G, v2); p1=new ArcNode; /生成一個新的邊結(jié)點生成一個新的邊結(jié)點*p1 p1-adjv

22、ex=j; /鄰接點序號為鄰接點序號為j p1-nextarc= G.verticesi.firstarc; G.verticesi.firstarc=p1; /將新結(jié)點將新結(jié)點*p1插入頂點插入頂點vi的邊表頭部的邊表頭部 p2=new ArcNode; /生成另一個對稱的新的邊結(jié)點生成另一個對稱的新的邊結(jié)點*p2 p2-adjvex=i; /鄰接點序號為鄰接點序號為i p2-nextarc= G.verticesj.firstarc; G.verticesj.firstarc=p2; /將新結(jié)點將新結(jié)點*p2插入頂點插入頂點vj的邊表頭部的邊表頭部 /for return OK; /Cre

23、ateUDG 【算法描述算法描述】 2022年6月27日 優(yōu)點：優(yōu)點：空間效率高，容易尋找頂點的鄰接點；空間效率高，容易尋找頂點的鄰接點；缺點：缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。點對應(yīng)的單鏈表，沒有鄰接矩陣方便。鄰接表表示法的特點鄰接表表示法的特點 2022年6月27日 v1v2v3v5v4v44321013341420v5v4v3v2v1231420（ 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 00 1 0 1 01

24、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)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。 2022年6月27日 2. 2. 區(qū)別：區(qū)別： 對于任一確定的無向圖，鄰接矩陣是對于任一確定的無向圖，鄰接矩陣是唯一唯一的（行列的（行列號與頂點編號一致），但鄰接表號與頂點編號一致），但鄰接表不唯一不

25、唯一（鏈接次序（鏈接次序與頂點編號無關(guān)）。與頂點編號無關(guān)）。 鄰接矩陣的空間復(fù)雜度為鄰接矩陣的空間復(fù)雜度為O(nO(n2 2),),而鄰接表的空間復(fù)而鄰接表的空間復(fù)雜度為雜度為O(n+e)O(n+e)。3. 3. 用途：用途：鄰接矩陣多用于鄰接矩陣多用于稠密圖稠密圖；而鄰接表多用于；而鄰接表多用于稀稀疏圖疏圖鄰接矩陣與鄰接表表示法的關(guān)系鄰接矩陣與鄰接表表示法的關(guān)系 2022年6月27日 遍歷定義：遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做問一次，就叫做圖的圖

26、的基本運算基本運算。遍歷實質(zhì)：遍歷實質(zhì)：找每個頂點的鄰接點的過程。找每個頂點的鄰接點的過程。圖的特點：圖的特點：圖中可能存在圖中可能存在回路回路，且圖的任一頂點都可，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊會沿著某些邊又回到了曾經(jīng)訪問過的頂點又回到了曾經(jīng)訪問過的頂點6.3 6.3 圖的遍歷圖的遍歷 2022年6月27日 圖常用的遍歷：圖常用的遍歷：深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索解決思路：解決思路：設(shè)置設(shè)置輔助數(shù)組輔助數(shù)組 visitedvisited n n ，用來標(biāo)記每，用來標(biāo)記每個被訪問過的頂點。個

27、被訪問過的頂點。初始狀態(tài)為初始狀態(tài)為0 0i i 被訪問，改被訪問，改 visitedvisited i i 為為1 1，防止被多次訪問，防止被多次訪問怎樣避免重復(fù)訪問？怎樣避免重復(fù)訪問？ 2022年6月27日 基本思想：基本思想：仿樹的先序遍歷過程。仿樹的先序遍歷過程。v1v2v3v8v7v6v4v5起點起點深度優(yōu)先搜索深度優(yōu)先搜索( DFS ( DFS Depth_First Search)Depth_First Search) 2022年6月27日 深度優(yōu)先搜索的步驟深度優(yōu)先搜索的步驟簡單歸納：簡單歸納：訪問起訪問起始點始點v v; ;若若v v的的第第1 1個個鄰接點沒訪問過，鄰接點沒

28、訪問過，深度遍歷深度遍歷此鄰接此鄰接點；點；若當(dāng)前鄰接點已訪問過，再找若當(dāng)前鄰接點已訪問過，再找v v的第的第2 2個鄰接點個鄰接點重新遍歷。重新遍歷。 2022年6月27日 深度優(yōu)先搜索的步驟深度優(yōu)先搜索的步驟詳細(xì)歸納：詳細(xì)歸納：E在訪問圖中某一起始頂點在訪問圖中某一起始頂點 v 后，后，由由 v 出發(fā)，訪問出發(fā)，訪問它的任一鄰接頂它的任一鄰接頂點點 w1；E再從再從 w1 出發(fā)，訪問出發(fā)，訪問與與 w1鄰接鄰接但還但還未被訪問未被訪問過的頂點過的頂點 w2；E然后再從然后再從 w2 出發(fā)，進(jìn)行類似的出發(fā)，進(jìn)行類似的訪問，訪問， E如此進(jìn)行下去，直至到達(dá)所有如此進(jìn)行下去，直至到達(dá)所有的鄰接頂

29、點都被訪問過的頂點的鄰接頂點都被訪問過的頂點 u 為止。為止。起點起點 2022年6月27日 深度優(yōu)先搜索的步驟深度優(yōu)先搜索的步驟詳細(xì)歸納：詳細(xì)歸納：E接著，退回一步，接著，退回一步，退到前一次退到前一次剛訪問過的頂點剛訪問過的頂點，看是否還有其，看是否還有其它沒有被訪問的鄰接頂點。它沒有被訪問的鄰接頂點。 如果有，如果有，則訪問此頂點，之后則訪問此頂點，之后再從此頂點出發(fā)，進(jìn)行與前述類再從此頂點出發(fā)，進(jìn)行與前述類似的訪問；似的訪問； 如果沒有，如果沒有，就就再退回一步再退回一步進(jìn)行進(jìn)行搜索。重復(fù)上述過程，直到連通搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。圖中所有頂點都被訪問過為

30、止。起點起點 2022年6月27日 討論討論1 1：計算機(jī)如何實現(xiàn)：計算機(jī)如何實現(xiàn)DFSDFS？1 2345610 000000 0000030 0000040 0000050 0000060 00000000000123456010000100001000010101鄰鄰接接矩矩陣陣A輔助數(shù)組輔助數(shù)組 visited n 起點起點開輔助數(shù)組開輔助數(shù)組 visited n ！1 23 456100000 00300 00400 005000060 0000 2022年6月27日 void DFS(AMGraph G, int v) /圖圖G為鄰接矩陣類型為鄰接矩陣類型 coutv; visit

31、edv = true; /訪問第訪問第v個頂點個頂點 for(w = 0; w G.vexnum; w+) /依次檢查鄰接矩陣依次檢查鄰接矩陣v所在的行所在的行 if(G.arcsvw!=0)& (!visitedw) DFS(G, w); /w是是v的鄰接點，如果的鄰接點，如果w未訪問，則遞歸調(diào)用未訪問，則遞歸調(diào)用DFS 可以用遞歸算法！可以用遞歸算法！ 2022年6月27日 00000123輔助數(shù)組輔助數(shù)組 visited n 1000110011101111照樣借用照樣借用visited n ！起點起點0123 2022年6月27日 void DFS(ALGraph G, int v)

32、/圖圖G為鄰接表類型為鄰接表類型 coutadjvex; /表示表示w是是v的鄰接點的鄰接點 if(!visitedw) DFS(G, w); /如果如果w未訪問，則遞歸調(diào)用未訪問，則遞歸調(diào)用DFS p=p-nextarc; /p指向下一個邊結(jié)點指向下一個邊結(jié)點 仍可用遞歸算法仍可用遞歸算法 2022年6月27日 n用用鄰接矩陣鄰接矩陣來表示圖，遍歷圖中每一個頂點都要來表示圖，遍歷圖中每一個頂點都要從頭掃描從頭掃描該頂點所在行，時間復(fù)雜度為該頂點所在行，時間復(fù)雜度為O(O(n n2 2) )。n用用鄰接表鄰接表來表示圖，雖然有來表示圖，雖然有 2 2e e 個表結(jié)點，但只個表結(jié)點，但只需掃描需

33、掃描 e e 個結(jié)點即可完成遍歷，加上訪問個結(jié)點即可完成遍歷，加上訪問 n n個個頭結(jié)點的時間，時間復(fù)雜度為頭結(jié)點的時間，時間復(fù)雜度為O(O(n n+ +e e) )。結(jié)論：結(jié)論：稠密圖稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；適于在鄰接矩陣上進(jìn)行深度遍歷；稀疏圖稀疏圖適于在鄰接表上進(jìn)行深度遍歷。適于在鄰接表上進(jìn)行深度遍歷。DFSDFS算法效率分析算法效率分析 2022年6月27日 基本思想：基本思想：仿樹的層次遍歷過程仿樹的層次遍歷過程廣度優(yōu)先搜索廣度優(yōu)先搜索( BFS ( BFS Breadth_First Search)Breadth_First Search)v1v2v3v8v7v6v4v5

34、起點起點 2022年6月27日 簡單歸納：簡單歸納：在訪問了在訪問了起始點起始點v v之后，依次訪問之后，依次訪問 v v的鄰接點的鄰接點；然后再依次訪問然后再依次訪問這些頂點中未被訪問過的鄰接點這些頂點中未被訪問過的鄰接點；直到所有頂點都被訪問直到所有頂點都被訪問過為止。過為止。廣度優(yōu)先搜索是一種廣度優(yōu)先搜索是一種分層分層的搜索過程，每向前的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。那樣有回退的情況。因此，廣度優(yōu)先搜索因此，廣度優(yōu)先搜索不是一個遞歸不是一個遞歸的過程，其的過程，其算法也不是遞歸的。算法也不是遞歸的。廣度優(yōu)

35、先搜索的步驟廣度優(yōu)先搜索的步驟 2022年6月27日 討論討論1 1：計算機(jī)如何實現(xiàn)：計算機(jī)如何實現(xiàn)BFSBFS？鄰接表鄰接表除輔助數(shù)組除輔助數(shù)組visited n 外，外，還需再開一輔助隊列還需再開一輔助隊列起點起點輔助隊列輔助隊列v2已訪問過了已訪問過了BFS BFS 遍歷結(jié)果遍歷結(jié)果入隊！入隊！初始初始f=n-1,r=0f=n-1,r=0 2022年6月27日 （1 1）從圖中某個頂點）從圖中某個頂點v v出發(fā)，訪問出發(fā)，訪問v v，并置，并置visitedvisitedv v 的值為的值為truetrue，然后將，然后將v v進(jìn)隊。進(jìn)隊。（2 2）只要隊列不空，則重復(fù)下述處理。）只要隊

36、列不空，則重復(fù)下述處理。 隊頭頂點隊頭頂點u u出隊。出隊。 依次檢查依次檢查u u的所有鄰接點的所有鄰接點w w，如果，如果visitedvisitedw w 的值為的值為falsefalse，則訪問，則訪問w w，并置，并置visitedvisitedw w 的值為的值為truetrue，然后將，然后將w w進(jìn)隊。進(jìn)隊?！舅惴ㄋ枷胨惴ㄋ枷搿?2022年6月27日 void BFS (Graph G, int v) /按廣度優(yōu)先非遞歸遍歷連通圖按廣度優(yōu)先非遞歸遍歷連通圖G cout=0; w = NextAdjVex(G, u, w) if(!visitedw) /w為為u的尚未訪問的鄰接頂

37、點的尚未訪問的鄰接頂點 coutw; visitedw = true;EnQueue(Q, w); /w進(jìn)隊進(jìn)隊 /if /while /BFS 【算法描述算法描述】 2022年6月27日 如果使用鄰接矩陣，則如果使用鄰接矩陣，則BFS對于每一個被訪問到的頂點對于每一個被訪問到的頂點，都要循環(huán)檢測矩陣中的整整一行（，都要循環(huán)檢測矩陣中的整整一行（ n 個元素），總個元素），總的時間代價為的時間代價為O(n2)。 用鄰接表來表示圖，雖然有用鄰接表來表示圖，雖然有 2e 個表結(jié)點，但只需掃描個表結(jié)點，但只需掃描 e 個結(jié)點即可完成遍歷，加上訪問個結(jié)點即可完成遍歷，加上訪問 n個頭結(jié)點的時間，個頭結(jié)

38、點的時間，時間復(fù)雜度為時間復(fù)雜度為O(n+e)。BFSBFS算法效率分析算法效率分析 2022年6月27日 空間復(fù)雜度相同，都是空間復(fù)雜度相同，都是O(n)O(n)( (借用了堆?；蜿犃校唤栌昧硕褩；蜿犃校?時間復(fù)雜度只與存儲結(jié)構(gòu)時間復(fù)雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）（鄰接矩陣或鄰接表）有關(guān)，有關(guān)，而與搜索路徑無關(guān)。而與搜索路徑無關(guān)。DFSDFS與與BFSBFS算法效率比較算法效率比較 2022年6月27日 最小生成樹最小生成樹最短路徑最短路徑拓?fù)渑判蛲負(fù)渑判蜿P(guān)鍵路徑關(guān)鍵路徑6.4 6.4 圖的應(yīng)用圖的應(yīng)用 2022年6月27日 ：該子圖是該子圖是G G 的連通子圖，在該子圖中刪的連通

39、子圖，在該子圖中刪除任何一條邊，子圖不再連通。除任何一條邊，子圖不再連通。包含圖包含圖G G所有頂點的極小連通子圖（所有頂點的極小連通子圖（n-1條邊）條邊）。G1G1的生成樹的生成樹連通圖連通圖 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小生成樹最小生成樹 2022年6月27日 DFSDFS生生成成樹樹鄰鄰接接表表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFSBFS生生成成樹樹v0v1v3v2v4無向連通圖無向連通圖畫出下圖的生成樹畫出下

40、圖的生成樹v0v1v2v4v4v3 2022年6月27日 求最小生成樹求最小生成樹首先明確首先明確： 使用不同的遍歷圖的方法，可以得到不同的生成樹使用不同的遍歷圖的方法，可以得到不同的生成樹 從不同的頂點出發(fā)，也可能得到不同的生成樹。從不同的頂點出發(fā)，也可能得到不同的生成樹。 按照生成樹的定義，按照生成樹的定義，n n 個頂點的個頂點的連通網(wǎng)絡(luò)連通網(wǎng)絡(luò)的生成樹的生成樹有有 n n 個頂點、個頂點、n-n-1 1 條邊。條邊。目標(biāo)：目標(biāo)：在網(wǎng)的多個生成樹中，尋找一個在網(wǎng)的多個生成樹中，尋找一個各邊各邊權(quán)值之和最小權(quán)值之和最小的生成樹的生成樹 2022年6月27日 v必須只使用該必須只使用該網(wǎng)中的

41、邊網(wǎng)中的邊來構(gòu)造最小生成樹；來構(gòu)造最小生成樹；v必須使用且僅使用必須使用且僅使用n-1n-1條邊條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的來聯(lián)結(jié)網(wǎng)絡(luò)中的n n個個頂點頂點v不能使用產(chǎn)生不能使用產(chǎn)生回路回路的邊的邊構(gòu)造最小生成樹的準(zhǔn)則構(gòu)造最小生成樹的準(zhǔn)則 2022年6月27日 欲在欲在n n個城市間建立通信網(wǎng)，則個城市間建立通信網(wǎng)，則n n個城市應(yīng)鋪個城市應(yīng)鋪n-1n-1條條線路；但因為每條線路都會有對應(yīng)的經(jīng)濟(jì)成本，而線路；但因為每條線路都會有對應(yīng)的經(jīng)濟(jì)成本，而n n個個城市可能有城市可能有n(n-1)/2 n(n-1)/2 條線路，那么，條線路，那么，如何選擇如何選擇n n1 1條條線路，使總費用最少？線路，使總費用

42、最少？數(shù)學(xué)模型：數(shù)學(xué)模型：頂點頂點表示城市，有表示城市，有n n個；個；邊邊表示線路，有表示線路，有n n1 1條；條；邊的權(quán)值邊的權(quán)值表示線路的經(jīng)濟(jì)代價；表示線路的經(jīng)濟(jì)代價；連通網(wǎng)連通網(wǎng)表示表示n n個城市間通信網(wǎng)。個城市間通信網(wǎng)。顯然此連通網(wǎng)顯然此連通網(wǎng)是一個是一個生成樹生成樹！最小生成樹的典型用途最小生成樹的典型用途 2022年6月27日 v PrimPrim（普里姆）算法（普里姆）算法 v KruskalKruskal（克魯斯卡爾）算法（克魯斯卡爾）算法PrimePrime算法算法: : 歸并頂點歸并頂點，與邊數(shù)無關(guān)，適于，與邊數(shù)無關(guān)，適于稠密網(wǎng)稠密網(wǎng)Kruskal算法：算法：歸并邊歸

43、并邊，適于，適于稀疏網(wǎng)稀疏網(wǎng)如何求最小生成樹如何求最小生成樹 2022年6月27日 設(shè)連通網(wǎng)絡(luò)設(shè)連通網(wǎng)絡(luò) N = V, E 生成樹的頂點集合生成樹的頂點集合UU普里姆算法的基本思想普里姆算法的基本思想歸并頂點歸并頂點 2022年6月27日 應(yīng)用普里姆算法構(gòu)造最小生成樹的過程應(yīng)用普里姆算法構(gòu)造最小生成樹的過程 2022年6月27日 設(shè)連通網(wǎng)絡(luò)設(shè)連通網(wǎng)絡(luò) N = V, E 1. 構(gòu)造一個只有構(gòu)造一個只有 n 個頂點，沒有邊的非連通圖個頂點，沒有邊的非連通圖 T = V, , 每個頂點自成一個連通分量每個頂點自成一個連通分量 2. 在在 E 中選最小權(quán)值的邊中選最小權(quán)值的邊,若該邊的兩個頂點落若該邊

44、的兩個頂點落在不同的連通分量上，則加入在不同的連通分量上，則加入 T 中；否則舍去中；否則舍去，重新選擇，重新選擇 3. 重復(fù)下去，直到所有頂點在同一連通分量上重復(fù)下去，直到所有頂點在同一連通分量上為止為止克魯斯卡爾算法的基本思想克魯斯卡爾算法的基本思想歸并邊歸并邊 2022年6月27日 應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程 2022年6月27日 用有向圖來描述一個工程或系統(tǒng)的進(jìn)行過程。用有向圖來描述一個工程或系統(tǒng)的進(jìn)行過程。一個工程可以分為若干個子工程，只要完成了這些子工程一個工程可以分為若干個子工程，只要完成了這些子工程（活動），就可以導(dǎo)致整個工程的

45、完成。（活動），就可以導(dǎo)致整個工程的完成。 AOVAOV網(wǎng)網(wǎng)(Activity On Vertices)(Activity On Vertices)用用頂點頂點表示活動的網(wǎng)絡(luò)表示活動的網(wǎng)絡(luò) AOEAOE網(wǎng)網(wǎng)(Activity On Edges)(Activity On Edges)用用邊邊表示活動的網(wǎng)絡(luò)表示活動的網(wǎng)絡(luò)比如教學(xué)計劃的制定比如教學(xué)計劃的制定哪些課程是必須先修的，哪些課程是可以并行學(xué)習(xí)的。哪些課程是必須先修的，哪些課程是可以并行學(xué)習(xí)的。有向無環(huán)圖及其應(yīng)用有向無環(huán)圖及其應(yīng)用 2022年6月27日 2022年6月27日 學(xué)生課程學(xué)習(xí)工程圖學(xué)生課程學(xué)習(xí)工程圖 對學(xué)生選課工程圖進(jìn)行拓?fù)渑判颍?/p>

46、得到的拓?fù)溆行蛐蛄袨閷W(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到的拓?fù)溆行蛐蛄袨镃1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 2022年6月27日 輸入輸入AOV網(wǎng)絡(luò)。令網(wǎng)絡(luò)。令 n 為頂點個數(shù)。為頂點個數(shù)。 在在AOV網(wǎng)絡(luò)中網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點選一個沒有直接前驅(qū)的頂點, 并輸出之并輸出之; 從圖中刪去該頂點從圖中刪去該頂點, 同時刪去所有它發(fā)出的有向邊同時刪去所有它發(fā)出的有向邊; 重復(fù)以上重復(fù)以上 2、3 步步, 直到：直到：u全部頂點均已輸出，拓?fù)溆行蛐蛄行纬桑?/p>

47、拓?fù)渑判蛉宽旤c均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；或：完成；或：u圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。這時找不到?jīng)]有前驅(qū)的頂點了。這時AOV網(wǎng)絡(luò)中必定存網(wǎng)絡(luò)中必定存在有向環(huán)。在有向環(huán)。拓?fù)渑判蛩惴ǖ乃枷胪負(fù)渑判蛩惴ǖ乃枷胫貜?fù)選擇沒有直接前驅(qū)的頂點重復(fù)選擇沒有直接前驅(qū)的頂點 2022年6月27日 拓?fù)渑判虻倪^程拓?fù)渑判虻倪^程 2022年6月27日 2022年6月27日 典型用途：典型用途：交通問題。如：城市交通問題。如：城市A

48、 A到城市到城市B B有多條線路，有多條線路，但每條線路的交通費（或所需時間）不同，那么，但每條線路的交通費（或所需時間）不同，那么，如何如何選擇一條線路，使總費用（或總時間）最少？選擇一條線路，使總費用（或總時間）最少？問題抽象：問題抽象：在在帶權(quán)有向圖帶權(quán)有向圖中中A A點（源點）到達(dá)點（源點）到達(dá)B B點（終點）點（終點）的多條路徑中，尋找一條的多條路徑中，尋找一條各邊權(quán)值之和最小各邊權(quán)值之和最小的路徑，即的路徑，即最短路徑。最短路徑。（注：最短路徑與最小生成樹不同，路徑上（注：最短路徑與最小生成樹不同，路徑上不一定包含不一定包含n n個頂點）個頂點）最短路徑最短路徑 2022年6月27

49、日 一頂點到其一頂點到其余各頂點余各頂點兩種常見的最短路徑問題：兩種常見的最短路徑問題：一、一、 單源最短路徑單源最短路徑用用Dijkstra（迪杰斯特拉）（迪杰斯特拉）算法算法二、所有頂點間的最短路徑二、所有頂點間的最短路徑用用Floyd（弗洛伊德）算法（弗洛伊德）算法任意兩頂任意兩頂點之間點之間 2022年6月27日 目的：目的： 設(shè)一設(shè)一有向圖有向圖G=G=（V, EV, E），已知各邊的權(quán)值，以某），已知各邊的權(quán)值，以某指定點指定點v v0 0為源點，求從為源點，求從v v0 0到圖的其余各點的最短路徑。到圖的其余各點的最短路徑。限定限定各邊上的權(quán)值大于或等于各邊上的權(quán)值大于或等于0

50、0。源點源點從從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的最短路徑是哪條？的最短路徑是哪條？單源最短路徑問題（單源最短路徑問題（DijkstraDijkstra算法）算法） 2022年6月27日 v0(v0, v1)10源點源點終點終點 最最 短短路路 徑徑路徑長度路徑長度(v0, v1, v2) (v0, v3, v2)(v0, v3)30 v1

51、v2 v3 v4100(v0, v4)(v0, v3, v4)(v0, v3, v2, v4) 6001234 5090 70討論：計算機(jī)如何自動求出這些最短路徑？討論：計算機(jī)如何自動求出這些最短路徑？(v0, v1, v2, v4)60 2022年6月27日 先找出從源點先找出從源點v v0 0到各終點到各終點v vk k的直達(dá)路徑（的直達(dá)路徑（v v0 0,v,vk k），即），即通過一條弧到達(dá)的路徑。通過一條弧到達(dá)的路徑。從這些路徑中找出一條長度最短的路徑（從這些路徑中找出一條長度最短的路徑（v v0 0,u,u）, ,然后然后對其余各條路徑進(jìn)行適當(dāng)調(diào)整：對其余各條路徑進(jìn)行適當(dāng)調(diào)整：若在

52、圖中存在弧（若在圖中存在?。╱,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)整后的各條路徑中，再找長度最短的路徑，依此在調(diào)整后的各條路徑中，再找長度最短的路徑，依此類推。類推。DijkstraDijkstra算法的思想算法的思想 2022年6月27日 初始化：初始化：將源點將源點v0加到加到S中，即中，即Sv0 = true；將將v0到各個終點的最短路徑長度初始化為權(quán)值，到各個終點的最短路徑長度初始化為權(quán)值，即即D

53、i = G.arcsv0vi，(viV S)；如果如果v0和頂點和頂點vi之間有弧，則將之間有弧，則將vi的前驅(qū)置為的前驅(qū)置為v0，即即Pathi = v0，否則，否則Pathi = 1。 選擇下一條最短路徑的終點選擇下一條最短路徑的終點vk，使得：，使得：Dk = MinDi|viV S【算法思想算法思想】 2022年6月27日 將將vk加到加到S中，即中，即Svk = true。 更新從更新從v0出發(fā)到集合出發(fā)到集合V S上任一頂點的最短路徑的上任一頂點的最短路徑的長度，同時更改長度，同時更改vi的前驅(qū)為的前驅(qū)為vk。若若Dk+G.arcskiDi，則，則Di=Dk+ G.arcski; Path i=k;。 重復(fù)重復(fù) n 1次，即可按照路徑長度的遞增順序次，即可按照路徑長度的遞增順序，逐個求得從，逐個求得從v0到圖上其余各頂點的最短路徑。到圖上其余各頂點的最短路徑?！舅惴ㄋ枷胨惴ㄋ枷搿?2022年6月27日 初始化各類結(jié)構(gòu)（輔助結(jié)構(gòu)）依次求V o 到V i的最短距離i= 1i n找V j, D j = m in D j V j加入S 中修改其它頂點的最短路徑i+ +結(jié)束 2022年6月27日 (v0,v2)+ (v2,v3)(v0,v3)終終點點 從從v0到各終點的到各終點的di