第7章圖(5.11)

1、第第7章章 圖圖 第第7章章 圖圖 圖圖 7.1 圖的定義與基本術(shù)語圖的定義與基本術(shù)語 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 7.3 圖的遍歷圖的遍歷 7.4 圖的連通性問題圖的連通性問題 7.5 有向無環(huán)圖的應(yīng)用有向無環(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òu)成，記作由兩個集合構(gòu)成，記作G= 其中其中: V（vertex）是頂點的非空有限集合）是頂點的非空有限集合 E（edge）是邊的有限集合，）是邊的有限集合， 而邊是頂點對而邊是頂點對的集合。的集合。 V0V0 V4V4 V3V3 V1V1 V2V27.1 圖的定義與基本術(shù)語圖的定義與基本術(shù)語 第第7章章 圖圖 例例1 1 交通圖（公路、鐵路）交通圖（公路、鐵路） 頂點頂點：地點：地點 邊邊：連接地點的公路：連接地點的公路 交通圖中的有單行道雙行道，分別用交通圖中的有單行道雙行道，分別用有向邊有向邊、無向邊無向邊表示；表示；例例2 2 電路圖電路圖 頂點頂點：元件：元件 邊邊

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

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

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

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

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

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

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

10、術(shù)語 第第7章章 圖圖 (a)(a)(b)(b)(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 設(shè)有兩個圖設(shè)有兩個圖G=（V，E）、）、G1=（V1，E1），若），若V1 V，E1 E，E1關(guān)聯(lián)的頂點都在關(guān)聯(lián)的頂點都在V1中，則稱中，則稱 G1是是G的的子圖子圖； 例例 (b)、(c) 是是 (a) 的子圖的子圖子圖子圖7.1 圖的定義與基本術(shù)語圖的定義與基本術(shù)語 第第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 在無（有）向圖在無（有）向圖G=中，若中，若對任何兩個頂點對任何兩個頂點 v、u 都存在從都存在從v 到到 u 的路徑的路徑，則稱，則稱G是是連通圖連通圖對有向圖而言，稱對有向圖而言，稱強(qiáng)連通圖強(qiáng)連通圖連通圖、強(qiáng)連通圖連通圖、強(qiáng)連通圖7.1 圖的定義與基本術(shù)語圖的定義與基本術(shù)語 第第7章章 圖圖 連通分量連通分量非連通圖非連通圖 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4無向圖無向圖G 的極大連通子圖稱為的極大連通子

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

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

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

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

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

17、.2 圖的存儲結(jié)構(gòu)圖的存儲結(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的鄰接矩陣是滿足如下條件：的鄰接矩陣是滿足如下條件：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鄰接矩陣表示法的空間代價鄰接矩陣表示法的空間代價只與圖的頂點數(shù)有關(guān)只與圖的頂點數(shù)有關(guān) V0V0 V4V4 V3V3 V1V1 V2V21）無向圖鄰接矩陣是）無向圖鄰接矩陣是對稱矩陣對稱矩陣，可考慮矩陣的壓縮存儲，可考慮矩陣的壓縮存儲2）G占用存儲空間只與它的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；占用存儲空間只與它的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)； 適用于邊稠密的圖適

19、用于邊稠密的圖V0 V1 V2 V3 V4鄰接矩陣表示的特點鄰接矩陣表示的特點第第7章章 圖圖 鄰接矩陣下圖的有關(guān)操作鄰接矩陣下圖的有關(guān)操作1）求頂點）求頂點v的度：的度：2）判斷兩頂點是否鄰接：）判斷兩頂點是否鄰接：3）在圖中增加、刪除邊：）在圖中增加、刪除邊：4）檢測圖中的總邊數(shù)：）檢測圖中的總邊數(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ù)組對應(yīng)行（或列）中等于二維數(shù)組對應(yīng)行（或列）中1的個數(shù)；的個數(shù)；只需判二維數(shù)組對應(yīng)分量是否為只需判二維數(shù)組對應(yīng)分量是否為1；只需對二維數(shù)組對應(yīng)分量賦值只需對二維數(shù)組對應(yīng)分量賦值1或清或清0；掃描整個數(shù)組掃描整個數(shù)組A，統(tǒng)計出數(shù)組中非，統(tǒng)計出數(shù)組中非0元素元素的個數(shù)。的個數(shù)。第第7章章 圖圖 鄰接矩陣的鄰接矩陣的C語言描述語言描述#define N 10 /*最多頂點數(shù)最多頂點數(shù)*/typedef char vextype; /*頂點類型頂點類型*/typ

21、edef sturct vextype vexsN; /*存頂點的數(shù)組存頂點的數(shù)組*/ adjtype edgeNN;/*存邊信息的矩陣存邊信息的矩陣*/ int n; /頂點數(shù)頂點數(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章章 圖圖 建立無向圖的鄰接矩陣建立無向圖的鄰接矩陣 算法思想：算法思想：1）給存頂點的一維數(shù)組賦值；）給

22、存頂點的一維數(shù)組賦值；2）初始化存邊的二維數(shù)組；）初始化存邊的二維數(shù)組；3）依次讀入頂點對，給二維數(shù)組相關(guān)的元素）依次讀入頂點對，給二維數(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) 編號編號 指針指針鄰接表表示鄰接表表示1. 無向圖的鄰接表無向圖的鄰接表 頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中；頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中； 關(guān)聯(lián)同一頂點的邊：用關(guān)聯(lián)同

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

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

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

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

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

28、輸入信息：將圖轉(zhuǎn)換為線性輸入信息：頂點數(shù)為：頂點數(shù)為：n=5邊數(shù)為邊數(shù)為:e=6邊集：邊集：0 10 31 21 42 32 4第第7章章 圖圖 思想：如何給存儲結(jié)構(gòu)賦值思想：如何給存儲結(jié)構(gòu)賦值1. 建立頂點數(shù)組。讀入各頂點數(shù)據(jù)建立頂點數(shù)組。讀入各頂點數(shù)據(jù)data，將，將firstarc域賦域賦NULL。2. 建立各頂點的鄰接表。讀入頂點對建立各頂點的鄰接表。讀入頂點對, 生成兩個結(jié)點，分生成兩個結(jié)點，分別插入頂點別插入頂點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建立無向圖的鄰接表建立無向圖的鄰接表第第7章章 圖圖 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 1加入邊加入邊(u, v): 設(shè)設(shè)u=0, v=10 0建立無向圖的鄰接表建立無向圖的鄰接表第第7章章 圖圖 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 10 0插入邊插入邊 (v0,v3):u=0,v=33 3建立無向圖的鄰接表建立無向圖的鄰接表第第7章章 圖圖 在不同的存儲結(jié)構(gòu)下，實現(xiàn)各種

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

31、圖圖 復(fù)習(xí)復(fù)習(xí)1、有頭結(jié)點的單鏈表4，2，6，5，3，1（1）單鏈表的建立（頭部插入新結(jié)點和尾部插入新結(jié)點兩種方法）（2）輸出并刪除第i個結(jié)點（3）在第i個位置插入新元素x (4) 對所有元素排序2、重做約瑟夫環(huán)猴子選猴王（無頭結(jié)點的循環(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、遍歷圖的遍歷 圖的遍歷：從圖的某頂點出發(fā)，訪問圖中所有頂圖的遍歷：從圖的某頂點出發(fā)，訪問圖中所有頂點，并且每個頂點僅訪問一次。點，并且每個頂點僅訪問一次。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4第第7章章 圖圖 一一 、深度優(yōu)先遍歷（、深度優(yōu)先遍歷（DFS）1 1）從圖中某頂點）從圖中某頂點v v出發(fā)，訪問頂點出發(fā)，訪問頂點v v；2 2）依次從）依次從v v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進(jìn)行深度優(yōu)先的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進(jìn)行深度優(yōu)先遍歷；遍歷； V0,V1,V3

33、,V7,V4,V2,V5,V6 V0,V1,V3,V7,V4,V2,V5,V6 由于沒有規(guī)定由于沒有規(guī)定訪問鄰接點的順序，訪問鄰接點的順序，DFSDFS序列不唯一序列不唯一例例求圖求圖G G以以V0V0起點的深度優(yōu)先序列起點的深度優(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章章 圖圖 圖中某未訪問過的頂點圖中某未訪問過的頂點vivi出發(fā)：

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

35、規(guī)定由于沒有規(guī)定訪問鄰接點的順序，訪問鄰接點的順序，BFSBFS序列不唯一序列不唯一例例求圖求圖G G 的以的以V0V0起點的的廣度優(yōu)先序列起點的的廣度優(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章章 圖圖 寫出下圖的深度優(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章章 圖圖 在圖中，訪問部分頂點后，可能又沿著其他邊在圖中，訪問部分頂點后，可能又沿著其他邊回到已被訪問過的頂點。為保證每一個頂點只被訪回到已被訪問過的頂點。為保證每一個頂點只被訪問一次，必須對頂點進(jìn)行標(biāo)記，可用一個輔助數(shù)組問一次，必須對頂點進(jìn)行標(biāo)記，可用一個輔助數(shù)組 visitedMAX作為對頂點的標(biāo)記。作為對頂點的標(biāo)記。7.3.2 圖的遍歷算法圖的遍歷算法輔助數(shù)組輔助數(shù)組 int visitedMAX; /頂點標(biāo)志數(shù)組頂點標(biāo)志數(shù)組,全局變量全局變量 若若visitedi=0，頂點，頂點vi未被訪問未被訪問 若若visitedi=1，當(dāng)，當(dāng)vi已被訪問。已被訪問。

37、visitvisit0 01 12 23 34 4m-1m-10 00 00 00 00 0第第7章章 圖圖 void DFSTraverse (Graph G,Status (*visit)(int v)/*對圖對圖G進(jìn)行深度優(yōu)先搜索，進(jìn)行深度優(yōu)先搜索，Graph 表示圖的一種存儲結(jié)構(gòu)表示圖的一種存儲結(jié)構(gòu)*/ VisitFunc = Visit; for (v=0; vG.vexnum; v+) visitedv=False ; /*訪問標(biāo)志數(shù)組初訪問標(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章章 圖圖 遞歸過程分析遞歸過程分析 3 1 2 4 5 7 6 8 -無向圖無向圖 DFS(1)DFS(2)DFS(4)DFS(8)DFS(5)DFS(6)DFS(3)DFS(7)鄰接矩陣深度優(yōu)先搜索示意圖鄰接矩陣深度優(yōu)先搜索示意圖第第7章章 圖圖 基于鄰接表的基于鄰接表的DFS算法算法:DFSl() 核心問題：如何在鄰接表中沿深度進(jìn)行遍歷 時間復(fù)雜度：O(n+e)第第7章章 圖圖 思想：思想：圖中某未訪問過的頂點圖中某未訪問過的頂點vi出發(fā)：出發(fā)：1）訪問頂點）訪問頂點vi ；2）訪問）訪問 vi 的所有未被訪問的鄰接點的所有未被

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

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

41、如下處理： 如果j 未被訪問過，則訪問j并讓j入隊列 第第7章章 圖圖 BFS算法算法:void BFSTraverse(Graph G, Statis (*Visit)(int v) for(v=0;vG.vexnum;+v) visitedv =FALSE; InitQueue(Q); /*初始化空隊*/ 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無向圖無向圖

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)，對該圖進(jìn)行，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點序列正確的是（深度優(yōu)先遍歷，得到的頂點序列正確的是（ ）。）。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個序列中，符合深度優(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個 B4個 C3個 D2個 a

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

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

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

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

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

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

49、法的基本思想 有了點到集合的距離，Prim算法的基本思想基本思想可這樣描述： （1）首先置S=1，生成樹邊集T= ； （2）然后，只要S是V的真子集，就作如下的貪貪心選擇：心選擇：在在S S外的點中選取離集合外的點中選取離集合S S最近的點加入最近的點加入S.S. 這個過程一直進(jìn)行到S=V時為止。 這個過程中選取到的所有邊恰好構(gòu)成G的一棵最最小生成樹小生成樹。第第7章章 圖圖 例如例如，對于下圖中的帶權(quán)圖，按PrimPrim算法算法選取邊的過程如圖所示。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)：任選一點加入初始狀態(tài)：任選一點加入S, S=1，T=；第第7章章 圖圖 62111965432174133（2）選頂點）選頂點2(d(1,2)=1)加入加入S： S=1，2將邊（將邊（1，2）加入）加入T，T=（1，2）；2第第7章章 圖圖 62111965432174133 (3)選頂點選頂點3(d(1,3)=2)加入加入S： S=1，2，3將邊（將邊（1，3）加入）加入T，T=(1,2)，(1,3)；3第第7章章 圖圖 62111965432174133 (4)選頂點選頂點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)選頂點選頂點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）選頂點）選頂點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章章 圖圖 為了實現(xiàn)這個算法需要設(shè)置一個為了實現(xiàn)這個算法需要設(shè)置一個輔助

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

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

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

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

56、的權(quán)值Prim算法的實現(xiàn)算法的實現(xiàn)第第7章章 圖圖 在Prim算法執(zhí)行過程中，先找出數(shù)組closedge中l(wèi)owcost值最小的頂點k, 將k添加到S中，并對lowcost和adjvex作必要的修改。 用這個辦法實現(xiàn)的Prim算法所需的計算時計算時間間為)(2nO第第7章章 圖圖 void MiniSpanTree_Prim(MGraph G, VertexType u)/*從頂點從頂點u出發(fā)，出發(fā)， 按普里姆算法構(gòu)造連通網(wǎng)按普里姆算法構(gòu)造連通網(wǎng)G 的最小生的最小生成樹，成樹， 并輸出生成樹的每條邊并輸出生成樹的每條邊*/ 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); /*輸出生成樹的當(dāng)輸出生成樹的當(dāng)前最小邊前最小邊*/ closedgek.lowcost=0; /*將頂點將頂點k納入納入U集合集合*/ for ( j=0 ; jG.vexnum; j+) /*在頂點在頂點v0并入并入U之后，之后， 更更新新closedgej */ if (

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

59、如果端點v和w在當(dāng)前的同一個連通分支中，就直接丟棄邊(v,w)。 這個過程一直進(jìn)行到只剩下一個連通分支時為止。第第7章章 圖圖 例如，例如，對前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。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最小生成樹的邊：最小生成樹的邊：(1,2)=1, (1,3)=2, (4,6)=3, (5,6)=4,

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