第7章圖(5.11)

1、第第7章章 圖圖 第第7章章 圖圖 圖圖 7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu) 7.3 圖的遍歷圖的遍歷 7.4 圖的連通性問(wèn)題圖的連通性問(wèn)題 7.5 有向無(wú)環(huán)圖的應(yīng)用有向無(wú)環(huán)圖的應(yīng)用 7.6 最短路徑最短路徑 第第7章章 圖圖 1. 圖的定義G1=G1=V1=vV1=v0 0 ,v ,v1 1,v,v2 2,v,v3 3,v,v4 4 E1=(vE1=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v2 2,v,v3 3)(v)(v2 2,v,v4 4)

2、 圖圖G由兩個(gè)集合構(gòu)成，記作由兩個(gè)集合構(gòu)成，記作G= 其中其中: V（vertex）是頂點(diǎn)的非空有限集合）是頂點(diǎn)的非空有限集合 E（edge）是邊的有限集合，）是邊的有限集合， 而邊是頂點(diǎn)對(duì)而邊是頂點(diǎn)對(duì)的集合。的集合。 V0V0 V4V4 V3V3 V1V1 V2V27.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 例例1 1 交通圖（公路、鐵路）交通圖（公路、鐵路） 頂點(diǎn)頂點(diǎn)：地點(diǎn)：地點(diǎn) 邊邊：連接地點(diǎn)的公路：連接地點(diǎn)的公路 交通圖中的有單行道雙行道，分別用交通圖中的有單行道雙行道，分別用有向邊有向邊、無(wú)向邊無(wú)向邊表示；表示；例例2 2 電路圖電路圖 頂點(diǎn)頂點(diǎn)：元件：元件 邊邊

3、：連接元件之間的線(xiàn)路：連接元件之間的線(xiàn)路例例3 3 通訊線(xiàn)路圖通訊線(xiàn)路圖 頂點(diǎn)頂點(diǎn)：地點(diǎn)：地點(diǎn) 邊邊：地點(diǎn)間的連線(xiàn)：地點(diǎn)間的連線(xiàn)例例4 4 各種流程圖，如產(chǎn)品的生產(chǎn)流程圖各種流程圖，如產(chǎn)品的生產(chǎn)流程圖 頂點(diǎn)頂點(diǎn)：工序：工序 邊邊：各道工序之間的順序關(guān)系：各道工序之間的順序關(guān)系 圖的應(yīng)用舉例：7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 第第7章章 圖圖 例例5 田徑賽的時(shí)間安排問(wèn)題（圖的著色問(wèn)題）田徑賽的時(shí)間安排問(wèn)題（圖的著色問(wèn)題） ： 設(shè)設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽

4、日程表，有五人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。使得在盡可能短的時(shí)間內(nèi)完成比賽。姓 名項(xiàng) 目 1項(xiàng) 目 2項(xiàng) 目 3丁 一跳 高跳 遠(yuǎn)100 米馬 二標(biāo) 槍鉛 球張 三標(biāo) 搶100 米200 米李 四鉛 球200 米跳 高王 五跳 遠(yuǎn)200 米7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 （1）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目： 跳高跳高 跳遠(yuǎn)跳遠(yuǎn) 標(biāo)槍標(biāo)槍 鉛球鉛球 100米米 200米米 A B C D E F （2）用頂點(diǎn)代表比賽項(xiàng)目）用頂點(diǎn)代表比賽項(xiàng)目 不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一

5、條邊。不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。 （3）某選手比賽的項(xiàng)目必定有邊相連（不能同）某選手比賽的項(xiàng)目必定有邊相連（不能同時(shí)比賽）。時(shí)比賽）。 -田徑賽的時(shí)間安排問(wèn)題解法田徑賽的時(shí)間安排問(wèn)題解法7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 姓名項(xiàng)目1 項(xiàng)目2 項(xiàng)目3丁一 A B E馬二 C D 張三 C E F李四 D F A王五 B FAEBFDC比賽時(shí)間比賽項(xiàng)目1A，C2B，D3E4F田徑賽賽程安排問(wèn)題田徑賽賽程安排問(wèn)題圖的頂點(diǎn)著色問(wèn)題圖的頂點(diǎn)著色問(wèn)題 用用4種顏色即可為所有頂點(diǎn)著色，使種顏色即可為所有頂點(diǎn)著色，使得相鄰頂點(diǎn)不同色，即只需安排四個(gè)得相鄰頂點(diǎn)不同色，即只

6、需安排四個(gè)單位時(shí)間進(jìn)行比賽單位時(shí)間進(jìn)行比賽第第7章章 圖圖 鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)關(guān)聯(lián)邊：若邊關(guān)聯(lián)邊：若邊e= (v, u), e= (v, u), 則稱(chēng)頂點(diǎn)則稱(chēng)頂點(diǎn)v v、u u 關(guān)聯(lián)邊關(guān)聯(lián)邊頂點(diǎn)的度頂點(diǎn)的度 在無(wú)向圖中在無(wú)向圖中, ,頂點(diǎn)頂點(diǎn)V V的度的度 = = 與與V V相關(guān)聯(lián)的邊的數(shù)相關(guān)聯(lián)的邊的數(shù)目，記作目，記作TD(V)TD(V) 在有向圖中在有向圖中, ,頂點(diǎn)頂點(diǎn)V V的度的度= V= V的出度的出度+V+V的入度的入度 頂點(diǎn)頂點(diǎn)V V的出度的出度= =以以V V為起點(diǎn)有向邊數(shù)為起點(diǎn)有向邊數(shù) 頂點(diǎn)頂點(diǎn)V V的入度的入度= =以以V V為終點(diǎn)有向邊數(shù)為終點(diǎn)有向邊數(shù)

7、2. 圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第第7章章 圖圖 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3頂點(diǎn)頂點(diǎn)入度入度 出度出度度度V0123V1101V2112V3112頂點(diǎn)頂點(diǎn)度度V02V13V23V32V42頂點(diǎn)的度頂點(diǎn)的度7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 完全圖完全圖：無(wú)向完全圖：無(wú)向完全圖：任意兩頂點(diǎn)

8、間都有邊的圖。任意兩頂點(diǎn)間都有邊的圖。 在一個(gè)含有在一個(gè)含有n n個(gè)頂點(diǎn)的無(wú)向完全圖中，有個(gè)頂點(diǎn)的無(wú)向完全圖中，有n(n-1)/2n(n-1)/2條邊。條邊。有向完全圖有向完全圖:任意兩頂點(diǎn)之間都有方向互為相反的兩任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接的有向圖。條弧相連接的有向圖。 在一個(gè)含有在一個(gè)含有n n個(gè)頂點(diǎn)的有向完全圖中，有個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)n(n-1)條弧。條弧。2. 圖的基本術(shù)語(yǔ)圖的基本術(shù)語(yǔ)7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3路徑路徑GG中的中

9、的頂點(diǎn)序列頂點(diǎn)序列v v1 1,v,v2 2, , ,v ,vk k, ,若各邊若各邊(v(vi i,v,vi+1i+1) ) E, E, 則稱(chēng)該序列是從頂點(diǎn)則稱(chēng)該序列是從頂點(diǎn)v v1 1到頂點(diǎn)到頂點(diǎn)v vk k的路徑；的路徑；回路回路若路徑的頂點(diǎn)和終點(diǎn)相同，則稱(chēng)回路。若路徑的頂點(diǎn)和終點(diǎn)相同，則稱(chēng)回路。簡(jiǎn)單路徑簡(jiǎn)單路徑 在一條路徑中在一條路徑中,若除起點(diǎn)和終點(diǎn)外若除起點(diǎn)和終點(diǎn)外,所有頂點(diǎn)所有頂點(diǎn)各不相同各不相同,則該路徑為簡(jiǎn)單路徑；則該路徑為簡(jiǎn)單路徑；簡(jiǎn)單回路簡(jiǎn)單回路由簡(jiǎn)單路徑組成的回路稱(chēng)為簡(jiǎn)單回路；由簡(jiǎn)單路徑組成的回路稱(chēng)為簡(jiǎn)單回路；路徑和回路路徑和回路7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本

10、術(shù)語(yǔ) 第第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=（V，E）、）、G1=（V1，E1），若），若V1 V，E1 E，E1關(guān)聯(lián)的頂點(diǎn)都在關(guān)聯(lián)的頂點(diǎn)都在V1中，則稱(chēng)中，則稱(chēng) G1是是G的的子圖子圖； 例例 (b)、(c) 是是 (a) 的子圖的子圖子圖子圖7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 非連通圖非連通圖 連通圖連通圖 強(qiáng)連通圖強(qiáng)連通圖 非強(qiáng)連通圖非強(qiáng)連通圖 V0V0 V1V1 V2V

11、2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4 在無(wú)（有）向圖在無(wú)（有）向圖G=中，若中，若對(duì)任何兩個(gè)頂點(diǎn)對(duì)任何兩個(gè)頂點(diǎn) v、u 都存在從都存在從v 到到 u 的路徑的路徑，則稱(chēng)，則稱(chēng)G是是連通圖連通圖對(duì)有向圖而言，稱(chēng)對(duì)有向圖而言，稱(chēng)強(qiáng)連通圖強(qiáng)連通圖連通圖、強(qiáng)連通圖連通圖、強(qiáng)連通圖7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 連通分量連通分量非連通圖非連通圖 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4無(wú)向圖無(wú)向圖G 的極大連通子圖稱(chēng)為的極大連通子

12、圖稱(chēng)為G的連通分量的連通分量極大連通子圖極大連通子圖：該子圖是：該子圖是 G 連通子圖，將連通子圖，將G 的任何的任何不在該子圖中的頂點(diǎn)加入，子圖不再連通；不在該子圖中的頂點(diǎn)加入，子圖不再連通；7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 強(qiáng)連通分量強(qiáng)連通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 有向圖有向圖D 的極大強(qiáng)連通子圖稱(chēng)為的極大強(qiáng)連通子圖稱(chēng)為D 的強(qiáng)連通分量的強(qiáng)連通分量 極大強(qiáng)連通子圖極大強(qiáng)連通子圖：該子圖是：該子圖是D的強(qiáng)連通子圖，將的強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)的任何不在該子圖中的頂點(diǎn)加入

13、，子圖不再是強(qiáng)連通的；連通的；7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 連通圖連通圖 G1G1G1G1的生成樹(shù)的生成樹(shù) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2生成樹(shù)生成樹(shù) 包含無(wú)向圖包含無(wú)向圖G 所有頂點(diǎn)的的極小連通子圖稱(chēng)為所有頂點(diǎn)的的極小連通子圖稱(chēng)為G 的的生成樹(shù)生成樹(shù)。 極小連通子圖極小連通子圖：該子圖是：該子圖是G 的連通子圖，在該子圖中刪除任的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。何一條邊，子圖不再連通。 若若T是是G 的生成樹(shù)當(dāng)且僅當(dāng)?shù)纳蓸?shù)

14、當(dāng)且僅當(dāng)T 滿(mǎn)足如下條件：滿(mǎn)足如下條件： T是是G 的連通子圖的連通子圖 T包含包含G 的所有頂點(diǎn)的所有頂點(diǎn) T中無(wú)回路中無(wú)回路7.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ) 第第7章章 圖圖 邊的權(quán)：在圖的邊或弧上表示數(shù)字，表示與該邊邊的權(quán)：在圖的邊或弧上表示數(shù)字，表示與該邊相關(guān)的數(shù)據(jù)信息，這個(gè)數(shù)據(jù)信息就稱(chēng)該邊的權(quán)（相關(guān)的數(shù)據(jù)信息，這個(gè)數(shù)據(jù)信息就稱(chēng)該邊的權(quán)（weightweight）。）。 網(wǎng)（網(wǎng)（networknetwork）：邊（或?。┥蠋?quán)的圖稱(chēng)為網(wǎng)。）：邊（或?。┥蠋?quán)的圖稱(chēng)為網(wǎng)。 V0V0 V4V4 V3V3 V1V1 V2V28246537.1 圖的定義與基本術(shù)語(yǔ)圖的定義與基本術(shù)語(yǔ)

15、 第第7章章 圖圖 1設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（，則該圖最多有（ ）條邊。）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 EN22一個(gè)一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（ ）。）。An-1 Bn Cn+1 Dnlogn；3n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。An*n n（n） Cn2 Dn*（nl）4一個(gè)有一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（個(gè)結(jié)點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有）個(gè)連通分量，最多有（ ）個(gè)連通分量。）個(gè)連通分量。A0 B1 Cn-1 Dn5在一個(gè)無(wú)

16、向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（之和的（ ）倍。）倍。A1/2 B2 C1 D43.3.課堂練習(xí)課堂練習(xí)7.1 練習(xí)題練習(xí)題 第第7章章 圖圖 圖的存儲(chǔ)結(jié)構(gòu)要保存兩類(lèi)信息：圖的存儲(chǔ)結(jié)構(gòu)要保存兩類(lèi)信息：1)1)頂點(diǎn)的數(shù)據(jù)頂點(diǎn)的數(shù)據(jù)2)2)頂點(diǎn)間的關(guān)系頂點(diǎn)間的關(guān)系 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3鄰接矩陣表示法鄰接矩陣表示法鄰接表表示法鄰接表表示法V0V1V2V3V47

17、.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)第第7章章 圖圖 Aij=Aij=1 1 若若(v(vi i,v,vi+1i+1) ) E E 或或 v E E0 0 否則否則0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 圖圖G的鄰接矩陣是滿(mǎn)足如下條件：的鄰接矩陣是滿(mǎn)足如下條件：V0

18、V1 V2 V3 V4V0 V1 V2 V3鄰接矩陣鄰接矩陣第第7章章 圖圖 0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0鄰接矩陣表示法的空間代價(jià)鄰接矩陣表示法的空間代價(jià)只與圖的頂點(diǎn)數(shù)有關(guān)只與圖的頂點(diǎn)數(shù)有關(guān) V0V0 V4V4 V3V3 V1V1 V2V21）無(wú)向圖鄰接矩陣是）無(wú)向圖鄰接矩陣是對(duì)稱(chēng)矩陣對(duì)稱(chēng)矩陣，可考慮矩陣的壓縮存儲(chǔ)，可考慮矩陣的壓縮存儲(chǔ)2）G占用存儲(chǔ)空間只與它的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)；占用存儲(chǔ)空間只與它的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)； 適用于邊稠密的圖適

19、用于邊稠密的圖V0 V1 V2 V3 V4鄰接矩陣表示的特點(diǎn)鄰接矩陣表示的特點(diǎn)第第7章章 圖圖 鄰接矩陣下圖的有關(guān)操作鄰接矩陣下圖的有關(guān)操作1）求頂點(diǎn)）求頂點(diǎn)v的度：的度：2）判斷兩頂點(diǎn)是否鄰接：）判斷兩頂點(diǎn)是否鄰接：3）在圖中增加、刪除邊：）在圖中增加、刪除邊：4）檢測(cè)圖中的總邊數(shù)：）檢測(cè)圖中的總邊數(shù)： V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V30 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 00 1 1 00 1 1 0

20、0 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0V0 V1 V2 V3 V4V0 V1 V2 V3等于二維數(shù)組對(duì)應(yīng)行（或列）中等于二維數(shù)組對(duì)應(yīng)行（或列）中1的個(gè)數(shù)；的個(gè)數(shù)；只需判二維數(shù)組對(duì)應(yīng)分量是否為只需判二維數(shù)組對(duì)應(yīng)分量是否為1；只需對(duì)二維數(shù)組對(duì)應(yīng)分量賦值只需對(duì)二維數(shù)組對(duì)應(yīng)分量賦值1或清或清0；掃描整個(gè)數(shù)組掃描整個(gè)數(shù)組A，統(tǒng)計(jì)出數(shù)組中非，統(tǒng)計(jì)出數(shù)組中非0元素元素的個(gè)數(shù)。的個(gè)數(shù)。第第7章章 圖圖 鄰接矩陣的鄰接矩陣的C語(yǔ)言描述語(yǔ)言描述#define N 10 /*最多頂點(diǎn)數(shù)最多頂點(diǎn)數(shù)*/typedef char vextype; /*頂點(diǎn)類(lèi)型頂點(diǎn)類(lèi)型*/typ

21、edef sturct vextype vexsN; /*存頂點(diǎn)的數(shù)組存頂點(diǎn)的數(shù)組*/ adjtype edgeNN;/*存邊信息的矩陣存邊信息的矩陣*/ int n; /頂點(diǎn)數(shù)頂點(diǎn)數(shù) int e; /邊數(shù)邊數(shù)matrix_graph0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0 V0V0 V4V4 V3V3 V1V1 V2V2V0 V1 V2 V3 V4第第7章章 圖圖 建立無(wú)向圖的鄰接矩陣建立無(wú)向圖的鄰接矩陣 算法思想：算法思想：1）給存頂點(diǎn)的一維數(shù)組賦值；）給

22、存頂點(diǎn)的一維數(shù)組賦值；2）初始化存邊的二維數(shù)組；）初始化存邊的二維數(shù)組；3）依次讀入頂點(diǎn)對(duì)，給二維數(shù)組相關(guān)的元素）依次讀入頂點(diǎn)對(duì)，給二維數(shù)組相關(guān)的元素賦值。賦值。第第7章章 圖圖 V0V0 V4V4 V3V3 V1V1 V2V22 2 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 03 34 4下標(biāo)下標(biāo) 編號(hào)編號(hào) 指針指針鄰接表表示鄰接表表示1. 無(wú)向圖的鄰接表無(wú)向圖的鄰接表 頂點(diǎn)：通常按編號(hào)順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中；頂點(diǎn)：通常按編號(hào)順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中； 關(guān)聯(lián)同一頂點(diǎn)的邊：用關(guān)聯(lián)同

23、一頂點(diǎn)的邊：用線(xiàn)性鏈表線(xiàn)性鏈表存儲(chǔ)存儲(chǔ)表頭數(shù)據(jù)表頭數(shù)據(jù)指向鄰接表的指向鄰接表的指針指針鄰接結(jié)點(diǎn)鄰接結(jié)點(diǎn)數(shù)據(jù)數(shù)據(jù)指向下一鄰接指向下一鄰接點(diǎn)的指針點(diǎn)的指針第第7章章 圖圖 1 1）有向圖的鄰接表（出邊表）有向圖的鄰接表（出邊表）頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為以同一頂點(diǎn)為起點(diǎn)起點(diǎn)的?。河镁€(xiàn)性鏈表存儲(chǔ)的?。河镁€(xiàn)性鏈表存儲(chǔ)下標(biāo)下標(biāo) 編號(hào)編號(hào) 指針指針 V0V0V1V1V2V2V3V31 12 23 30 0 0 1 2 3m-1 V0V0 V1V1 V2V2 V3V3有向圖的鄰接表和逆鄰接表有向圖的鄰接表和逆鄰接表第第7章章 圖圖 2 2）有向圖的逆鄰接

24、表（入邊表）有向圖的逆鄰接表（入邊表）頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為以同一頂點(diǎn)為終點(diǎn)終點(diǎn)的?。河镁€(xiàn)性鏈表存儲(chǔ)的?。河镁€(xiàn)性鏈表存儲(chǔ)V0V0V1V1V2V2V3V3 0 1 2 3m-10 00 02 23 3 V0V0 V1V1 V2V2 V3V3有向圖的鄰接表和逆鄰接表有向圖的鄰接表和逆鄰接表第第7章章 圖圖 1）求頂點(diǎn)）求頂點(diǎn)v的度：的度：2）判斷兩頂點(diǎn)是否鄰接：）判斷兩頂點(diǎn)是否鄰接：3）在圖中增加、刪除邊：）在圖中增加、刪除邊：4）檢測(cè)圖中的總邊數(shù)：）檢測(cè)圖中的總邊數(shù)：鄰接表存儲(chǔ)下圖的有關(guān)操作鄰接表存儲(chǔ)下圖的有關(guān)操作等于等于v對(duì)應(yīng)線(xiàn)性鏈表的

25、長(zhǎng)度；對(duì)應(yīng)線(xiàn)性鏈表的長(zhǎng)度；要看要看v對(duì)應(yīng)線(xiàn)性鏈表中有無(wú)對(duì)應(yīng)結(jié)點(diǎn)對(duì)應(yīng)線(xiàn)性鏈表中有無(wú)對(duì)應(yīng)結(jié)點(diǎn)在相應(yīng)的頂點(diǎn)的鏈表中插入、刪在相應(yīng)的頂點(diǎn)的鏈表中插入、刪除結(jié)點(diǎn)除結(jié)點(diǎn)求每條線(xiàn)性鏈表的長(zhǎng)度和求每條線(xiàn)性鏈表的長(zhǎng)度和第第7章章 圖圖 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 04 43 3鄰接表的空間代價(jià)鄰接表的空間代價(jià)與圖的邊及頂點(diǎn)數(shù)均有關(guān)與圖的邊及頂點(diǎn)數(shù)均有關(guān) V0V0 V4V4 V3V3 V1V1 V2V22 2 1）在）在G鄰接表中，同一條邊對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)；鄰接表中，同一條邊對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)； 2）設(shè)存儲(chǔ)頂點(diǎn)

26、的一維數(shù)組大小為）設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為m(m 圖的頂點(diǎn)數(shù)圖的頂點(diǎn)數(shù)n), 圖的邊圖的邊數(shù)為數(shù)為e，G占用存儲(chǔ)空間為：占用存儲(chǔ)空間為：m+2*e。G占用存儲(chǔ)空間與占用存儲(chǔ)空間與 G 的的頂點(diǎn)數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖頂點(diǎn)數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖無(wú)向圖的鄰接表的特點(diǎn)無(wú)向圖的鄰接表的特點(diǎn)第第7章章 圖圖 typedef struct Arcnode /定義定義 邊結(jié)點(diǎn)的類(lèi)型邊結(jié)點(diǎn)的類(lèi)型 int adjver; /邊的鄰接點(diǎn)的數(shù)據(jù)邊的鄰接點(diǎn)的數(shù)據(jù) struct Arcnode *nextarc; /指向下一鄰接點(diǎn)的指針指向下一鄰接點(diǎn)的指針 Arcnode; typedef stru

27、ct VNode VertexType data; /頂點(diǎn)數(shù)據(jù)頂點(diǎn)數(shù)據(jù) ArcNode *firstarc; /指向該頂點(diǎn)第一條弧的指針指向該頂點(diǎn)第一條弧的指針*/ Vnode,AdjListMAX_VERTEX_NUM ; typedef struct AdjList vertices; int vexnum, arcnum; /圖的頂點(diǎn)數(shù)和弧數(shù)圖的頂點(diǎn)數(shù)和弧數(shù) int kind; /圖的種類(lèi)標(biāo)志圖的種類(lèi)標(biāo)志ALGraph; 鄰接表在鄰接表在C語(yǔ)言中的類(lèi)型定義語(yǔ)言中的類(lèi)型定義第第7章章 圖圖 建立無(wú)向圖的鄰接表建立無(wú)向圖的鄰接表 V0V0 V4V4 V3V3 V1V1 V2V2將圖轉(zhuǎn)換為線(xiàn)性

28、輸入信息：將圖轉(zhuǎn)換為線(xiàn)性輸入信息：頂點(diǎn)數(shù)為：頂點(diǎn)數(shù)為：n=5邊數(shù)為邊數(shù)為:e=6邊集：邊集：0 10 31 21 42 32 4第第7章章 圖圖 思想：如何給存儲(chǔ)結(jié)構(gòu)賦值思想：如何給存儲(chǔ)結(jié)構(gòu)賦值1. 建立頂點(diǎn)數(shù)組。讀入各頂點(diǎn)數(shù)據(jù)建立頂點(diǎn)數(shù)組。讀入各頂點(diǎn)數(shù)據(jù)data，將，將firstarc域賦域賦NULL。2. 建立各頂點(diǎn)的鄰接表。讀入頂點(diǎn)對(duì)建立各頂點(diǎn)的鄰接表。讀入頂點(diǎn)對(duì), 生成兩個(gè)結(jié)點(diǎn)，分生成兩個(gè)結(jié)點(diǎn)，分別插入頂點(diǎn)別插入頂點(diǎn)v, u的鄰接表的頭部。直至處理完所有的邊。的鄰接表的頭部。直至處理完所有的邊。 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V4

29、1 13 31 10 01 12 22 20 03 34 42 24 40 10 31 21 42 32 4建立無(wú)向圖的鄰接表建立無(wú)向圖的鄰接表第第7章章 圖圖 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 1加入邊加入邊(u, v): 設(shè)設(shè)u=0, v=10 0建立無(wú)向圖的鄰接表建立無(wú)向圖的鄰接表第第7章章 圖圖 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 10 0插入邊插入邊 (v0,v3):u=0,v=33 3建立無(wú)向圖的鄰接表建立無(wú)向圖的鄰接表第第7章章 圖圖 在不同的存儲(chǔ)結(jié)構(gòu)下，實(shí)現(xiàn)各種

30、操作的效率可能在不同的存儲(chǔ)結(jié)構(gòu)下，實(shí)現(xiàn)各種操作的效率可能是不同的。所以在求解實(shí)際問(wèn)題時(shí)，要根據(jù)求解問(wèn)題是不同的。所以在求解實(shí)際問(wèn)題時(shí)，要根據(jù)求解問(wèn)題所需操作，選擇合適的存儲(chǔ)結(jié)構(gòu)。所需操作，選擇合適的存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)的選擇存儲(chǔ)結(jié)構(gòu)的選擇第第7章章 圖圖 課堂練習(xí)課堂練習(xí)1、已知有向圖G，V（G）=1，2，3，4，E（G）=，試畫(huà)出G的鄰接矩陣，并說(shuō)明，若已知點(diǎn)i，如何根據(jù)鄰接矩陣找到與i相鄰的點(diǎn)j？ 2、已知無(wú)向圖G，V（G）=1，2，3，4，E（G）= （1，2），（1，3），（2，3），（2，4），（3，4）試畫(huà)出G的鄰接表，并說(shuō)明，若已知點(diǎn)i，如何根據(jù)鄰接表找到與i相鄰的點(diǎn)j第第7章章

31、圖圖 復(fù)習(xí)復(fù)習(xí)1、有頭結(jié)點(diǎn)的單鏈表4，2，6，5，3，1（1）單鏈表的建立（頭部插入新結(jié)點(diǎn)和尾部插入新結(jié)點(diǎn)兩種方法）（2）輸出并刪除第i個(gè)結(jié)點(diǎn)（3）在第i個(gè)位置插入新元素x (4) 對(duì)所有元素排序2、重做約瑟夫環(huán)猴子選猴王（無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表）第第7章章 圖圖 采用怎樣的策略進(jìn)行圖的遍歷采用怎樣的策略進(jìn)行圖的遍歷 有兩種遍歷方法有兩種遍歷方法： 深度優(yōu)先遍歷（深度優(yōu)先遍歷（DFSDFS：Depth First SearchDepth First Search） 廣度優(yōu)先遍歷（廣度優(yōu)先遍歷（BFSBFS：Breadth First SearchBreadth First Search）7.3圖的

32、遍歷圖的遍歷 圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問(wèn)圖中所有頂圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問(wèn)圖中所有頂點(diǎn)，并且每個(gè)頂點(diǎn)僅訪問(wèn)一次。點(diǎn)，并且每個(gè)頂點(diǎn)僅訪問(wèn)一次。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4第第7章章 圖圖 一一 、深度優(yōu)先遍歷（、深度優(yōu)先遍歷（DFS）1 1）從圖中某頂點(diǎn)）從圖中某頂點(diǎn)v v出發(fā)，訪問(wèn)頂點(diǎn)出發(fā)，訪問(wèn)頂點(diǎn)v v；2 2）依次從）依次從v v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷；遍歷； V0,V1,V3

33、,V7,V4,V2,V5,V6 V0,V1,V3,V7,V4,V2,V5,V6 由于沒(méi)有規(guī)定由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，訪問(wèn)鄰接點(diǎn)的順序，DFSDFS序列不唯一序列不唯一例例求圖求圖G G以以V0V0起點(diǎn)的深度優(yōu)先序列起點(diǎn)的深度優(yōu)先序列：V0,V1,V4,V7,V3,V2,V5,V6V0,V1,V4,V7,V3,V2,V5,V6 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V47.3.1 兩種遍歷思想兩種遍歷思想第第7章章 圖圖 圖中某未訪問(wèn)過(guò)的頂點(diǎn)圖中某未訪問(wèn)過(guò)的頂點(diǎn)vivi出發(fā)：

34、出發(fā)：1 1）訪問(wèn)頂點(diǎn)）訪問(wèn)頂點(diǎn)vi vi ；2 2）訪問(wèn)）訪問(wèn) vi vi 的所有未被訪問(wèn)的鄰接點(diǎn)的所有未被訪問(wèn)的鄰接點(diǎn)w w1 1 ,w ,w2 2 , , w wk k ；3 3）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn)）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn); ; 直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；二、廣度優(yōu)先遍歷（二、廣度優(yōu)先遍歷（BFSBFS） V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4由于沒(méi)有

35、規(guī)定由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序，訪問(wèn)鄰接點(diǎn)的順序，BFSBFS序列不唯一序列不唯一例例求圖求圖G G 的以的以V0V0起點(diǎn)的的廣度優(yōu)先序列起點(diǎn)的的廣度優(yōu)先序列: :V0,V1,V2,V3,V4,V5,V6,V7 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4第第7章章 圖圖 寫(xiě)出下圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列25476831( a )深度優(yōu)先：深度優(yōu)先：1 2 5 8 6 7 3 4深度優(yōu)先：深度優(yōu)先：1 3 5 8 6 7 3 4廣度優(yōu)先：廣度優(yōu)先：1 2 3 4 5

36、6 7 8小練習(xí)小練習(xí)第第7章章 圖圖 在圖中，訪問(wèn)部分頂點(diǎn)后，可能又沿著其他邊在圖中，訪問(wèn)部分頂點(diǎn)后，可能又沿著其他邊回到已被訪問(wèn)過(guò)的頂點(diǎn)。為保證每一個(gè)頂點(diǎn)只被訪回到已被訪問(wèn)過(guò)的頂點(diǎn)。為保證每一個(gè)頂點(diǎn)只被訪問(wèn)一次，必須對(duì)頂點(diǎn)進(jìn)行標(biāo)記，可用一個(gè)輔助數(shù)組問(wèn)一次，必須對(duì)頂點(diǎn)進(jìn)行標(biāo)記，可用一個(gè)輔助數(shù)組 visitedMAX作為對(duì)頂點(diǎn)的標(biāo)記。作為對(duì)頂點(diǎn)的標(biāo)記。7.3.2 圖的遍歷算法圖的遍歷算法輔助數(shù)組輔助數(shù)組 int visitedMAX; /頂點(diǎn)標(biāo)志數(shù)組頂點(diǎn)標(biāo)志數(shù)組,全局變量全局變量 若若visitedi=0，頂點(diǎn)，頂點(diǎn)vi未被訪問(wèn)未被訪問(wèn) 若若visitedi=1，當(dāng)，當(dāng)vi已被訪問(wèn)。已被訪問(wèn)。

37、visitvisit0 01 12 23 34 4m-1m-10 00 00 00 00 0第第7章章 圖圖 void DFSTraverse (Graph G,Status (*visit)(int v)/*對(duì)圖對(duì)圖G進(jìn)行深度優(yōu)先搜索，進(jìn)行深度優(yōu)先搜索，Graph 表示圖的一種存儲(chǔ)結(jié)構(gòu)表示圖的一種存儲(chǔ)結(jié)構(gòu)*/ VisitFunc = Visit; for (v=0; vG.vexnum; v+) visitedv=False ; /*訪問(wèn)標(biāo)志數(shù)組初訪問(wèn)標(biāo)志數(shù)組初始化始化*/ for( v=0; v=0; w=NextAdjVex(G, v, w) if(! visitedw) DFS(G,

38、w); /*遞歸調(diào)用遞歸調(diào)用DFS*/ /*DFS*/第第7章章 圖圖 遞歸過(guò)程分析遞歸過(guò)程分析 3 1 2 4 5 7 6 8 -無(wú)向圖無(wú)向圖 DFS(1)DFS(2)DFS(4)DFS(8)DFS(5)DFS(6)DFS(3)DFS(7)鄰接矩陣深度優(yōu)先搜索示意圖鄰接矩陣深度優(yōu)先搜索示意圖第第7章章 圖圖 基于鄰接表的基于鄰接表的DFS算法算法:DFSl() 核心問(wèn)題：如何在鄰接表中沿深度進(jìn)行遍歷 時(shí)間復(fù)雜度：O(n+e)第第7章章 圖圖 思想：思想：圖中某未訪問(wèn)過(guò)的頂點(diǎn)圖中某未訪問(wèn)過(guò)的頂點(diǎn)vi出發(fā)：出發(fā)：1）訪問(wèn)頂點(diǎn)）訪問(wèn)頂點(diǎn)vi ；2）訪問(wèn)）訪問(wèn) vi 的所有未被訪問(wèn)的鄰接點(diǎn)的所有未被

39、訪問(wèn)的鄰接點(diǎn)w1 ,w2 , wk ；3）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn)訪問(wèn)的鄰接點(diǎn); 依此類(lèi)推，直到圖中所有訪問(wèn)過(guò)依此類(lèi)推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；2.廣度優(yōu)先遍歷算法廣度優(yōu)先遍歷算法第第7章章 圖圖 問(wèn)題：如何保證鄰接點(diǎn)的訪問(wèn)順序？問(wèn)題：如何保證鄰接點(diǎn)的訪問(wèn)順序？25476831( a )要借助隊(duì)列：要借助隊(duì)列：訪問(wèn)順序：訪問(wèn)順序： 3 5 6 8 7輸出下圖從輸出下圖從1出發(fā)的廣度優(yōu)先遍歷序列出發(fā)的廣度優(yōu)先遍歷序列第第7章章 圖圖 解決：利用隊(duì)列解決：利用隊(duì)列1）從圖中某未訪問(wèn)過(guò)的頂

40、點(diǎn)）從圖中某未訪問(wèn)過(guò)的頂點(diǎn)vi出發(fā)：出發(fā)：2）訪問(wèn)頂點(diǎn)）訪問(wèn)頂點(diǎn)vi ；3）訪問(wèn)）訪問(wèn) vi 的所有未被訪問(wèn)的鄰接點(diǎn)的所有未被訪問(wèn)的鄰接點(diǎn)w1 ,w2 , wk ；4）將）將w1 ,w2 , wk 入隊(duì)；入隊(duì)；5）取隊(duì)頭頂點(diǎn)，從該頂點(diǎn)出發(fā)，訪問(wèn)它的所有）取隊(duì)頭頂點(diǎn)，從該頂點(diǎn)出發(fā)，訪問(wèn)它的所有未被訪問(wèn)的鄰接點(diǎn)；即重復(fù)未被訪問(wèn)的鄰接點(diǎn)；即重復(fù)25，直到圖中所，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)第第7章章 圖圖 BFS算法算法: /設(shè)從V0開(kāi)始； (1) 訪問(wèn)V0 (2)將V0加入隊(duì)列Q（3）當(dāng)隊(duì)列Q非空 (4) 取隊(duì)頭元素存入i (5) 對(duì)i的所有鄰接點(diǎn)j, 做

41、如下處理： 如果j 未被訪問(wèn)過(guò)，則訪問(wèn)j并讓j入隊(duì)列 第第7章章 圖圖 BFS算法算法:void BFSTraverse(Graph G, Statis (*Visit)(int v) for(v=0;vG.vexnum;+v) visitedv =FALSE; InitQueue(Q); /*初始化空隊(duì)*/ for(v = 0;v =0; w=NextAdjVex(G, u, w) if (!visitedw) Visit(w); visitedw=True; EnQueue(Q, w); /if /while /if /BFSTraverse第第7章章 圖圖 課堂練習(xí)課堂練習(xí)1無(wú)向圖無(wú)向圖

42、G=(V,E),其中：其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對(duì)該圖進(jìn)行，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（ ）。）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b第第7章章 圖圖 2、設(shè)下圖如右所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？（ ）a e b d f c a c f d e b a e d f c b a e f d c b a e f d b cA5個(gè) B4個(gè) C3個(gè) D2個(gè) a

43、bedcf第第7章章 圖圖 3 下面的鄰接表表示一個(gè)給定的無(wú)向圖 （1）給出從頂點(diǎn)v1開(kāi)始,對(duì)圖G用深度優(yōu)先搜索法進(jìn)行遍歷時(shí)的頂點(diǎn)序列；（2）給出從頂點(diǎn)v1開(kāi)始,對(duì)圖G用廣度優(yōu)先搜索法進(jìn)行遍歷時(shí)的頂點(diǎn)序列。第第7章章 圖圖 7.4 圖的連通性問(wèn)題圖的連通性問(wèn)題7.4.1 無(wú)向圖的連通分量無(wú)向圖的連通分量 對(duì)于連通圖，無(wú)論是廣度優(yōu)先搜索還是深度優(yōu)先搜對(duì)于連通圖，無(wú)論是廣度優(yōu)先搜索還是深度優(yōu)先搜索，僅需要調(diào)用索，僅需要調(diào)用一次一次搜索過(guò)程，便可以遍歷圖中的各搜索過(guò)程，便可以遍歷圖中的各個(gè)頂點(diǎn)。個(gè)頂點(diǎn)。 對(duì)于非連通圖，則需要對(duì)于非連通圖，則需要多次多次調(diào)用搜索過(guò)程，而每次調(diào)用搜索過(guò)程，而每次調(diào)用得到

44、的頂點(diǎn)訪問(wèn)序列恰為各連通分量中的頂點(diǎn)集。調(diào)用得到的頂點(diǎn)訪問(wèn)序列恰為各連通分量中的頂點(diǎn)集。第第7章章 圖圖 圖圖7.17 圖及其連通分量圖及其連通分量 15671082349123456789102112655102834437499(a) 無(wú)向圖G5(b) G5的鄰接表圖7.1734129108567(c) 無(wú)向圖G5的三個(gè)連通分量第第7章章 圖圖 設(shè)設(shè)E(G)E(G)為連通圖為連通圖G G中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，將歷圖時(shí)，將E(G)E(G)分成兩個(gè)集合分成兩個(gè)集合T(G)T(G)和和B(G)B(G)。T(G)T(G)為遍歷時(shí)的邊的為

45、遍歷時(shí)的邊的集合，集合，B(G)B(G)是剩余邊的集合。顯然，是剩余邊的集合。顯然，T(G)T(G)和和G G中所有頂點(diǎn)一起構(gòu)成中所有頂點(diǎn)一起構(gòu)成連通圖連通圖G G的極小連通子圖，且為一棵生成樹(shù)，分別稱(chēng)為深度優(yōu)先生的極小連通子圖，且為一棵生成樹(shù)，分別稱(chēng)為深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。成樹(shù)和廣度優(yōu)先生成樹(shù)。 對(duì)于非連通圖，每個(gè)連通分量的頂點(diǎn)集和走過(guò)的邊集一起構(gòu)對(duì)于非連通圖，每個(gè)連通分量的頂點(diǎn)集和走過(guò)的邊集一起構(gòu)成若干生成樹(shù)，稱(chēng)為生成森林。成若干生成樹(shù)，稱(chēng)為生成森林。 第第7章章 圖圖 7.4.2 7.4.2 最小生成樹(shù)最小生成樹(shù)(prim(prim算法）算法） 設(shè)G =(V,E)是無(wú)向連通帶權(quán)

46、圖，即一個(gè)網(wǎng)絡(luò)網(wǎng)絡(luò)。 E中每條邊(v,w)的權(quán)為cvw。如果G的子圖G是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G為G的生成樹(shù)生成樹(shù)。 生成樹(shù)上各邊權(quán)的總和稱(chēng)為該生成樹(shù)的耗費(fèi)耗費(fèi)。 在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)最小生成樹(shù)。第第7章章 圖圖 網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)cvw表示建立城市v和城市w之間的通信線(xiàn)路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。 最小生成樹(shù)的應(yīng)用最小生成樹(shù)的應(yīng)用第第7章章 圖圖 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)是一條具有最小代價(jià)的邊，且uU，

47、vV-U，則必存在一棵包含邊(u,v)的最小生成樹(shù)。這個(gè)性質(zhì)簡(jiǎn)稱(chēng)為MSTMST性質(zhì)性質(zhì)。 本節(jié)介紹的本節(jié)介紹的PrimPrim算法和算法和KruskalKruskal算法都算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這盡管這2 2個(gè)算法做貪心選擇的方式不同，它個(gè)算法做貪心選擇的方式不同，它們都利用了上面的最小生成樹(shù)性質(zhì)。們都利用了上面的最小生成樹(shù)性質(zhì)。1 1、最小生成樹(shù)性質(zhì)、最小生成樹(shù)性質(zhì)第第7章章 圖圖 設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。 Prim算法的基本思想基本思想是： （1）首先置S=1，生成樹(shù)邊集T= ； （2）然后，只要S是V的

48、真子集，就作如下的貪心選擇：貪心選擇：選取滿(mǎn)足條件選取滿(mǎn)足條件i i S S，j j V-SV-S，且，且cijcij最小的邊，將頂點(diǎn)最小的邊，將頂點(diǎn)j j添加到添加到S S中中, ,將邊（將邊（i,j)i,j)加入加入T T。 這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。 在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)最小生成樹(shù)。 2 2、PrimPrim算法算法第第7章章 圖圖 點(diǎn)到集合的距離點(diǎn)到集合的距離 集合外一點(diǎn)u，到集合S=v1,v2,vn的距離定義為點(diǎn)u到結(jié)合s中所有點(diǎn)間的最小距離。即： D(u,S)=mind(u,vi), vi屬于S第第7章章 圖圖 PrimPrim算法的基本思想算

49、法的基本思想 有了點(diǎn)到集合的距離，Prim算法的基本思想基本思想可這樣描述： （1）首先置S=1，生成樹(shù)邊集T= ； （2）然后，只要S是V的真子集，就作如下的貪貪心選擇：心選擇：在在S S外的點(diǎn)中選取離集合外的點(diǎn)中選取離集合S S最近的點(diǎn)加入最近的點(diǎn)加入S.S. 這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。 這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最最小生成樹(shù)小生成樹(shù)。第第7章章 圖圖 例如例如，對(duì)于下圖中的帶權(quán)圖，按PrimPrim算法算法選取邊的過(guò)程如圖所示。62111965432174133L=0 1 2 10 6 11 26 0 9 11 11 9 0 7 3 13 7 0 4 3 4 0 第第

50、7章章 圖圖 62111965432174133(1)初始狀態(tài)：任選一點(diǎn)加入初始狀態(tài)：任選一點(diǎn)加入S, S=1，T=；第第7章章 圖圖 62111965432174133（2）選頂點(diǎn)）選頂點(diǎn)2(d(1,2)=1)加入加入S： S=1，2將邊（將邊（1，2）加入）加入T，T=（1，2）；2第第7章章 圖圖 62111965432174133 (3)選頂點(diǎn)選頂點(diǎn)3(d(1,3)=2)加入加入S： S=1，2，3將邊（將邊（1，3）加入）加入T，T=(1,2)，(1,3)；3第第7章章 圖圖 62111965432174133 (4)選頂點(diǎn)選頂點(diǎn)4(d(3,4)=9)加入加入S： S=1，2，3，4

51、將邊（將邊（3，4）加入）加入T，T=(1,2),(1,3),(3,4)；4第第7章章 圖圖 62111965432174133(5)選頂點(diǎn)選頂點(diǎn)6(d(4,6)=3)加入加入S： S=1，2，3，4，6將邊（將邊（4，6）加入）加入T，T=(1,2),(1,3),(3,4),(4,6)；6第第7章章 圖圖 62111965432174133（6）選頂點(diǎn)）選頂點(diǎn)5(d(6,5)=4)加入加入S： S=1，2，3，4，6將邊（將邊（6，5）加入）加入T，T=(1,2),(1,3),(3,4),(4,6),(6,5)；5第第7章章 圖圖 為了實(shí)現(xiàn)這個(gè)算法需要設(shè)置一個(gè)為了實(shí)現(xiàn)這個(gè)算法需要設(shè)置一個(gè)輔助

52、數(shù)組輔助數(shù)組closedge，以，以記錄從記錄從U到到V-U具有最小代價(jià)的邊。對(duì)每個(gè)頂點(diǎn)具有最小代價(jià)的邊。對(duì)每個(gè)頂點(diǎn)vV-U，在輔，在輔助數(shù)組中存在一個(gè)分量助數(shù)組中存在一個(gè)分量closedgev，它包括兩個(gè)域，它包括兩個(gè)域adjvex和和lowcost，其中，其中l(wèi)owcost存儲(chǔ)該邊上的權(quán)，存儲(chǔ)該邊上的權(quán)， 顯然有顯然有 closedgev.lowcost=Min(cost(u, v) | uU)struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; /* 求最小生成樹(shù)時(shí)的求最小生成樹(shù)時(shí)的輔助數(shù)組輔助數(shù)組*/ 第第7

53、章章 圖圖 -100-1-1-101 12lowcost:adjvex:Closedgei.lowcost:記錄頂點(diǎn)記錄頂點(diǎn)i 到到S的最短距離；的最短距離；Closedgei. adjvex:記錄頂點(diǎn)記錄頂點(diǎn)i到集合中哪個(gè)頂點(diǎn)最近到集合中哪個(gè)頂點(diǎn)最近第第7章章 圖圖 62111965432174133(1)初始狀態(tài)：初始狀態(tài)：任選一點(diǎn)加入任選一點(diǎn)加入S, S=1，T=； 以上選擇過(guò)程計(jì)算機(jī)如何實(shí)現(xiàn)？以上選擇過(guò)程計(jì)算機(jī)如何實(shí)現(xiàn)？-100-1-1-101 12lowcost:adjvex:第第7章章 圖圖 62111965432174133(2) 在在S 外的頂點(diǎn)中選擇頂點(diǎn)外的頂點(diǎn)中選擇頂點(diǎn)2加

54、入加入S。-100-1-1-101 120更新更新s外的點(diǎn)到外的點(diǎn)到s的距離及最近頂?shù)木嚯x及最近頂點(diǎn)點(diǎn)111lowcost:adjvex:第第7章章 圖圖 (3) 選擇離集合選擇離集合S最近的頂點(diǎn)最近的頂點(diǎn)3加入加入S62111965432174133-1002-1-100 0211更新更新s外的點(diǎn)到外的點(diǎn)到s的距離及最近頂?shù)木嚯x及最近頂點(diǎn)點(diǎn)092132lowcost:adjvex:第第7章章 圖圖 (4) 選擇離集合選擇離集合S最近的頂點(diǎn)最近的頂點(diǎn)4加入加入S62111965432174133-1002-1-100 00913更新更新s外的點(diǎn)到外的點(diǎn)到s的距離及最近頂?shù)木嚯x及最近頂點(diǎn)點(diǎn)033

55、37lowcost:adjvex:第第7章章 圖圖 (5) 選頂點(diǎn)選頂點(diǎn)6加入加入S62111965432174133-10024300 00073更新更新s外的點(diǎn)到外的點(diǎn)到s的距離及最近頂?shù)木嚯x及最近頂點(diǎn)點(diǎn)045lowcost:adjvex:第第7章章 圖圖 (6) 選頂點(diǎn)選頂點(diǎn)5加入加入S：62111965432174133-10025300 00040lowcost:adjvex:0第第7章章 圖圖 void Prim(int GN, int n) /用普里姆方法建立網(wǎng)G的最小生成樹(shù)minSTree/初始化/從序號(hào)為0的頂點(diǎn)出發(fā)構(gòu)造最小生成樹(shù)/尋找當(dāng)前最小權(quán)值的邊的頂點(diǎn)/修改其他頂點(diǎn)的邊

56、的權(quán)值Prim算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)第第7章章 圖圖 在Prim算法執(zhí)行過(guò)程中，先找出數(shù)組closedge中l(wèi)owcost值最小的頂點(diǎn)k, 將k添加到S中，并對(duì)lowcost和adjvex作必要的修改。 用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)計(jì)算時(shí)間間為)(2nO第第7章章 圖圖 void MiniSpanTree_Prim(MGraph G, VertexType u)/*從頂點(diǎn)從頂點(diǎn)u出發(fā)，出發(fā)， 按普里姆算法構(gòu)造連通網(wǎng)按普里姆算法構(gòu)造連通網(wǎng)G 的最小生的最小生成樹(shù)，成樹(shù)， 并輸出生成樹(shù)的每條邊并輸出生成樹(shù)的每條邊*/ k=LocateVertex(G, u); for (j=0; jG.

57、vexnum; j+) if ( j! =k) closedgej=u, G.arcskj.adj; closedgek.lowcost=0; 第第7章章 圖圖 for (i=1; iG.vexnum; i+) k=Minium(closedge); printf(closedgek.adjvex, G.vexsk); /*輸出生成樹(shù)的當(dāng)輸出生成樹(shù)的當(dāng)前最小邊前最小邊*/ closedgek.lowcost=0; /*將頂點(diǎn)將頂點(diǎn)k納入納入U(xiǎn)集合集合*/ for ( j=0 ; jG.vexnum; j+) /*在頂點(diǎn)在頂點(diǎn)v0并入并入U(xiǎn)之后，之后， 更更新新closedgej */ if (

58、 G.arcskj.adj closedgej.lowcost) closedgej=G.vexsk, G.arcskj.adj; /for /minispantree_prim第第7章章 圖圖 3.Kruskal3.Kruskal算法算法貪心策略：總是選擇最小代價(jià)連通兩個(gè)不同的連通分貪心策略：總是選擇最小代價(jià)連通兩個(gè)不同的連通分支。支?；舅枷牖舅枷耄海?）首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。（2）然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊(v,w) ： （a)如果端點(diǎn)v和w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就保留邊(v,w) (b)

59、如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接丟棄邊(v,w)。 這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。第第7章章 圖圖 例如，例如，對(duì)前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹(shù)上的邊如下圖所示。62111965432174133第第7章章 圖圖 365421邊集合排序：邊集合排序：(1,2)=1, (1,3)=2, (4,6)=3, (5,6)=4, (2,3)=6, (4,5)=7 (3,4)=9, (2,4)=11, (3,5)=13第第7章章 圖圖 365421最小生成樹(shù)的邊：最小生成樹(shù)的邊：(1,2)=1, (1,3)=2, (4,6)=3, (5,6)=4,

60、(3,4)=9第第7章章 圖圖 KruskalKruskal算法（1）按非降序把E中的邊排序（2）最小生成樹(shù)的邊集合T置為空（3）當(dāng)T中邊的數(shù)量小于n-1 ,做 a.在E 中取下一條邊（x,y)； b.若頂點(diǎn)x到y(tǒng)無(wú)路徑：則將（x,y） 加入T第第7章章 圖圖 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 頂點(diǎn)x到y(tǒng)無(wú)路徑這一問(wèn)題如何判斷？ 解決辦法：用并查集（見(jiàn)第用并查集（見(jiàn)第6章章 等價(jià)關(guān)系求解）等價(jià)關(guān)系求解）第第7章章 圖圖 這是一個(gè)有6棵樹(shù)的森林，6個(gè)頂點(diǎn)各屬一個(gè)集合，可用如下并查集表示365421123456123456(1,2)=1, (1,3)=2, (4,6)=3, (5,6)=4, (2,3)=6, (