第7章數(shù)據(jù)結構 圖

1、1第七章第七章 圖圖F本章主要內(nèi)容本章主要內(nèi)容7.1 基本概念和術語基本概念和術語7.2 圖的存儲結構圖的存儲結構7.3 圖的遍歷圖的遍歷&圖的應用圖的應用7.4 最小代價生成樹最小代價生成樹7.5 拓撲排序、關鍵路徑拓撲排序、關鍵路徑7.6 最短路徑最短路徑27.1 基本術語基本術語 圖是頂點集和邊集組成的二元組圖是頂點集和邊集組成的二元組G=,E中每條邊是中每條邊是V中一對頂點中一對頂點(u,v)間的聯(lián)系間的聯(lián)系,如果是無序?qū)?，那么稱該圖如果是無序?qū)?，那么稱該圖為為無向圖無向圖，否則為，否則為有向圖有向圖。q完全圖、稠密圖和稀疏圖、子圖完全圖、稠密圖和稀疏圖、子圖q鄰接點鄰接點及及

2、關聯(lián)邊關聯(lián)邊鄰接點：邊的兩個頂點互為鄰接點鄰接點：邊的兩個頂點互為鄰接點關聯(lián)邊：若有邊關聯(lián)邊：若有邊e= (v, u), e= (v, u), 則稱頂點則稱頂點v v、u u關聯(lián)邊關聯(lián)邊e ep網(wǎng)網(wǎng)：在圖中賦予每條邊或弧一定的權值，這種帶權的：在圖中賦予每條邊或弧一定的權值，這種帶權的圖稱為網(wǎng)。圖稱為網(wǎng)。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V337.1 基本術語基本術語(續(xù)續(xù))q頂點的度、入度和出度頂點的度、入度和出度頂點頂點V V的度的度 = = 與與V V相關聯(lián)的邊的數(shù)目相關聯(lián)的邊的數(shù)目在有向圖中：在有向圖中： 頂點頂點V V的出度的出度

3、= = 以以V V為起點有向邊數(shù)為起點有向邊數(shù) 頂點頂點V V的入度的入度 = = 以以V V為終點有向邊數(shù)為終點有向邊數(shù) 頂點頂點V V的度的度 = V= V的出度的出度+V+V的入度的入度設圖設圖G G的頂點數(shù)為的頂點數(shù)為n n，邊數(shù)為，邊數(shù)為e e 圖的所有頂點的度數(shù)之和圖的所有頂點的度數(shù)之和 = 2= 2* *e e （每條邊對圖的所有頂點的度數(shù)和（每條邊對圖的所有頂點的度數(shù)和“貢獻貢獻”2 2度度） V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V347.1 基本術語基本術語(續(xù)續(xù))q路徑、回路路徑、回路在圖在圖G=中，若有中，若有頂點序列頂點序

4、列v v1 1,v,v2 2, , ,v ,vk k, ,且且v E(E(有向圖有向圖) )或或(v(vi i,v,vi+1i+1) ) E(E(無向圖無向圖) )，其中其中i=1,2,i=1,2,k-1,v=vk-1,v=v1 1,u=v,u=vk k，則稱該序列是從頂，則稱該序列是從頂點點v v到頂點到頂點u u的的路徑路徑；若；若v=uv=u，則稱該序列為，則稱該序列為回路回路。q簡單路徑、簡單回路簡單路徑、簡單回路在一條路徑中在一條路徑中, , 除起點和終點外除起點和終點外, ,若其余頂點各若其余頂點各不相同不相同, ,則稱該路徑為則稱該路徑為簡單路徑簡單路徑。由簡單路徑組成的回路稱為

5、由簡單路徑組成的回路稱為簡單回路簡單回路。例如在上面的無向圖中，例如在上面的無向圖中，V0,V1,V2,V3V0,V1,V2,V3是簡單路徑是簡單路徑V0,V1,V2,V4,V1V0,V1,V2,V4,V1不是簡單路徑；在上面的有向圖中，不是簡單路徑；在上面的有向圖中，V0,V2,V3,V0V0,V2,V3,V0是簡單回路。是簡單回路。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V357.1 基本術語基本術語(續(xù)續(xù))q連通圖、強連通圖連通圖、強連通圖 在無（有）向圖在無（有）向圖G=G=中，若對任何兩個頂點中，若對任何兩個頂點u、v都存都存在從在從u到

6、到v的路徑，則稱的路徑，則稱G G是連通圖是連通圖( (強連通圖強連通圖) )。(b)(b)非連通圖非連通圖 V0V0 V1V1 V2V2 V3V3(c)(c)強連通圖強連通圖(a)(a)連通圖連通圖V0V0V3V3V2V2V1V1V4V4V5V5(d)(d)非強連通圖非強連通圖 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V367.1 基本術語基本術語(續(xù)續(xù))q連通分量、強連通圖分量連通分量、強連通圖分量 在無（有）向圖在無（有）向圖G=G=中，若對任何兩個頂點中，若對任何兩個頂點u、v都存都存在從在從u到到v的路徑，則稱的路徑，則稱G G是連通圖是連

7、通圖( (強連通圖強連通圖) )。無（有）向。無（有）向圖的極大連通子圖稱為圖的連通分量（強連通分量）圖的極大連通子圖稱為圖的連通分量（強連通分量）非連通圖，有兩個連通分量非連通圖，有兩個連通分量 V0V0 V1V1 V2V2 V3V3非強連通圖非強連通圖 V0V0 V1V1 V2V2 V3V3有兩個強連通分量有兩個強連通分量V0V0V3V3V2V2V1V1V4V4V5V577.1 基本術語基本術語(續(xù)續(xù))q生成樹生成樹一個連通圖的生成樹是一個一個連通圖的生成樹是一個極小極小連通子圖，它含有圖中全連通子圖，它含有圖中全部頂點，但只有足以構成一棵樹的部頂點，但只有足以構成一棵樹的n-1n-1條邊

8、。條邊。(a)(a)連通圖連通圖G1G1 V0V0 V4V4 V3V3 V1V1 V2V2(b)(b)連通圖連通圖G1G1的一個生成樹的一個生成樹 V0V0 V4V4 V3V3 V1V1 V2V287.1 基本術語基本術語(續(xù)續(xù))：無向圖及其生成樹：無向圖及其生成樹V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5無向圖G97.1 基本術語基本術語(續(xù)續(xù))：賦權圖：賦權圖54613241510215203041010107.1 基本術語基本術語(續(xù)續(xù))：有向圖的強連通子圖：有向圖的強連通子圖5461324151021520304101013241522054611 例例1

9、 1 交通圖（公路、鐵路）交通圖（公路、鐵路） 頂點：地點頂點：地點 邊：連接地點的公路邊：連接地點的公路 交通圖中的有單行道雙行道，分別用有向邊、無向邊表示交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；圖的應用示例圖的應用示例 例例2 2 電路圖電路圖 頂點：元件頂點：元件 邊：連接元件之間的線路邊：連接元件之間的線路 例例3 3 通訊線路圖通訊線路圖 頂點：地點頂點：地點 邊：地點間的連線邊：地點間的連線 例例4 4 各種流程圖各種流程圖 如如產(chǎn)品的生產(chǎn)流程圖產(chǎn)品的生產(chǎn)流程圖 頂點：工序頂點：工序 邊：各道工序之間的順序關系邊：各道工序之間的順序關系 V0V0 V4V4 V3V3 V

10、1V1 V2V2 V0V0 V1V1 V2V2 V3V3127.2 7.2 圖的存儲結構圖的存儲結構圖的存儲結構圖的存儲結構至少要保存兩類信息：至少要保存兩類信息： 1)1)頂點的數(shù)據(jù)頂點的數(shù)據(jù) 2)2)頂點間的關系頂點間的關系約定約定: : G= G=是圖是圖, , V= V=v v0 0,v,v1 1,v,v2 2, , v vn-1n-1 , ,設頂點的設頂點的 角標角標為它的編號為它的編號 如何表示頂點間的關系？如何表示頂點間的關系？ V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3137.2.1 7.2.1 圖的數(shù)組表示法圖的數(shù)組表示法在數(shù)組表

11、示法中，在數(shù)組表示法中，用鄰接矩陣表示頂點間的關系用鄰接矩陣表示頂點間的關系Aij=Aij=1 1 頂點頂點v vi i與與v vj j間有邊間有邊( (弧弧) )0 0 頂點頂點v vi i與與v vj j間無邊間無邊( (弧弧) )0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 12 20 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 V2V

12、2 V3V3147.2.1(7.2.1(續(xù)續(xù)) )數(shù)組表示法的類型定義數(shù)組表示法的類型定義#define MaxVnum 50typedef double AdjMatrixMaxVnumMaxVnum; typedef struct VertexType vexsMaxVnum; /頂點向量頂點向量 AdjMatrix arcs; /鄰接矩陣鄰接矩陣 int vexnum,arcnum; /圖的當前頂點數(shù)和邊數(shù)圖的當前頂點數(shù)和邊數(shù)Graph;Graph G;151 1）無向圖的鄰接矩陣是無向圖的鄰接矩陣是對稱矩陣對稱矩陣，同一條邊表示了兩次；，同一條邊表示了兩次；2）頂點頂點v的度：等于二維

13、數(shù)組對應行（或列）中值為的度：等于二維數(shù)組對應行（或列）中值為1的元素個數(shù)；的元素個數(shù)；3 3）判斷兩頂點判斷兩頂點v v、u u是否為鄰接點：只需判二維數(shù)組對應分量是否為是否為鄰接點：只需判二維數(shù)組對應分量是否為1 14 4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應分量賦值頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應分量賦值1 1或清或清0 0；5 5）設圖的頂點數(shù)為設圖的頂點數(shù)為 n ,n ,用有用有n n個元素的一維數(shù)組存儲圖的頂點個元素的一維數(shù)組存儲圖的頂點, ,用鄰接用鄰接矩陣表示邊矩陣表示邊, ,則則G G占用的存儲空間為：占用的存儲空間為：n+nn+n2 2；圖的圖的

14、存儲空間占用量只與存儲空間占用量只與它的頂點數(shù)有關它的頂點數(shù)有關，與邊數(shù)無關；適用于邊稠密的圖；，與邊數(shù)無關；適用于邊稠密的圖；0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 12 20 1 0 00 1 0 00 1 1 0 00 1 1 0 07.2.1(7.2.1(續(xù)續(xù)) )數(shù)組表示法的特點數(shù)組表示法的特點 V0V0 V4V4 V3V3 V1V1 V2V2160) 0) 有向圖的鄰接矩陣不一定是對稱的；有向圖的鄰接矩陣不一定是對稱的；1) 頂點頂點v的出度：等于二維數(shù)組對應行中值為的出度：等于二維數(shù)組對應行中值為1的元素個數(shù)；的元素

15、個數(shù)；2）頂點頂點v的入度：等于二維數(shù)組對應列中值為的入度：等于二維數(shù)組對應列中值為1的元素個數(shù)；的元素個數(shù)；7.2.1(7.2.1(續(xù)續(xù)) )數(shù)組表示法的特點數(shù)組表示法的特點0 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0 V0V0 V1V1 V2V2 V3V3177.2.1(7.2.1(續(xù)續(xù)) ) 網(wǎng)的數(shù)組表示法網(wǎng)的數(shù)組表示法8273496221V32V2V4V1V6V5 8 7 4 9 8 2 1 2 3 2 7 1 3 2 4 2 6 9 2 2 6 1234561 2 3 4 5 6187.2.2 7.2.2 圖的鄰接表存

16、儲結構圖的鄰接表存儲結構例例 V0V0 V4V4 V3V3 V1V1 V2V2下標下標v01v1v2v3v43 024 134 02 12 01234v在鄰接表表示法中在鄰接表表示法中頂點頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中關聯(lián)同一頂點的關聯(lián)同一頂點的邊邊：用線性鏈表存儲：用線性鏈表存儲該結點表示邊（該結點表示邊（V0,V1V0,V1）, ,其中的其中的1 1是是V1V1的序號，即的序號，即一維數(shù)組中的下標。一維數(shù)組中的下標。197.2.2(7.2.2(續(xù)續(xù)) ) 網(wǎng)的鄰接鏈表表示網(wǎng)的鄰接鏈表表示8273496221V32V2V4V1V6V5

17、表頭頂點的表頭頂點的鄰接頂點編號鄰接頂點編號和邊相關和邊相關的信息的信息指向下一個指向下一個鄰接頂點的指針鄰接頂點的指針(a) 表結點結構表結點結構(c) 鄰接鏈表鄰接鏈表12345628546947183241225262431721336214663219425632V1V2V3V4V5V6頂點數(shù)據(jù)頂點數(shù)據(jù)指向第一個指向第一個鄰接頂點的指針鄰接頂點的指針(b) 頭結點結構頭結點結構207.2.2(7.2.2(續(xù)續(xù)) ) 鄰接表的類型定義鄰接表的類型定義typedef struct VertexType data; ArcNode *firstarc;AdjListMaxVnum; ;typ

18、edef struct ArcNode int adjvex; double weight; struct ArcNode *nextarc;ArcNode;表頭頂點的表頭頂點的鄰接頂點編號鄰接頂點編號和邊相關和邊相關的信息的信息指向下一個指向下一個鄰接頂點的指針鄰接頂點的指針(a) 表結點結構表結點結構頂點數(shù)據(jù)頂點數(shù)據(jù)指向第一個指向第一個鄰接頂點的指針鄰接頂點的指針(b) 頭結點結構頭結點結構217.2.2(7.2.2(續(xù)續(xù)) ) 圖的鄰接表表示圖的鄰接表表示typedef struct VertexType data; ArcNode *firstarc;AdjListMaxVnum; ;

19、 typedef struct ArcNode int adjvex; double weight; struct ArcNode *nextarc;ArcNode;表頭頂點的表頭頂點的鄰接頂點編號鄰接頂點編號和邊相關和邊相關的信息的信息指向下一個指向下一個鄰接頂點的指針鄰接頂點的指針(a) 表結點結構表結點結構頂點數(shù)據(jù)頂點數(shù)據(jù)指向第一個指向第一個鄰接頂點的指針鄰接頂點的指針(b) 頭結點結構頭結點結構typedef struct int vexnum,arcnum; AdjList vertices;AGraph; AGraph G; 227.2.2(7.2.2(續(xù)續(xù)) ) 有向圖的鄰接表表

20、示有向圖的鄰接表表示例例下標下標v01v1v2v32 3 0 0123v在鄰接表表示中在鄰接表表示中頂點頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中以同一頂點為以同一頂點為起點起點的弧的?。河镁€性鏈表存儲：用線性鏈表存儲 V0V0 V1V1 V2V2 V3V3237.2.2(7.2.2(續(xù)續(xù)) )有向圖的逆鄰接表表示有向圖的逆鄰接表表示例例v在逆鄰接表表示中在逆鄰接表表示中頂點頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中以同一頂點為以同一頂點為終點終點的弧的?。河镁€性鏈表存儲：用線性鏈表存儲 V0V0 V1

21、V1 V2V2 V3V3下標下標v0v1v2v33 0 2 01230 247.2.3 7.2.3 有向圖的十字鏈表表示有向圖的十字鏈表表示v將有向圖的鄰接表和逆鄰接表結合起來得到的鏈表。將有向圖的鄰接表和逆鄰接表結合起來得到的鏈表。v在十字鏈表中，在十字鏈表中，頂點結點頂點結點存儲數(shù)據(jù)元素，存儲數(shù)據(jù)元素，弧結點弧結點存儲弧及其上的信息。存儲弧及其上的信息。 V0V0 V1V1 V2V2 V3V3v0v1v2v30012310 22 030313223鄰接鏈表鄰接鏈表tailvex headvexhlinktlinkinfo弧結點弧結點datafirstinfirstout頂點結點頂點結點25

22、7.2.3(7.2.3(續(xù)續(xù)) )有向圖的十字鏈表表示有向圖的十字鏈表表示v0v1v2v30012310 22 030313223逆鄰接鏈表逆鄰接鏈表 V0V0 V1V1 V2V2 V3V3v將有向圖的鄰接表和逆鄰接表結合起來得到的鏈表。將有向圖的鄰接表和逆鄰接表結合起來得到的鏈表。v在十字鏈表中，在十字鏈表中，頂點結點頂點結點存儲數(shù)據(jù)元素，存儲數(shù)據(jù)元素，弧結點弧結點存儲弧及其上的信息。存儲弧及其上的信息。267.2.3(7.2.3(續(xù)續(xù)) )有向圖的十字鏈表表示有向圖的十字鏈表表示v0v1v2v30012310 22 030313223十字鏈表十字鏈表 V0V0 V1V1 V2V2 V3V3

23、v將有向圖的鄰接表和逆鄰接表結合起來得到的鏈表。將有向圖的鄰接表和逆鄰接表結合起來得到的鏈表。v在十字鏈表中，在十字鏈表中，頂點結點頂點結點存儲數(shù)據(jù)元素，存儲數(shù)據(jù)元素，弧結點弧結點存儲弧及其上的信息。存儲弧及其上的信息。277.2.4 7.2.4 無向圖的鄰接多重表表示無向圖的鄰接多重表表示v無向圖的鄰接多重表表示中，無向圖的鄰接多重表表示中，每條邊只表示一次每條邊只表示一次。v0v1v2v30123010 3 （v0,v1）（v0,v3） V0V0 V4V4 V3V3 V1V1 V2V221v442341 42 markivexilinkjvexjlink(vi,vj)287.2.4(7.2

24、.4(續(xù)續(xù)) ) 無向圖的鄰接多重表表示無向圖的鄰接多重表表示v無向圖的鄰接多重表表示中，每條邊只表示一次。無向圖的鄰接多重表表示中，每條邊只表示一次。v0v1v2v30123010 3 （v0,v1）（v0,v3） V0V0 V4V4 V3V3 V1V1 V2V221v442341 42 markivexilinkjvexjlink(vi,vj)297.3 圖的遍歷圖的遍歷q從圖的某個頂點出發(fā)，訪問圖中的所有頂點，且從圖的某個頂點出發(fā)，訪問圖中的所有頂點，且使每個頂點僅被訪問一次。這一過程叫做圖的遍使每個頂點僅被訪問一次。這一過程叫做圖的遍歷。歷。q圖的遍歷操作是求解圖的連通性問題、拓撲排序

25、圖的遍歷操作是求解圖的連通性問題、拓撲排序等問題的基礎。等問題的基礎。q遍歷方法遍歷方法: :深度優(yōu)先遍歷和廣度優(yōu)先遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷307.3.1 深度優(yōu)先搜索深度優(yōu)先搜索(DFS)從頂點從頂點v1出發(fā)進行出發(fā)進行DFS遍歷遍歷V3V2V4V1V6V5V8V7V1V2V4V5V8V3V6V7317.3.1(續(xù)續(xù)) 深度優(yōu)先搜索深度優(yōu)先搜索(DFS)q深度優(yōu)先遍歷圖的方法是，從圖中某頂點深度優(yōu)先遍歷圖的方法是，從圖中某頂點v v出發(fā)：出發(fā)： (1)(1)訪問頂點訪問頂點v v；(2)(2)依次從依次從v v的未被訪問的鄰接點出發(fā)，對圖進行的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷

26、；直至圖中和深度優(yōu)先遍歷；直至圖中和v v有路徑相通的頂點有路徑相通的頂點都被訪問；都被訪問；(3)(3)若此時圖中尚有頂點未被訪問，則從一個未被若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止。到圖中所有頂點均被訪問過為止。327.3.1(續(xù)續(xù)) 深度優(yōu)先搜索深度優(yōu)先搜索(DFS)q深度優(yōu)先遍歷過程是遞歸的，在遍歷過程中，若深度優(yōu)先遍歷過程是遞歸的，在遍歷過程中，若某個頂點的所有鄰接頂點均被訪問過，則需要回某個頂點的所有鄰接頂點均被訪問過，則需要回溯。溯。V1V2V4V5V8V3V6V7V1V

27、5V2V4V2V8V1V7V3V3V6337.3.1(續(xù)續(xù)) 深度優(yōu)先搜索深度優(yōu)先搜索(DFS)int visitedMAX; /訪問標志數(shù)組訪問標志數(shù)組void DFSTraverse(Graph G) for(v=0;vG.vexnum;+v) visitedv = false; for(v=0;vadjvex=0) DFS(G, p-adjvex); /*若若p-adjvex頂點未訪問頂點未訪問,遞歸訪問它遞歸訪問它*/ p=p-nextarc; /*p指向頂點指向頂點v的下一條弧的弧頭結點的下一條弧的弧頭結點*/ 7.3.1(續(xù)續(xù)) 深度優(yōu)先搜索深度優(yōu)先搜索(DFS)357.3.2 廣

28、度優(yōu)先搜索廣度優(yōu)先搜索BFSV3V2V4V1V6V5廣度優(yōu)先遍歷廣度優(yōu)先遍歷V3V2V4V1V6V5367.3.2(續(xù)續(xù)) 廣度優(yōu)先搜索廣度優(yōu)先搜索(BFS)從頂點從頂點v1出發(fā)進行出發(fā)進行BFS遍歷遍歷V3V2V4V1V6V5V8V7V1V2V4V8V5V3V6V7377.3.2(續(xù)續(xù)) 廣度優(yōu)先搜索廣度優(yōu)先搜索(BFS)q從圖中某頂點從圖中某頂點v vi i出發(fā)：出發(fā)： 訪問頂點訪問頂點v vi i ； 訪問訪問v vi i 的所有未被訪問的鄰接點的所有未被訪問的鄰接點w w1 1 ,w ,w2 2 , , w wk k ； 依次從這些鄰接點（在步驟依次從這些鄰接點（在步驟中訪問的頂點）出

29、發(fā)，中訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點訪問它們的所有未被訪問的鄰接點; ; 依此類推，直到依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；圖中所有訪問過的頂點的鄰接點都被訪問；q為實現(xiàn)為實現(xiàn)，需要保存在步驟，需要保存在步驟中訪問的頂點，而且中訪問的頂點，而且訪問這訪問這些頂點的些頂點的鄰接點鄰接點的順序為：先保存的頂點，其鄰接點先被的順序為：先保存的頂點，其鄰接點先被訪問。訪問。38Void BFSTraverse(ALGraph G) for (v=0; vG.vexnum; +v) visitedv = FALSE ; InitQueue(Q); for(v=0; va

30、djvex) visitedp-adjvex=1; printf(%d , p-adjvex); EnQueue(Q, p-adjvex); /if p=p-nextarc; /while(p) /while(!Queue) /if(!visite) /for V3V2V4V1V6V5V8V739算法分析算法分析n圖中每個頂點至多入隊一次，因此外循環(huán)次數(shù)為圖中每個頂點至多入隊一次，因此外循環(huán)次數(shù)為n。n當圖當圖G采用鄰接表方式存儲，則當結點采用鄰接表方式存儲，則當結點v出隊后，內(nèi)循環(huán)出隊后，內(nèi)循環(huán)次數(shù)等于結點次數(shù)等于結點v的度。由于訪問所有頂點的鄰接點的總的的度。由于訪問所有頂點的鄰接點的總的

31、時間復雜度為時間復雜度為O(d0+d1+d2+dn-1)=O(e)， 因此圖因此圖采用鄰接表方式存儲，廣度優(yōu)先搜索算法的時間復雜度為采用鄰接表方式存儲，廣度優(yōu)先搜索算法的時間復雜度為O(n+e)；n當圖當圖G采用鄰接矩陣方式存儲，由于找每個頂點的鄰接點采用鄰接矩陣方式存儲，由于找每個頂點的鄰接點時，內(nèi)循環(huán)次數(shù)等于時，內(nèi)循環(huán)次數(shù)等于n，因此廣度優(yōu)先搜索算法的時間復，因此廣度優(yōu)先搜索算法的時間復雜度為雜度為O(n2)。 407.4 圖的連通性圖的連通性q利用圖的遍歷運算求解圖的連通性問題利用圖的遍歷運算求解圖的連通性問題F無向圖是否連通、有幾個連通分量，求解無向無向圖是否連通、有幾個連通分量，求解

32、無向圖的所有連通分量圖的所有連通分量深度優(yōu)先生成樹、生成森林深度優(yōu)先生成樹、生成森林廣度優(yōu)先生成樹、生成森林廣度優(yōu)先生成樹、生成森林F有向圖是否是強連通、求解其強連通分量有向圖是否是強連通、求解其強連通分量q求無向網(wǎng)的最小代價生成樹求無向網(wǎng)的最小代價生成樹41回顧：無向圖及其生成樹回顧：無向圖及其生成樹V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5無向圖G427.4.3 最小代價生成樹最小代價生成樹q生成樹的代價等于其邊上的權值之和。生成樹的代價等于其邊上的權值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V5

33、1253443普里姆普里姆(Prim)算法算法q假設假設N=(VN=(V，E)E)是連通網(wǎng)，是連通網(wǎng)，TETE是是N N上最小生成樹中邊的集上最小生成樹中邊的集合。合。q算法從算法從U=uU=u0 0(u(u0 0V)V)，TE=TE=開始，重復執(zhí)行下述操開始，重復執(zhí)行下述操作：作：F在所有在所有uUuU，vV-UvV-U的邊的邊(u(u，v)v)中找一條代價最小中找一條代價最小的邊的邊(u(u0 0 ,v,v0 0),),將其并入集合將其并入集合TETE，同時將，同時將v v0 0并入并入U U集合集合F當當U=VU=V則結束，此時則結束，此時TETE中必有中必有n-1n-1條邊，則條邊，則

34、T=(VT=(V，TE)TE)為為N的最小生成樹。的最小生成樹。q普里姆算法構造最小生成樹的過程是從一個頂點普里姆算法構造最小生成樹的過程是從一個頂點U=uU=u0 0 作初態(tài)，不斷尋找與作初態(tài)，不斷尋找與U U中頂點相鄰且代價最小的邊的另中頂點相鄰且代價最小的邊的另一個頂點，擴充到一個頂點，擴充到U U集合直至集合直至U=VU=V為止。為止。44最小代價生成樹最小代價生成樹q普里姆算法求最小生成樹普里姆算法求最小生成樹V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-UV1 V2 ,V3 ,V4 , V5 ,V6 步驟步驟(0)V1 ,V3 V2 ,V4 ,

35、 V5 ,V6 (1)V1 ,V3 ,V6 V2 ,V4 , V5 (2)V1 ,V3 ,V6 ,V4 V2, V5 (3)V1 ,V3 ,V6 ,V4 ,V2 V5 (4)V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)45V4V1V3V2V6V5165V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5UV-U最小代價生成樹最小代價生成樹q普里姆算法求最小生成樹普里姆算法求最小生成樹46V4V1V3V2V6V565V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟步驟(0)V1 ,V3

36、V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)46554UV-U最小代價生成樹最小代價生成樹q普里姆算法求最小生成樹普里姆算法求最小生成樹47V4V1V3V2V6V565V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4655V1 ,V3 ,V6 ,V4 V2, V5 (3)262UV-U最小代價生成樹最小代價生成樹q普里姆算法求最小生成樹普里姆算法求最小生成樹48V4V1V3V2V6V56V4V1

37、V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)465V1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5UV-U最小代價生成樹最小代價生成樹q普里姆算法求最小生成樹普里姆算法求最小生成樹49V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)46V

38、1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)33UV-U最小代價生成樹最小代價生成樹q普里姆算法求最小生成樹普里姆算法求最小生成樹50V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4V1 ,V3 ,V6 ,V4 V2, V5 (3)2V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V

39、2 ,V5 (5)3UV-U最小代價生成樹最小代價生成樹q普里姆算法求最小生成樹普里姆算法求最小生成樹51Prim算法的實現(xiàn)算法的實現(xiàn)q頂點集合如何表示？頂點集合如何表示？q最小邊如何選擇？最小邊如何選擇？q一個頂點加入一個頂點加入U U集合如何表示？集合如何表示？structstruct int adjvex int adjvex; ; double lowcost double lowcost; ;closedgeMAX_VERTEX_NUMclosedgeMAX_VERTEX_NUM;closedgei.adjvex=kclosedgei.lowcost=0頂點頂點i與頂點與頂點k鄰接鄰

40、接頂點頂點k已經(jīng)在已經(jīng)在U集合中集合中頂點頂點i加入加入U集合時集合時52adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v6323456UV-Uk 頂點頂點iclosedgeclosedge2.adjvex=1 closedge2. lowcost=6closedge3.adjvex=1closedge3. lowcost=1closedge4.adjvex=1closedge4. lowcost=5V4V1V3V2V6V5165U集合的成員集合的成員：V-U集合的成員：集合的成員：q當當U集合中加入一個新頂點時，集合中加入一個新頂點時，V-U集合集合中的頂點到中的

41、頂點到U的最小代價邊可能會更新的最小代價邊可能會更新53adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v6623456UV-Uk 頂點頂點iclosedgeV4V1V3V2V6V55564U集合的成員集合的成員：V-U集合的成員：集合的成員：q當當U集合中加入一個新頂點時，集合中加入一個新頂點時，V-U集合集合中的頂點到中的頂點到U的最小代價邊可能會更新的最小代價邊可能會更新54adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcos

42、tv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 423456UV-Uk 頂點頂點iclosedgeV4V1V3V2V6V5562U集合的成員集合的成員：V-U集合的成員：集合的成員：q當當U集合中加入一個新頂點時，集合中加入一個新頂點時，V-U集合集合中的頂點到中的頂點到U的最小代價邊可能會更新的最小代價邊可能會更新55adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlo

43、wcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 23456UV-Uk 頂點頂點iclosedge2V4V1V3V2V6V556U集合的成員集合的成員：V-U集合的成員：集合的成員：q當當U集合中加入一個新頂點時，集合中加入一個新頂點時，V-U集合集合中的頂點到中的頂點到U的最小代價邊可能會更新的最小代價邊可能會更新56adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlo

44、wcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 2adjvexlowcost000v230v1,v3,v6,v4,v2v5 23456UV-Uk 頂點頂點iclosedge5V4V1V3V2V6V53U集合的成員集合的成員：V-U集合的成員：集合的成員：q當當U集合中加入一個新頂點時，集合中加入一個新頂點時，V-U集合集合中的頂點到中的頂點到U的最小代價邊可能會更新的最小代價邊可能會更新57adjvexlowcostv16v11v15 v1v2,v3,v4,v5,v63adjvexlowcostv

45、350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 223456UV-Uk 頂點頂點iclosedgeV4V1V3V2V6V5adjvexlowcost00000v1,v3,v6,v4,v2,v5 adjvexlowcost000v230v1,v3,v6,v4,v2v5 514253U集合的成員集合的成員：V-U集合的成員：集合的成員：58void MiniSpanTree_PRIM (Graph G, VertexType u

46、) /用普里姆算法從頂點用普里姆算法從頂點u u出發(fā)構造出發(fā)構造G G的最小生成樹的最小生成樹 for(j = 0; j G.vexnum; +j) /輔助數(shù)組初始化輔助數(shù)組初始化 if ( j != u ) closedgej = u, G.arcsuj;struct int adjvex; double lowcost;closedgeMAX_VERTEX_NUM; closedgeu.lowcost = 0; /初始初始,U=u,U=u for(i = 1; i G.vexnum; +i) k = minimum(closedge); /求生成樹的下一個頂點求生成樹的下一個頂點k k c

47、out closedgek.adjvex G.vexsk; closedgek.lowcost = 0; for(j = 0; j G.vexnum; +j) if (G.arcskj.adj 0, vi v-u cout closedgek.adjvex G.vexsk; /輸出生成樹的邊輸出生成樹的邊 closedgek.lowcost = 0; /頂點頂點k k并入并入U U集合集合 for(j = 0; j G.vexnum; +j) if (G.arcskj closedgej.lowcost) closedgej = k, G.arcskj; 算法的時間復雜度為：算法的時間復雜度為

48、：O(nO(n2 2) )59克魯斯卡爾克魯斯卡爾(Kruskal)算法算法q假設連通網(wǎng)假設連通網(wǎng)N=(VN=(V，E)E)，則令最小生成樹的初始狀態(tài)為只有，則令最小生成樹的初始狀態(tài)為只有n n個頂點而無邊的非連通圖個頂點而無邊的非連通圖T=(VT=(V，)，圖中每個頂點自成一，圖中每個頂點自成一個連通分量。個連通分量。q在在E E中選擇代價最小的邊，若該邊依附的頂點落在中選擇代價最小的邊，若該邊依附的頂點落在T T中不同中不同的連通分量上，則將此邊加入到的連通分量上，則將此邊加入到T T中，否則舍去此邊而選擇中，否則舍去此邊而選擇下一條代價最小的邊。依次類推，直至下一條代價最小的邊。依次類推

49、，直至T T中所有頂點都在同中所有頂點都在同一連通分量上為止。一連通分量上為止。60最小代價生成樹最小代價生成樹q克魯斯卡爾算法求最小生成樹克魯斯卡爾算法求最小生成樹V4V1V3V2V6V56512665534V4V1V3V2V6V5123461q克魯斯卡爾算法求最小生成樹克魯斯卡爾算法求最小生成樹V4V1V3V2V6V56512665534V4V1V3V2V6V512345V V3 3、V V4 4依附在同依附在同一個連通分量一個連通分量最小代價生成樹最小代價生成樹62q克魯斯卡爾算法求最小生成樹克魯斯卡爾算法求最小生成樹V4V1V3V2V6V56512665534V4V1V3V2V6V51

50、234V V1 1、V V4 4依附在同依附在同一個連通分量一個連通分量5最小代價生成樹最小代價生成樹63q克魯斯卡爾算法求最小生成樹克魯斯卡爾算法求最小生成樹V4V1V3V2V6V56512665534V4V1V3V2V6V512534最小代價生成樹最小代價生成樹64克魯斯卡爾克魯斯卡爾(Kruskal)算法算法q從上述過程可知，實現(xiàn)從上述過程可知，實現(xiàn)克魯斯卡爾克魯斯卡爾(Kruskal)算法時，算法時，要解決以下兩個問題：要解決以下兩個問題：如何選擇代價最小的邊；如何選擇代價最小的邊；如何判定邊所關聯(lián)的兩個頂點是否在同一個連通如何判定邊所關聯(lián)的兩個頂點是否在同一個連通分量中分量中657.

51、5 有向無環(huán)圖有向無環(huán)圖DAG*a+b+dcdc表達式：表達式：a+b(c+d) (c+d)(a) 表達式樹*a+bdc(b) DAG圖667.5(續(xù)續(xù)) 有向無環(huán)圖及應用有向無環(huán)圖及應用nAOV網(wǎng)、AOE網(wǎng)n拓撲排序n關鍵路徑67例例 某工程可分為某工程可分為7 7個子工個子工程，若用程，若用頂點表示子工程（頂點表示子工程（也稱活動），也稱活動）， 用用弧表示子弧表示子工程間的順序關系，工程間的順序關系，工程的工程的施工流程可用如右的施工流程可用如右的AOVAOV網(wǎng)網(wǎng)表示。表示。q AOVAOV網(wǎng)網(wǎng)(Activity On Vertex net )(Activity On Vertex ne

52、t )F用頂點表示用頂點表示活動活動，邊表示邊表示活動的順序關系活動的順序關系的有向圖稱的有向圖稱為為AOVAOV網(wǎng)網(wǎng)( (頂點表示活動的網(wǎng)頂點表示活動的網(wǎng)).).應用：應用： 工程流程、生產(chǎn)過程中各道工序的流程等工程流程、生產(chǎn)過程中各道工序的流程等 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V67.5(續(xù)續(xù)) 有向無環(huán)圖及應用有向無環(huán)圖及應用68q 對工程問題，人們至少會關心如下兩類問題：對工程問題，人們至少會關心如下兩類問題：1)1) 工程能否順序進行，即工程流程是否工程能否順序進行，即工程流程是否“合理合理”2)2) 完成整項工程至少需要多少時間，哪些子工程是影響完

53、成整項工程至少需要多少時間，哪些子工程是影響工程進度的關鍵子工程工程進度的關鍵子工程q 為求解工程流程是否為求解工程流程是否“合理合理”，通常用，通常用AOVAOV網(wǎng)表示工程流網(wǎng)表示工程流程程 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V6 某工程可分為某工程可分為7 7個子工程個子工程(V0(V0、V1V1、V2V2、V3V3、V4V4、V5V5、V6)V6)，若用，若用頂點表示子工程（頂點表示子工程（也稱活動），也稱活動）， 用用弧表示子工弧表示子工程間的順序關系，程間的順序關系，工程流程工程流程可用如右的可用如右的AOVAOV網(wǎng)表示。網(wǎng)表示。例例7.5(續(xù)續(xù)) 有向

54、無環(huán)圖及應用有向無環(huán)圖及應用69c4c1c2c3c12c9c10c11c6c7c8c5課程編號課程編號課程名稱課程名稱先修課程先修課程c1程序設計基礎程序設計基礎無無c2離散數(shù)學離散數(shù)學c1c3數(shù)據(jù)結構數(shù)據(jù)結構c1, c2c4匯編語言匯編語言c1c5算法設計與分析算法設計與分析c3, c4c6計算機體系結構計算機體系結構c11c7編譯原理編譯原理c3, c5c8操作系統(tǒng)原理操作系統(tǒng)原理c3, c6c9高等數(shù)學高等數(shù)學無無c10線性代數(shù)線性代數(shù)c9c11普通物理普通物理c9c12數(shù)值分析數(shù)值分析c1 , c9, c107.5(續(xù)續(xù)) 有向無環(huán)圖及應用有向無環(huán)圖及應用如何安排施工計劃？如何安排施工

55、計劃？如何安排教學計劃？如何安排教學計劃？70q 一個可行的施工計劃：一個可行的施工計劃： V0, V1, V2, V4, V3, V6, V5q 一個可行的學習計劃為：一個可行的學習計劃為：C1, C9, C4, C2, C10, C11, C12, C3, C6, C5, C7, C8q 特點：特點：若在有向圖中有弧若在有向圖中有弧，則稱頂點，則稱頂點v是頂點是頂點u 的前趨，那的前趨，那么施工計劃中頂點么施工計劃中頂點v 也排在也排在u之前。也稱之前。也稱u是是v的后繼。的后繼。c4c1c2c3c12c9c10c11c6c7c8c5 V5V5 V3V3 V2V2 V0V0 V1V1 V4

56、V4 V6V671q 特點：特點：若在有向圖中有弧若在有向圖中有弧，則稱頂點，則稱頂點v是頂點是頂點u 的前趨，那么的前趨，那么施工計劃中頂點施工計劃中頂點v 也排在也排在u之前。也之前。也稱稱u是是v的后繼。的后繼。q 一個一個AOV網(wǎng)不應該存在環(huán)，因為網(wǎng)不應該存在環(huán)，因為存在環(huán)意味著某項活動的進行應該存在環(huán)意味著某項活動的進行應該以本活動的完成作為先決條件，這以本活動的完成作為先決條件，這肯定是荒謬的。肯定是荒謬的。c4c1c2c3c12c9c10c11c6c7c8c57.5.1 7.5.1 拓撲排序拓撲排序72q拓撲排序拓撲排序： 將有向圖中的頂點排成將有向圖中的頂點排成一個序列。一個序

57、列。q拓撲序列拓撲序列：有向圖有向圖D的一個頂點序的一個頂點序列稱作一個拓撲序列。如果該序列中任列稱作一個拓撲序列。如果該序列中任兩頂點兩頂點v 、u ，若在，若在D中中v是是u前趨，則在前趨，則在序列中序列中v也是也是u前趨前趨。c4c1c2c3c12c9c10c11c6c7c8c57.5.1(續(xù)續(xù)) 拓撲排序拓撲排序73q 拓撲排序方法：拓撲排序方法：1)在在有向圖中選一個無前趨的頂點有向圖中選一個無前趨的頂點v，輸出之；，輸出之；2)從有向圖中刪除從有向圖中刪除v及以及以v為尾的弧；為尾的??；3)重復重復1)、2)，直接全部輸出全部頂點或有向圖中不存在無前趨的結點，直接全部輸出全部頂點或

58、有向圖中不存在無前趨的結點時為止。時為止。如何在計算機上實現(xiàn)如何在計算機上實現(xiàn)對有向圖的拓撲排序？對有向圖的拓撲排序？7.5.1(7.5.1(續(xù)續(xù)) ) 拓撲排序拓撲排序 V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V674q 拓撲排序方法：拓撲排序方法：1)在有向圖中選一個無前趨的頂點在有向圖中選一個無前趨的頂點v，輸出之；，輸出之；2)從有向圖中刪除從有向圖中刪除v及以及以v為尾的?。粸槲驳幕?；3)重復重復1)、2)，直接全部輸出全部頂點或有向圖中不存在無前趨的結點，直接全部輸出全部頂點或有向圖中不存在無前趨的結點時為止。時為止。 V5V5 V3V3 V2V2 V0V0

59、 V1V1 V4V4 V6V6V0V07.5.1(續(xù)續(xù)) 拓撲排序拓撲排序75q 拓撲排序方法：拓撲排序方法：1)在在有向圖中選一個無前趨的頂點有向圖中選一個無前趨的頂點v，輸出之；，輸出之；2)從有向圖中刪除從有向圖中刪除v及以及以v為尾的?。粸槲驳幕?；3)重復重復1)、2)，直接全部輸出全部頂點或有向圖中不存在無前趨的結點，直接全部輸出全部頂點或有向圖中不存在無前趨的結點時為止。時為止。 V5V5 V3V3 V2V2 V1V1 V4V4 V6V6V0V07.5.1(續(xù)續(xù)) 拓撲排序拓撲排序76q 拓撲排序方法：拓撲排序方法：1)在有向圖中選一個無前趨的頂點在有向圖中選一個無前趨的頂點v，輸

60、出之；，輸出之；2)從有向圖中刪除從有向圖中刪除v及以及以v為尾的??；為尾的弧；3)重復重復1)、2)，直接全部輸出全部頂點或有向圖中不存在無前趨的結點，直接全部輸出全部頂點或有向圖中不存在無前趨的結點時為止。時為止。 V5V5 V3V3 V2V2 V1V1 V4V4 V6V6V0V0 V1V17.5.1(續(xù)續(xù)) 拓撲排序拓撲排序77q 拓撲排序方法：拓撲排序方法：1)在在有向圖中選一個無前趨的頂點有向圖中選一個無前趨的頂點v，輸出之；，輸出之；2)從有向圖中刪除從有向圖中刪除v及以及以v為尾的??；為尾的弧；3)重復重復1)、2)，直接全部輸出全部頂點或有向圖中不存在無前趨的結點，直接全部輸出全部頂點