數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)-第7章圖11-03ppt課件

1、第 2 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l圖的定義圖的定義l圖圖(Graph)圖圖G是由兩個(gè)集合是由兩個(gè)集合V(G)和和E(G)組成的組成的,記為記為G=(V,E)l 其中：其中：V(G)是頂點(diǎn)的非空有限集是頂點(diǎn)的非空有限集 l E(G)是邊的有限集合，邊是頂是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)Α｜c(diǎn)的無序?qū)蛴行驅(qū)?。l圖的分類圖的分類l 有向圖有向圖: All arcs are directed l 無向圖：無向圖：All arcs are undirected第 3 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l圖的定義圖的定義l有向圖有向圖有向圖有向圖G是由兩個(gè)集合是由

2、兩個(gè)集合V(G)和和E(G)組成的。組成的。l 其中：其中：V(G)是頂點(diǎn)的非空有限集。是頂點(diǎn)的非空有限集。l E(G)是有向邊也稱弧的有是有向邊也稱弧的有限集合，弧是頂點(diǎn)的有序?qū)?，記為限集合，弧是頂點(diǎn)的有序?qū)?，記為，v、w是頂點(diǎn)，是頂點(diǎn)，v為弧尾，為弧尾，w為弧頭。為弧頭。第 4 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l例如：例如：l G1 = l V1 = A, B, C, D, E l E1 = , , , , , , EACBD第 5 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l圖的定義圖的定義l無向圖無向圖無向圖無向圖G是由兩個(gè)集合是由兩個(gè)集合V(G)和和E(G)組成的。

3、組成的。l 其中：其中：V(G)是頂點(diǎn)的非空有限集。是頂點(diǎn)的非空有限集。l E(G)是邊的有限集合，邊是頂是邊的有限集合，邊是頂點(diǎn)的無序?qū)Γ洖辄c(diǎn)的無序?qū)?，記?(v,w) 或或 (w,v)，并且，并且(v,w)=(w,v)。第 6 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l例如：例如：l G2 = l V2 = v0 ,v1,v2,v3,v4 lE2 = (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) V0V4V3V1V2第 7 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l例如：例如：l G2 = l V2 = v0，v1，

4、v2，v3 l E2 = , , , V0 V0 V1 V1 V2 V2 V3 V3 例例245136G1V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , 第 8 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l圖的運(yùn)用舉例圖的運(yùn)用舉例l例例1、交通圖公路、鐵路、交通圖公路、鐵路l 頂點(diǎn)：地點(diǎn)頂點(diǎn)：地點(diǎn)邊：銜接邊：銜接地點(diǎn)的路地點(diǎn)的路l例例2、電路圖、電路圖l 頂點(diǎn)：元件頂點(diǎn)：元件邊：銜接邊：銜接元件之間的線路元件之間的線路l例例3、通訊線路圖、通訊線路圖l 頂點(diǎn)：地點(diǎn)頂點(diǎn)：地點(diǎn)邊：地點(diǎn)邊：地點(diǎn)間的連線間的連線l例例4、各種流程圖、各種流程圖l如

5、產(chǎn)品的消費(fèi)流程圖。如產(chǎn)品的消費(fèi)流程圖。l 頂點(diǎn)：工序頂點(diǎn)：工序邊：各道邊：各道工序之間的順序關(guān)系工序之間的順序關(guān)系第 9 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l圖的根本術(shù)語圖的根本術(shù)語l1 鄰接點(diǎn)及關(guān)聯(lián)邊鄰接點(diǎn)及關(guān)聯(lián)邊l 鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)鄰接點(diǎn)：邊的兩個(gè)頂點(diǎn)l 關(guān)聯(lián)邊：假設(shè)邊關(guān)聯(lián)邊：假設(shè)邊e= (v, u), 那么稱頂點(diǎn)那么稱頂點(diǎn)v、u 關(guān)聯(lián)邊關(guān)聯(lián)邊el2 頂點(diǎn)的度、入度、出度頂點(diǎn)的度、入度、出度 頂點(diǎn)頂點(diǎn)V的度的度 = 與與V相關(guān)聯(lián)的邊的數(shù)目相關(guān)聯(lián)的邊的數(shù)目l 在有向圖中：在有向圖中： l 頂點(diǎn)頂點(diǎn)V的出度的出度OD = 以以V為起點(diǎn)有向邊數(shù)為起點(diǎn)有向邊數(shù)l 頂點(diǎn)頂點(diǎn)V的入度的

6、入度ID = 以以V為終點(diǎn)有向邊數(shù)為終點(diǎn)有向邊數(shù)l 頂點(diǎn)頂點(diǎn)V的度的度Degree = V的出度的出度+V的入度的入度l 設(shè)圖設(shè)圖G 的頂點(diǎn)數(shù)為的頂點(diǎn)數(shù)為 n，邊數(shù)為，邊數(shù)為 el 圖的一切頂點(diǎn)的度數(shù)和圖的一切頂點(diǎn)的度數(shù)和 = 2*el 每條邊對圖的一切頂點(diǎn)的度數(shù)和每條邊對圖的一切頂點(diǎn)的度數(shù)和“奉獻(xiàn)奉獻(xiàn)2度度 V0 V0 V4 V4 V3 V3 V1 V1 V2 V2e eV0V1V2V3第 10 頁舉例舉例 ACDFE例如例如: :TD(B) = 3TD(A) = 2BABECF例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3第 11 頁7.1 7.1 圖的術(shù)語與定義圖的

7、術(shù)語與定義l途徑、回路途徑、回路l 無向圖無向圖 G =V，E中的頂點(diǎn)中的頂點(diǎn)序列序列v1, v2, ,vk，假設(shè)，假設(shè) (vi,vi+1)E ( i=1, 2 , k-1)， v=v1, u=vk，那么稱，那么稱該序列是從頂點(diǎn)該序列是從頂點(diǎn)v到頂點(diǎn)到頂點(diǎn)u的途徑；假的途徑；假設(shè)設(shè)v=u，那么稱該序列為回路。，那么稱該序列為回路。l 有向圖有向圖 DG =V，E中的頂點(diǎn)中的頂點(diǎn)序列序列 v1, v2, , vk，假設(shè)，假設(shè) E (i=1,2,k-1)，v=v1，u=vk，那么稱該序列是從頂點(diǎn)，那么稱該序列是從頂點(diǎn)v到頂點(diǎn)到頂點(diǎn)u的途徑；假設(shè)的途徑；假設(shè)v=u，那么稱該序列為，那么稱該序列為回路

8、?；芈?。第 12 頁例例: :長度為長度為3 3的途徑是？的途徑是？簡單途徑簡單途徑: :序列中頂點(diǎn)不反復(fù)出現(xiàn)的途徑。序列中頂點(diǎn)不反復(fù)出現(xiàn)的途徑。簡單回路簡單回路: :序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)一樣的途徑。序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)一樣的途徑。ABECF(A-F)第 13 頁7.1 7.1 圖的術(shù)語與定義圖的術(shù)語與定義l例如例如l 在圖在圖G1中，中，V0, V1, V2, V3 是是 V0 到到 V3 的途徑；的途徑；V0, V1, V2, V3, V0 是回是回路。路。l 在圖在圖G2中，中，V0, V2, V3 是是 V0 到到 V3 的途徑；的途徑； V0, V2, V3, V

9、0 是回路。是回路。無向圖無向圖G1G1有向圖有向圖G2 V0 V4 V3 V1 V2V0V1V2V3第 14 頁7.1 圖的術(shù)語與定義圖的術(shù)語與定義l連通圖連通圖connected Graph強(qiáng)連通圖強(qiáng)連通圖l 在無有向圖在無有向圖 G= 中，假中，假設(shè)對任何兩個(gè)頂點(diǎn)設(shè)對任何兩個(gè)頂點(diǎn) v、u 都存在從都存在從 v 到到 u 的途徑，那么稱的途徑，那么稱G是連通圖強(qiáng)連通圖，是連通圖強(qiáng)連通圖，strong connected 非連通圖非連通圖 連通圖連通圖 強(qiáng)連通圖強(qiáng)連通圖 非強(qiáng)連通圖非強(qiáng)連通圖 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1

10、 V5 V4沒有沒有V1到到V0的途徑的途徑第 15 頁7.1 圖的術(shù)語與定義圖的術(shù)語與定義l子圖子圖(sub-Graph)l 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖 G =V，E，G1 =V1，E1，假設(shè)，假設(shè)V1 V，E1 E，E1關(guān)聯(lián)的頂點(diǎn)都在關(guān)聯(lián)的頂點(diǎn)都在 V1 中，那么稱中，那么稱 G1 是是 G 的子圖；的子圖；l例例 (b)、(c)、(d) 是是 (a) 的子圖的子圖(a)(b)(c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2(d) V4 V1 V2第 16 頁7.1 圖的術(shù)語與定義圖的術(shù)語與定義l連通分量連通分量connected componen

11、tl 無向圖無向圖G的極大連通子圖稱為的極大連通子圖稱為G的連通的連通分量。分量。l 極大連通子圖含義：該子圖極大連通子圖含義：該子圖F是是G的連的連通子圖，將通子圖，將G的任何不在該子圖的任何不在該子圖F中的頂點(diǎn)中的頂點(diǎn)參與，構(gòu)成的子圖將不再連通。看圖參與，構(gòu)成的子圖將不再連通?？磮D7.3的的例子例子連通分量連通分量非連通圖非連通圖 V0 V2 V3 V1 V5 V4第 17 頁7.1 圖的術(shù)語與定義圖的術(shù)語與定義l 強(qiáng)連通分量強(qiáng)連通分量strong connected componentl 有向圖有向圖D的極大強(qiáng)連通子圖稱為的極大強(qiáng)連通子圖稱為D的強(qiáng)連通分量。的強(qiáng)連通分量。l 極大強(qiáng)連通子

12、圖的含義：該子圖極大強(qiáng)連通子圖的含義：該子圖F是是D的強(qiáng)連的強(qiáng)連通子圖，將通子圖，將D的任何不在該子圖的任何不在該子圖F中的頂點(diǎn)參與，中的頂點(diǎn)參與，構(gòu)成的子圖將不再是強(qiáng)連通的。構(gòu)成的子圖將不再是強(qiáng)連通的。強(qiáng)連通分量強(qiáng)連通分量 V0 V1 V2 V3 V0 V2 V3 V1將將V1參與后參與后不再連通不再連通第 18 頁7.1 圖的術(shù)語與定義圖的術(shù)語與定義l生成樹生成樹l 包含無向圖包含無向圖 G 的一切頂點(diǎn)的極小最少的一切頂點(diǎn)的極小最少數(shù)目的邊連通子圖稱為數(shù)目的邊連通子圖稱為G的生成樹。的生成樹。l 極小連通子圖極小連通子圖 的含義：該子圖是的含義：該子圖是G的連的連通子圖且包含通子圖且包含G

13、的全部頂點(diǎn)，在該子圖中刪除的全部頂點(diǎn)，在該子圖中刪除任何一條邊，子圖將不再連通，假設(shè)任何一條邊，子圖將不再連通，假設(shè)T是是G的的生成樹當(dāng)且僅當(dāng)生成樹當(dāng)且僅當(dāng)(if and only if)T滿足如下條件：滿足如下條件：l T是是G的連通子圖的連通子圖l T包含包含G的一切頂點(diǎn)的一切頂點(diǎn)l T中無回路中無回路連通圖連通圖G1G1的生成樹的生成樹 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2第 19 頁或者說：一個(gè)連通圖的生成樹，是指一個(gè)極小連通子圖，它含有圖中的全部頂點(diǎn)，且以最少的邊數(shù)(n-1條)使其連通。如添加一條邊必構(gòu)成一個(gè)環(huán)。有n個(gè)頂點(diǎn)的連通圖，其生成樹是由n個(gè)頂點(diǎn)和n-1條

14、邊組成的連通子圖，如圖C.BAGLMDIFCKHEJBALMFCJBALMFCJ (a)無向圖G (b) G的連通分量G1 (c)G1的一棵生成樹第 20 頁生成樹的了解要點(diǎn)生成樹的了解要點(diǎn)l假設(shè)在生成樹上添加一條邊，必定構(gòu)成一假設(shè)在生成樹上添加一條邊，必定構(gòu)成一個(gè)環(huán)，由于這條邊依靠的那兩個(gè)頂點(diǎn)之間個(gè)環(huán)，由于這條邊依靠的那兩個(gè)頂點(diǎn)之間有了第二條途徑；有了第二條途徑；l一棵有一棵有n個(gè)頂點(diǎn)的生成樹有且僅有個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊，條邊，假設(shè)一個(gè)圖有假設(shè)一個(gè)圖有n個(gè)頂點(diǎn)和小于個(gè)頂點(diǎn)和小于n-1條邊，那條邊，那么是非連通圖存在孤立頂點(diǎn)。假設(shè)它么是非連通圖存在孤立頂點(diǎn)。假設(shè)它多于多于n-1條邊

15、，那么一定有環(huán)；條邊，那么一定有環(huán)；l但是但是n-1條邊的圖不一定是生成樹條邊的圖不一定是生成樹(why?)。由于能夠存在回路由于能夠存在回路第 21 頁生成樹的特點(diǎn)生成樹的特點(diǎn)l一個(gè)圖可以有許多棵不同的生成樹，一切生一個(gè)圖可以有許多棵不同的生成樹，一切生成樹具有如下特點(diǎn)：成樹具有如下特點(diǎn)：l1、生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)一樣；、生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)一樣；l2、生成樹是圖的極小連通子圖；、生成樹是圖的極小連通子圖；l3、一個(gè)有、一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊；條邊；l4、生成樹中恣意兩個(gè)頂點(diǎn)之間的途徑獨(dú)一；、生成樹中恣意兩個(gè)頂點(diǎn)之間的途徑獨(dú)一；

16、l5、在生成樹中添加一條邊必然構(gòu)成回路；、在生成樹中添加一條邊必然構(gòu)成回路；l6、含、含n個(gè)頂點(diǎn)個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹。條邊的圖不一定是生成樹。第 22 頁7.2 圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造一、圖的數(shù)組一、圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲(chǔ)表示存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示第 23 頁 V0 V0 V1 V1 V2 V2 V3 V37.2 7.2 圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造一、數(shù)組表示法鄰接矩陣表示一、數(shù)組表示法鄰接矩陣表示 鄰接矩陣：鄰接矩陣：G的鄰接矩陣是滿足如下條件的鄰接矩陣是滿足如下條件的的n階矩陣：階矩陣：Aij=1 假設(shè)假設(shè)(vi,vj)E 或或 E0 否那么否那么0 1 0

17、 1 00 1 0 1 00 1 0 10 1 0 10 1 0 1 10 1 0 1 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0在數(shù)組表示法中，用鄰在數(shù)組表示法中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系接矩陣表示頂點(diǎn)間的關(guān)系 V0 V0 V4 V4 V3 V3 V1 V1 V2 V20 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 10 0 00 0 0值得留意：值得留意：對無向圖，鄰接矩陣中非零元素的個(gè)數(shù)等對無向圖，鄰接矩陣中非零元素的個(gè)數(shù)等于圖的邊數(shù)乘以于圖的邊數(shù)乘以2；對有向圖，鄰接矩陣中非零元素的個(gè)數(shù)等對有向圖，鄰接矩陣中非零元素的個(gè)數(shù)等于

18、邊于邊(箭線箭線)的個(gè)數(shù)。的個(gè)數(shù)。第 24 頁第 25 頁Aij=wij 假設(shè)vi, vj 間有弧(邊)，且權(quán)值為wij0 當(dāng)vi, vj 間無弧或邊時(shí)對于帶權(quán)圖，鄰接矩陣定義為：對于帶權(quán)圖，鄰接矩陣定義為：ABECF0 6 0 9 0 0 0 2 0 0 0 0 0 0 8 0 0 1 0 0 5 3 0 0 0 A B C E FA BCEF6138295第 26 頁 鄰接矩陣類型定義鄰接矩陣類型定義#define MAX_VERTEX_NUM 20Typedef enumDG, DN, UDG, UDNGraphKind; / 有向圖，有向網(wǎng)，無向圖，無向網(wǎng)有向圖，有向網(wǎng)，無向圖，無向網(wǎng)

19、typedef struct ArcCell / 弧的定義弧的定義, 構(gòu)造數(shù)組構(gòu)造數(shù)組 VRType adj; / VRType是頂點(diǎn)關(guān)系類型是頂點(diǎn)關(guān)系類型 / 對無權(quán)圖，用對無權(quán)圖，用1或或0表示相鄰否表示相鄰否 / 對帶權(quán)圖，那么用權(quán)值或?qū)?quán)圖，那么用權(quán)值或0表示相鄰否表示相鄰否 InfoType *info; / 該弧相關(guān)信息的指針該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;第 27 頁 鄰接矩陣類型定義鄰接矩陣類型定義上述定義中，上述定義中，ArcCell是構(gòu)造類型是構(gòu)造類型, AdjMatrix是二維數(shù)組矩陣類

20、型是二維數(shù)組矩陣類型typedef struct / 圖的定義圖的定義 VertexType / VertexType為頂點(diǎn)類型，為頂點(diǎn)類型，can be int or char etc. vexsMAX_VERTEX_NUM; /頂點(diǎn)向量頂點(diǎn)向量 AdjMatrix arcs; / 鄰接矩陣鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)，弧數(shù)圖的當(dāng)前頂點(diǎn)數(shù)，弧數(shù) GraphKind kind; / 圖的種類標(biāo)志圖的種類標(biāo)志 MGraph;第 28 頁Graph G：G.vexsG.arcsv2nev110存儲(chǔ)鄰接矩陣存儲(chǔ)鄰接矩陣AG存儲(chǔ)頂點(diǎn)存儲(chǔ)頂點(diǎn)存儲(chǔ)頂點(diǎn)個(gè)數(shù)存儲(chǔ)頂點(diǎn)個(gè)

21、數(shù)存儲(chǔ)邊數(shù)存儲(chǔ)邊數(shù)存儲(chǔ)圖的類型存儲(chǔ)圖的類型G.vexnumG.arcnumG.kindAEDCB第 29 頁無向圖數(shù)組表示法特點(diǎn)無向圖數(shù)組表示法特點(diǎn)1、無向圖的鄰接矩陣為對稱矩陣、無向圖的鄰接矩陣為對稱矩陣(假設(shè)假設(shè)(vi, vj)VR那么那么 (vj, vi)VR), 只需存儲(chǔ)只需存儲(chǔ)其下三角其下三角;2、判別恣意兩個(gè)頂點(diǎn)能否為鄰接點(diǎn)、判別恣意兩個(gè)頂點(diǎn)能否為鄰接點(diǎn)(ai,j=1 or 0)；3、對無向圖，易于計(jì)算頂點(diǎn)、對無向圖，易于計(jì)算頂點(diǎn)vi的度的度(how to calculate?)AEDCB0 1 1 0 00 1 1 0 01 0 0 1 11 0 0 1 11 0 0 0 11

22、0 0 0 10 1 0 0 10 1 0 0 10 1 1 1 00 1 1 1 0第 30 頁7.2 圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造二、鄰接表：圖的鏈?zhǔn)酱鎯?chǔ)構(gòu)造二、鄰接表：圖的鏈?zhǔn)酱鎯?chǔ)構(gòu)造1、無向圖的鄰接表、無向圖的鄰接表 頂點(diǎn)：通常按編號順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在頂點(diǎn)：通常按編號順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中；一維數(shù)組中； 關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ)關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ)(商定商定下標(biāo)由小到大下標(biāo)由小到大)。 V0 V4 V3 V1 V22 0 1 2 3 4m-1V0V1V2V3V413422110034該結(jié)點(diǎn)表示邊該結(jié)點(diǎn)表示邊(V2,V4)，其中的，其中的4是是V4在一在一維數(shù)組

23、中的位置維數(shù)組中的位置第 31 頁7.2 圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造l鏈表結(jié)點(diǎn)弧結(jié)點(diǎn)鏈表結(jié)點(diǎn)弧結(jié)點(diǎn)ltypedef struct ArcNodel int adjvex; / 頂點(diǎn)的鄰接點(diǎn)域頂點(diǎn)的鄰接點(diǎn)域l / 存放與存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置鄰接的點(diǎn)在表頭數(shù)組中的位置l struct ArcNode *next; / 鏈域，下一條邊或弧鏈域，下一條邊或弧l ArcNode;l表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)ltypedef struct tnodel int vexdata; / 存放頂點(diǎn)數(shù)據(jù)信息存放頂點(diǎn)數(shù)據(jù)信息l ArcNode * firstarc; / 指向指向ArcNode類型的第類型的第一

24、個(gè)鏈表結(jié)點(diǎn)一個(gè)鏈表結(jié)點(diǎn)l VNode, AdjList MAX_VERTEX_NUM ;ltypedef structl AdjList vertices; /構(gòu)造數(shù)組構(gòu)造數(shù)組lint vexnum, arcnum; / 頂點(diǎn)數(shù)和弧頂點(diǎn)數(shù)和弧數(shù)數(shù)lint kind; / 圖的種類圖的種類lALGraph;adjvex nextvexdata firstarc第 32 頁7.2 圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造l無向圖的鄰接表的特點(diǎn)無向圖的鄰接表的特點(diǎn)l 1在在G鄰接表中，同一條邊對應(yīng)兩個(gè)結(jié)鄰接表中，同一條邊對應(yīng)兩個(gè)結(jié)點(diǎn)；點(diǎn)；l 2頂點(diǎn)頂點(diǎn)v的度：等于的度：等于v對應(yīng)線性鏈表的對應(yīng)線性鏈表的長度；長度；

25、l 3斷定兩頂點(diǎn)斷定兩頂點(diǎn)v ，u能否鄰接：要看能否鄰接：要看v對對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點(diǎn)應(yīng)線性鏈表中有無對應(yīng)的結(jié)點(diǎn)u。l 4在在G中增減邊：要在兩個(gè)相鄰頂點(diǎn)關(guān)中增減邊：要在兩個(gè)相鄰頂點(diǎn)關(guān)聯(lián)的單鏈表中插入、刪除結(jié)點(diǎn)；聯(lián)的單鏈表中插入、刪除結(jié)點(diǎn)；l 5設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為 mm圖的頂點(diǎn)數(shù)圖的頂點(diǎn)數(shù)n，圖的邊數(shù)為，圖的邊數(shù)為 e，G占占用存儲(chǔ)空間為：用存儲(chǔ)空間為：m+2*e準(zhǔn)確地應(yīng)思索數(shù)據(jù)準(zhǔn)確地應(yīng)思索數(shù)據(jù)類型。類型。G占用存儲(chǔ)空間與占用存儲(chǔ)空間與G的頂點(diǎn)數(shù)、邊的頂點(diǎn)數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖。數(shù)均有關(guān)；適用于邊稀疏的圖。第 33 頁7.2 圖的存儲(chǔ)構(gòu)造圖的

26、存儲(chǔ)構(gòu)造2、有向圖的鄰接表、有向圖的鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)按編號升序陳列頂點(diǎn)：用一維數(shù)組存儲(chǔ)按編號升序陳列以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)0123v0v2v3v1vexdatafirstarc12 3 0adjvexnext類似于無向圖的鄰接表，所不同的是：類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)V0V1V2V3第 34 頁7.2 圖的存儲(chǔ)構(gòu)造圖的存儲(chǔ)構(gòu)造3、有向圖的逆鄰接表、有向圖的逆鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)按編號升序陳列頂點(diǎn)：用一維數(shù)組存儲(chǔ)按編號升序陳列以同一頂點(diǎn)為終點(diǎn)的?。河镁€

27、性鏈表存儲(chǔ)。以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存儲(chǔ)。0123v0v2v3v1vexdatafirstarc 3 0 0 2類似于有向圖的鄰接表，所不同的是：類似于有向圖的鄰接表，所不同的是：以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存儲(chǔ)以同一頂點(diǎn)為終點(diǎn)的弧：用線性鏈表存儲(chǔ)V0V1V2V3第 35 頁7.3 圖的遍歷圖的遍歷l深度優(yōu)先遍歷深度優(yōu)先遍歷l廣度優(yōu)先遍歷廣度優(yōu)先遍歷第 36 頁7.3 圖的遍歷圖的遍歷l連通圖的深度遍歷連通圖的深度遍歷DFSl從圖中某頂點(diǎn)從圖中某頂點(diǎn)v出發(fā)：出發(fā)： l 1訪問頂點(diǎn)訪問頂點(diǎn)v； 2對對v的每個(gè)未被訪問的鄰接點(diǎn)的每個(gè)未被訪問的鄰接點(diǎn)wj，從，從wj出發(fā)，繼續(xù)對圖進(jìn)展深度

28、優(yōu)先遍歷。出發(fā)，繼續(xù)對圖進(jìn)展深度優(yōu)先遍歷。深度遍歷：深度遍歷： V1,V2,V4,V5,V8,V3,V6,V7 例例 V1 V8 V7 V6 V5 V4 V3 V2V1V2V4V3V8V7V6 V5深度遍歷：深度遍歷： V1,V3,V6,V7,V2,V5,V8,V4第 37 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷圖的深度遍歷DFSVw1SG1SG2SG3w2w3w2 W1、W2和和W3 均為均為 V 的鄰的鄰接點(diǎn)，接點(diǎn)，SG1、SG2 和和 SG3 分分別為含頂點(diǎn)別為含頂點(diǎn)W1、W2和和W3 的的子圖。子圖。訪問頂點(diǎn)訪問頂點(diǎn) V ：for (W1、W2、W3 ) 假設(shè)該鄰接點(diǎn)假設(shè)該鄰

29、接點(diǎn)Wi(i=1,2,3)未被訪問，未被訪問， 那么從它出發(fā)進(jìn)展深度優(yōu)先搜索遍歷。那么從它出發(fā)進(jìn)展深度優(yōu)先搜索遍歷。第 38 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷圖的深度遍歷DFSVw1SG1SG2SG3w2w3w2從圖解可見：從圖解可見：1. 從深度優(yōu)先搜索遍歷連通圖的從深度優(yōu)先搜索遍歷連通圖的過程看，過程看，DFS類似于樹的先根遍類似于樹的先根遍歷；歷；處理的方法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè)處理的方法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問標(biāo)志訪問標(biāo)志 visitedw。2. 如何判別如何判別V的鄰接點(diǎn)能否被訪問？的鄰接點(diǎn)能否被訪問？第 39 頁7.3 圖的遍歷圖的遍歷Boolean visi

30、tedMAX; / 訪問標(biāo)志數(shù)組訪問標(biāo)志數(shù)組Status (*VisitFunc)(int v); / 訪問函數(shù)訪問函數(shù),can be printfvoid DFS ( Graph G, int v) / 從頂點(diǎn)從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v); for ( w=FirstAdjVex(G, v); w=0; w=NextAdjVex(G,v,w) ) if ( !visitedw ) DFS(G, w); / 對對v的尚未訪問的鄰接頂點(diǎn)的尚未訪問的鄰接頂點(diǎn)w / 遞歸調(diào)用遞歸調(diào)用DFS / DFS

31、第 40 頁7.3 7.3 圖的遍歷圖的遍歷非連通圖的深度優(yōu)先搜索遍歷非連通圖的深度優(yōu)先搜索遍歷 首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為為 FALSE，之后搜索圖中每個(gè)頂點(diǎn)，假，之后搜索圖中每個(gè)頂點(diǎn)，假設(shè)未被訪問，那么以該頂點(diǎn)為起始點(diǎn)，設(shè)未被訪問，那么以該頂點(diǎn)為起始點(diǎn)，進(jìn)展深度優(yōu)先搜索遍歷，否那么繼續(xù)檢進(jìn)展深度優(yōu)先搜索遍歷，否那么繼續(xù)檢查下一頂點(diǎn)。查下一頂點(diǎn)。第 41 頁7.3 圖的遍歷圖的遍歷void DFSTraverse ( Graph G, Status (*Visit) (int v) / 對非連通圖對非連通圖 G 作深度優(yōu)先遍歷。作深度優(yōu)先遍歷。 Visit

32、Func = Visit; /函數(shù)入口地址給函數(shù)指針函數(shù)入口地址給函數(shù)指針 for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 訪問標(biāo)志數(shù)組初始化訪問標(biāo)志數(shù)組初始化 for ( v=0; vG.vexnum; +v ) if (!visitedv) DFS(G, v); / 對尚未訪問的頂點(diǎn)調(diào)用對尚未訪問的頂點(diǎn)調(diào)用DFS第 42 頁7.3 7.3 圖的遍歷圖的遍歷例如：例如：abchdekfgF F F F F F F F FTTTTTTTTTachdkfe bgachkfedbg訪問標(biāo)志訪問標(biāo)志: :訪問次序訪問次序: : a b c d e f g

33、 h k 0 1 2 3 4 5 6 7 8第 43 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷圖的深度遍歷DFS算法算法7.4和和7.5開場開場訪問訪問V，置標(biāo)志，置標(biāo)志求求V鄰接點(diǎn)鄰接點(diǎn)有鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)求下一鄰接點(diǎn)W訪問過訪問過終了終了NYNYDFS(G,w)開場開場標(biāo)志數(shù)組初始化標(biāo)志數(shù)組初始化V=0V訪問過訪問過?DFS(g,v)V=V+1VVexNum終了終了NYYN第 44 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷圖的深度遍歷DFS遞歸算法遞歸算法V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvex

34、next55 6 4 8 2678678 7深度遍歷：深度遍歷：V1V3 V7 V6 V2 V4 V8 V5第 45 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷圖的廣度遍歷BFSl 從圖的某一頂點(diǎn)從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次出發(fā)，訪問此頂點(diǎn)后，依次訪問訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中一切已被訪鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中一切已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；假設(shè)此時(shí)圖中尚有頂問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)未被訪問

35、，那么另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，反復(fù)上述過程，直至圖中一切頂點(diǎn)都被訪問為止。點(diǎn)，反復(fù)上述過程，直至圖中一切頂點(diǎn)都被訪問為止。V1V2V4V5V3V7V6V8例例廣度遍歷：廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8第 46 頁7.3 圖的遍歷圖的遍歷l圖的廣度遍歷圖的廣度遍歷BFSl 從圖中的某個(gè)頂點(diǎn)從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問此頂出發(fā)，并在訪問此頂點(diǎn)之后依次訪問點(diǎn)之后依次訪問V0的一切未被訪問過的鄰接點(diǎn)，的一切未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中一切和們的鄰接點(diǎn)，直至圖中一切和V0有

36、途徑相通的有途徑相通的頂點(diǎn)都被訪問到。頂點(diǎn)都被訪問到。 假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么另選圖中一個(gè)未曾被訪問的假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，反復(fù)上述過程，直至圖中一切頂點(diǎn)都被訪問到為止。頂點(diǎn)作起始點(diǎn)，反復(fù)上述過程，直至圖中一切頂點(diǎn)都被訪問到為止。第 47 頁7.3 圖的遍歷圖的遍歷l圖的廣度遍歷圖的廣度遍歷BFSl從圖中某頂點(diǎn)從圖中某頂點(diǎn)v出發(fā)：出發(fā)：l1) 訪問頂點(diǎn)訪問頂點(diǎn)vl2) 訪問訪問v的一切未被訪問的鄰接點(diǎn)的一切未被訪問的鄰接點(diǎn)w1,w2,wkl3) 依次從這些鄰接點(diǎn)出發(fā)，訪問它們的一依次從這些鄰接點(diǎn)出發(fā)，訪問它們的一切未被訪問的鄰接點(diǎn)，

37、直到圖中一切訪問過的切未被訪問的鄰接點(diǎn)，直到圖中一切訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問到。頂點(diǎn)的鄰接點(diǎn)都被訪問到。V1V8V7V6V5V4V3V2V1 V2 V4 V3 V8 V7 V6 V5V1,V2,V3,V4,V8,V5,V6,V7V1,V3,V2,V6,V7,V4,V5,V8第 48 頁7.3 圖的遍歷圖的遍歷void BFSTraverse ( Graph G, Status (*Visit) (int v) ) for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 初始化訪問標(biāo)志初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列置空的輔

38、助隊(duì)列Q for ( v=0; v=0; w=NextAdjVex(G,u,w) ) if ( ! visitedw ) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點(diǎn)訪問的頂點(diǎn)w入隊(duì)列入隊(duì)列 / if / while第 50 頁7.3 圖的遍歷圖的遍歷l圖的廣度遍歷圖的廣度遍歷BFS例例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：遍歷序列：10 1 2 3 4 54fr遍歷序列：遍歷序列：1 40 1 2 3 4 54 3f

39、r遍歷序列：遍歷序列：1 4 3第 51 頁7.3 圖的遍歷圖的遍歷l圖的廣度遍歷圖的廣度遍歷BFS例例142350 1 2 3 4 54 3 2fr遍歷序列：遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序列：遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：遍歷序列：1 4 3 2 512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 2第 52 頁7.3 圖的遍歷圖的遍歷l圖的廣度遍歷圖的廣度遍歷BFS例例142350 1 2 3 4 5 2 5fr遍歷序列：遍歷序列：1 4 3 2 5

40、0 1 2 3 4 5 5fr遍歷序列：遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：遍歷序列：1 4 3 2 512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 2第 53 頁7.4 圖的最小生成樹圖的最小生成樹l問題提出問題提出l要在要在n個(gè)城市間建立通訊聯(lián)絡(luò)網(wǎng)：個(gè)城市間建立通訊聯(lián)絡(luò)網(wǎng)：l頂點(diǎn)頂點(diǎn)表示城市；表示城市；l權(quán)權(quán)城市間建立通訊線路所需破費(fèi)的代價(jià)；城市間建立通訊線路所需破費(fèi)的代價(jià)；l希望找到一棵生成樹，使它的每條邊上的權(quán)值之和希望找到一棵生成樹，使它的每條邊上的權(quán)值之和即建立該通訊網(wǎng)所需破費(fèi)的總代

41、價(jià)最小即建立該通訊網(wǎng)所需破費(fèi)的總代價(jià)最小此即此即最小代價(jià)生成樹。最小代價(jià)生成樹。l問題分析問題分析ln個(gè)城市間，最多可設(shè)置個(gè)城市間，最多可設(shè)置 n(n-1)/2 條線路，條線路，如全部布線代價(jià)太高；如全部布線代價(jià)太高；ln個(gè)城市間建立通訊網(wǎng)，只需個(gè)城市間建立通訊網(wǎng)，只需 n-1 條線路即條線路即可。可。l問題轉(zhuǎn)化為：如何在能夠的線路中選擇問題轉(zhuǎn)化為：如何在能夠的線路中選擇 n-1 條，能條，能把一切城市頂點(diǎn)均連起來，且總耗費(fèi)各邊權(quán)值把一切城市頂點(diǎn)均連起來，且總耗費(fèi)各邊權(quán)值之和最小。之和最小。第 54 頁問題分析：問題分析：l可用連通圖表示可用連通圖表示n個(gè)城市以及個(gè)城市以及n個(gè)城市間能夠個(gè)城市

42、間能夠的通訊線路，其中圖的頂點(diǎn)表示城市，便表的通訊線路，其中圖的頂點(diǎn)表示城市，便表示兩城市之間的線路，邊的權(quán)值表示該段線示兩城市之間的線路，邊的權(quán)值表示該段線路的代價(jià)。對于路的代價(jià)。對于n個(gè)頂點(diǎn)的連通圖可以建立許個(gè)頂點(diǎn)的連通圖可以建立許多不同的生成樹，每一棵生成樹都可以是一多不同的生成樹，每一棵生成樹都可以是一個(gè)通訊網(wǎng)。如今，要選擇一棵生成樹，使得個(gè)通訊網(wǎng)。如今，要選擇一棵生成樹，使得總耗費(fèi)最少。這就是構(gòu)造連通圖的最小代價(jià)總耗費(fèi)最少。這就是構(gòu)造連通圖的最小代價(jià)生成樹生成樹Minimum Cost Spanning Tree，簡稱最小生成樹簡稱最小生成樹MST的問題。一棵生成樹的問題。一棵生成樹

43、的代價(jià)就是樹上各邊的代價(jià)之和。的代價(jià)就是樹上各邊的代價(jià)之和。l構(gòu)造圖的最小生成樹的兩種算法：構(gòu)造圖的最小生成樹的兩種算法：第 55 頁7.4 圖的最小生成樹圖的最小生成樹Prim算法的根本思想：算法的根本思想： 取圖中恣意一個(gè)頂點(diǎn)取圖中恣意一個(gè)頂點(diǎn) v 作為生成樹作為生成樹的根，之后往生成樹上添加新的頂點(diǎn)的根，之后往生成樹上添加新的頂點(diǎn) w。 在添加的頂點(diǎn)在添加的頂點(diǎn) w 和曾經(jīng)在生成樹上和曾經(jīng)在生成樹上的頂點(diǎn)的頂點(diǎn) v 之間必定存在一條邊，并且該之間必定存在一條邊，并且該邊的權(quán)值在一切連通頂點(diǎn)邊的權(quán)值在一切連通頂點(diǎn) v 和和 w 之間的之間的邊中取值最小。邊中取值最小。 之后繼續(xù)往生成樹上添

44、加頂點(diǎn)，直之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有至生成樹上含有n個(gè)頂點(diǎn)、個(gè)頂點(diǎn)、n-1條邊條邊為止。為止。第 56 頁7.4 圖的最小生成樹圖的最小生成樹普里姆算法普里姆算法Prim設(shè)設(shè) G=V，GE為一個(gè)具有為一個(gè)具有 n 個(gè)頂個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，點(diǎn)的連通網(wǎng)絡(luò)，T=U，TE為構(gòu)造的生成為構(gòu)造的生成樹。樹。1初始時(shí)，初始時(shí)，U = u0，TE = ；2在一切在一切 uU 、vV-U 的邊的邊u,v中選擇一條權(quán)值最小的邊，無妨設(shè)為中選擇一條權(quán)值最小的邊，無妨設(shè)為u,v；3(u,v) 參與參與TE，同時(shí)將，同時(shí)將 v 參與參與U(留意這時(shí)留意這時(shí)U集合變大、集合變大、V-U變小了，實(shí)踐上變小了

45、，實(shí)踐上是按照選擇是按照選擇U集合與集合與V-U集合關(guān)聯(lián)的最小權(quán)的集合關(guān)聯(lián)的最小權(quán)的邊，向邊，向U中添加頂點(diǎn)中添加頂點(diǎn))；4反復(fù)反復(fù)(2)(3)，直到，直到 U=V 為止；為止；UV-U vu U擴(kuò)展擴(kuò)展V-U減少減少vu 第 57 頁7.4 7.4 圖的最小生成樹圖的最小生成樹普里姆算法普里姆算法Prim教材教材P175V3V3V1V1V4V4V6V6V5V5V2V23 36 65 52 21 16 65 55 54 46 6V3V3V1V1V4V4V6V6V5V5V2V21 12 2V3V3V1V1V4V4V6V6V5V5V2V21 14 4V3V3V1V1V4V4V6V6V5V5V2V2

46、1 14 42 2V3V3V1V1V4V4V6V6V5V5V2V21 14 45 52 2V3V3V1V1V4V4V6V6V5V5V2V21 14 45 53 3U= V1 U= V1 U= V1,V3 U= V1,V3 U= V1,V3,V6U= V1,V3,V6U= V1,V3,V6,V4 U= V1,V3,V6,V4 U= V1,V3,V6,V4,V2 U= V1,V3,V6,V4,V2 U= V1,V3,V6,V4,V2,V5 U= V1,V3,V6,V4,V2,V5 Question：從不同的頂點(diǎn)出發(fā)：從不同的頂點(diǎn)出發(fā)構(gòu)造的最小生成樹能否獨(dú)一？構(gòu)造的最小生成樹能否獨(dú)一？第 58 頁7

47、.4 7.4 圖的最小生成樹圖的最小生成樹l克魯斯卡爾克魯斯卡爾(Kruskal)算法算法l 思索問題的出發(fā)點(diǎn)：為使生成樹思索問題的出發(fā)點(diǎn)：為使生成樹上邊的權(quán)值之和到達(dá)最小，那么應(yīng)使生上邊的權(quán)值之和到達(dá)最小，那么應(yīng)使生成樹中每一條邊的權(quán)值盡能夠地小。成樹中每一條邊的權(quán)值盡能夠地小。 詳細(xì)做法：先構(gòu)造一個(gè)只含詳細(xì)做法：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖個(gè)頂點(diǎn)的子圖SG，然后從權(quán)，然后從權(quán)值最小的邊開場，假設(shè)它的添加不使值最小的邊開場，假設(shè)它的添加不使SG中產(chǎn)生回路，那么在中產(chǎn)生回路，那么在SG 中加上這條邊，如此反復(fù)，直至加到中加上這條邊，如此反復(fù)，直至加到n-1條邊為止。條邊為止。第 59 頁KruskalKruskal算法的例子算法的例子V3V3V1V1V4V4V6V6V5V5V