數(shù)據(jù)結(jié)構(gòu) 圖PPT課件
《數(shù)據(jù)結(jié)構(gòu) 圖PPT課件》由會(huì)員分享,可在線閱讀,更多相關(guān)《數(shù)據(jù)結(jié)構(gòu) 圖PPT課件(142頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、7.1 圖的定義和術(shù)語1第1頁/共142頁2 7.1 圖的定義和術(shù)語 圖(Graph) 是一種較線性結(jié)構(gòu)和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 線性表中,一個(gè)元素只能和其直接前驅(qū)或直接后繼相關(guān); 在樹中,一個(gè)結(jié)點(diǎn)可以和其下一層的所有孩子結(jié)點(diǎn)相關(guān),以及上一層的雙親結(jié)點(diǎn)相關(guān),但不能和其他的任何結(jié)點(diǎn)直接相關(guān); 而對(duì)于圖來說,圖中任意兩個(gè)結(jié)點(diǎn)之間都可以直接相關(guān)。BCADE姓 名學(xué) 號(hào) 性 別年 齡 健康情況王小林790631男 18 健康陳 紅790632女 20 一般劉建平790633男 21 健康張立立790634男 17 神經(jīng)衰弱 . . .第2頁/共142頁 圖的用途極其廣泛,已滲入到語言學(xué)、邏輯學(xué)、物理、
2、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)等其他分支學(xué)科當(dāng)中。 在本課程當(dāng)中,我們主要討論如何在計(jì)算機(jī)上實(shí)現(xiàn)圖的操作,因此主要學(xué)習(xí)圖的存儲(chǔ)結(jié)構(gòu)以及圖的若干操作的實(shí)現(xiàn)。3第3頁/共142頁47.1 圖的定義和術(shù)語 圖(graph) G由兩個(gè)集合V和E組成,記為G = (V, E) V是頂點(diǎn)的有窮非空集合; E是邊的集合,邊是V中頂點(diǎn)的偶對(duì)。 E可以是空集,若E為空,則G中只有頂點(diǎn)沒有邊。 在圖中,數(shù)據(jù)元素通常稱為頂點(diǎn)(vertex)。第4頁/共142頁57.1 圖的定義和術(shù)語 若頂點(diǎn)之間的偶對(duì)是有方向的,稱此圖為有向圖(digraph); 有方向偶對(duì)用尖括號(hào)括起來,并稱之為弧(arc)。如v, wV,E
3、,則是有向圖中從頂點(diǎn)v到頂點(diǎn)w的一條弧,v是弧尾(tail)(始點(diǎn)),w是弧頭(head)(終點(diǎn))。ABCD有向圖有向圖 G1第5頁/共142頁 若頂點(diǎn)之間的偶對(duì)是無方向的,稱此圖為無向圖(undigraph). 無方向偶對(duì)用圓括括起來,通常稱之為邊(edge)。如x, yV,(x, y)E,則(x, y)是無向圖中頂點(diǎn)x和頂點(diǎn)y之間的一條邊。6ABCDE無向圖無向圖 G2第6頁/共142頁7 7.1 圖的定義和術(shù)語ABCD有向圖有向圖 G1 結(jié)點(diǎn)結(jié)點(diǎn) 或或 頂點(diǎn):頂點(diǎn):AB 有向邊有向邊(?。ɑ。?、 弧尾或初始結(jié)點(diǎn)、弧尾或初始結(jié)點(diǎn)、 弧頭或終止結(jié)點(diǎn)弧頭或終止結(jié)點(diǎn)AB 有向圖:有向圖:G1
4、=(V1,A1 ) V1 = A,B,C,D A1 = , , , ABCDE無向圖無向圖 G2 結(jié)點(diǎn)結(jié)點(diǎn) 或或 頂點(diǎn):頂點(diǎn):AB 無向圖:無向圖:G2 =(V2,A2 ) V2 = A,B,C,D,E A2 = (A,B), (A,C), (B,D), (B,E), (C,E), (D,E) 無向邊或無向邊或邊邊AB第7頁/共142頁8 7.1 圖的定義和術(shù)語 在以后的討論中,不考慮頂點(diǎn)到其自身的弧或邊,那么: 對(duì)于有n個(gè)頂點(diǎn)的無向圖,邊的最大數(shù)目為:n(n-1)/2 對(duì)于n個(gè)頂點(diǎn)的有向圖,弧的最大數(shù)目為:n(n-1)第8頁/共142頁97.1 圖的定義和術(shù)語幾種圖的定義:完全圖(Compl
5、eted Graph):有n(n-1)/2條邊的無向圖。有向完全圖:有n(n-1)條弧的有向圖。稀疏圖(Sparse Graph):有很少條邊或弧的圖(e=nlogn)第9頁/共142頁107.1 圖的定義和術(shù)語有時(shí)圖的邊或弧附有相關(guān)的數(shù)值,這種數(shù)值稱為權(quán)(weight)。這些權(quán)可以表示一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離,或時(shí)間耗費(fèi)、開銷耗費(fèi)等。所以,權(quán)是與圖的邊或弧相關(guān)的數(shù)。鄰接點(diǎn):對(duì)于無向圖GG(V,E)(V,E),如果邊(v, v) E,則稱頂點(diǎn)v和v互為鄰接點(diǎn);邊(v, v)依附于頂點(diǎn)v和v,或者說,邊(v, v)和頂點(diǎn)v和v相關(guān)聯(lián)。第10頁/共142頁117.1 圖的定義和術(shù)語每條邊或弧都帶
6、權(quán)的圖又稱為網(wǎng)。第11頁/共142頁12 7.1 圖的定義和術(shù)語無向圖頂點(diǎn)的度(degree) :和該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目,記為TD(v)。有向圖頂點(diǎn)的出度( outdegree) :以該頂點(diǎn)為弧尾(起點(diǎn))的弧的數(shù)目,記為OD(v) 。有向圖頂點(diǎn)的入度(indegree):以該頂點(diǎn)為弧頭(終點(diǎn))的弧的數(shù)目,記為ID(v) 。有向圖頂點(diǎn)的度: TD(v)=ID(v)+OD(v)一般地,對(duì)于無向圖和有向圖,如果頂點(diǎn)vi的度記為TD(vi),那么一個(gè)有n個(gè)項(xiàng)點(diǎn),e條邊或弧的圖,niivTDe12/ )( 圖論中,有一個(gè)十分簡(jiǎn)單但有很有用的關(guān)于頂點(diǎn)的度的定理,即握手定理:第12頁/共142頁137.1
7、 圖的定義和術(shù)語 路徑:在圖中從頂點(diǎn)v v到頂點(diǎn)v v所經(jīng)過的所有頂點(diǎn)的序列。有向圖的路徑也是有向的。 路徑長(zhǎng)度:路徑上的邊或弧的數(shù)目。 簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 回路或環(huán):序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。 簡(jiǎn)單回路或環(huán):除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外,其余頂點(diǎn)不重復(fù)出現(xiàn)的路徑。第13頁/共142頁14 7.1 圖的定義和術(shù)語子圖:設(shè)兩個(gè)圖G(V, E)和G=(V,E),如果V V且E E,則稱G為G的子圖(Subgraph)。AACDACABCD有向圖有向圖G1的子圖的子圖ABCD有向圖有向圖 G1無無向圖向圖 G2ABCDEABDEAABCDABCDE無向圖無向圖
8、G2的子圖的子圖第14頁/共142頁15 7.1 圖的定義和術(shù)語連通:在無向圖中,如果從v到v存在路徑,則稱v和v是連通的。連通圖:無向圖G中如果任意兩個(gè)頂點(diǎn)vi,vj之間都是連通的。連通分量:無向圖中的極大連通子圖。強(qiáng)連通圖:在有向圖G中,如果對(duì)于每一對(duì)vi,vj V, vi vj,從vi到vj和從vj到vi都存在路徑,則稱G是強(qiáng)連通圖。強(qiáng)連通分量:有向圖中的極大強(qiáng)連通子圖?!皹O大”是指在保證子圖和連通的條件下無法再擴(kuò)大該子圖第15頁/共142頁167.1 圖的定義和術(shù)語ABCDEFGIJLHMK無向圖無向圖GABCDEHMFGIJLK無向圖無向圖GG的三個(gè)的三個(gè)連通分量連通分量( (無向圖
9、無向圖中的中的極大連通子圖極大連通子圖)第16頁/共142頁17第17頁/共142頁18 7.1 圖的定義和術(shù)語有向圖有向圖G的兩個(gè)強(qiáng)連通分量的兩個(gè)強(qiáng)連通分量有向圖有向圖GABCDBACD第18頁/共142頁197.1 圖的定義和術(shù)語u生成樹:圖的一個(gè)極小連通子圖,包含圖的所有 n 個(gè)結(jié)點(diǎn),但只含圖的n-1n-1 條邊。在生成樹中添加一條邊之后,必定會(huì)形成回路或環(huán),因?yàn)檫@條邊使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。u區(qū)別概念:無向圖中的極大連通子圖稱為連通分量。ABCDEHM無向圖無向圖G ABCDEHM無向圖無向圖G的生成樹的生成樹 第19頁/共142頁20n一個(gè)連通圖的生成樹,是含有該連
10、通圖的全部頂點(diǎn)的一個(gè)極小連通子圖。若連通圖G的頂點(diǎn)個(gè)數(shù)為n,則G的生成樹的頂點(diǎn)個(gè)數(shù)也為n,邊數(shù)為n-1,邊數(shù)多于n-1就不是極小連通子圖,少于n-1則不連通了。下圖(a)是個(gè)連通圖,圖(b)和(c)是它的兩個(gè)生成樹。第20頁/共142頁21 7.1 圖的定義和術(shù)語u如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)入度為0,其余頂點(diǎn)入度均為1,該圖必定是一棵有向樹。所有樹可以看成是圖的特例。u有向圖的生成森林:由若干棵有向樹組成,含有圖中全部頂點(diǎn),但只有構(gòu)成若干棵不相交的有向樹的弧。有向圖有向圖G的的生成森林生成森林有向圖有向圖GABFECDAFBEDC第21頁/共142頁7.2 圖的存儲(chǔ)結(jié)構(gòu)22第22頁/共142頁
11、23 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖存儲(chǔ)的特殊性: 頂點(diǎn)之間的關(guān)系無法用他們?cè)趦?nèi)存中的存儲(chǔ)位置來表示。 用多重鏈表來表示圖是自然的事情,它用一個(gè)由一個(gè)數(shù)據(jù)域和多個(gè)指針域組成的結(jié)點(diǎn)表示圖中的一個(gè)頂點(diǎn)。其中數(shù)據(jù)域存放該頂點(diǎn)的信息,指針域存放指向其鄰接點(diǎn)的地址。 常用的存儲(chǔ)方法有:鄰接矩陣表示法鄰接表表示法十字鏈表表示法鄰接多重表表示法第23頁/共142頁24 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法(鄰接矩陣表示法) 圖需要存儲(chǔ)的信息:頂點(diǎn)和弧(或邊)。 圖的數(shù)組表示法:用兩個(gè)數(shù)組分別存放圖中頂點(diǎn)的信息(數(shù)據(jù)元素)和圖中弧或邊的信息(數(shù)據(jù)元素之間的關(guān)系)。 頂點(diǎn)信息的存儲(chǔ)方法:一維數(shù)組頂點(diǎn)類型:整型、字
12、符型等 弧或邊信息的存儲(chǔ)方法:二維數(shù)組即鄰接矩陣弧或邊的信息類型:無權(quán)圖: 0或1;有權(quán)圖(網(wǎng)): 權(quán)值類型第24頁/共142頁25 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法 有向圖的鄰接矩陣有向圖的鄰接矩陣 設(shè)有向圖具有設(shè)有向圖具有 n n 個(gè)頂點(diǎn),則用個(gè)頂點(diǎn),則用 n n 行行 n n 列的矩列的矩陣陣 A A 表示該有向圖;表示該有向圖; 并且并且 Aij = 1Aij = 1,如果頂點(diǎn),如果頂點(diǎn)i i 至至 j j 有一條?。挥幸粭l??; Aij = 0Aij = 0,如果頂點(diǎn),如果頂點(diǎn) i i 至至 j j 沒有一條弧。沒有一條弧。 注意注意:Aii = 0Aii = 0。頂點(diǎn)頂點(diǎn)
13、i i 的出度的出度: : 第第i i 行之和行之和。 頂點(diǎn)頂點(diǎn) j j 的入度的入度: : 第第j j 列之和列之和。ABCD0 1 1 00 0 0 00 0 0 11 0 0 0表示成右圖矩陣第25頁/共142頁26 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法 無向圖的鄰接矩陣無向圖的鄰接矩陣 設(shè)無向圖具有設(shè)無向圖具有 n n 個(gè)頂點(diǎn),則用個(gè)頂點(diǎn),則用 n n 行行 n n 列的矩陣列的矩陣 A A 表示該無向圖;表示該無向圖; 并且并且 Aij = 1Aij = 1,如果頂點(diǎn),如果頂點(diǎn)i i 至至 j j 有一條邊;有一條邊; Aij = 0Aij = 0,如果頂點(diǎn),如果頂點(diǎn)i i 至
14、至 j j 沒有一條邊。沒有一條邊。 0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE表示成右圖矩陣無向圖的鄰接矩陣是對(duì)稱矩陣,有向圖的鄰接矩陣不一定是對(duì)稱矩陣。第26頁/共142頁277.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法:無向圖的鄰接矩陣無向圖的鄰接矩陣 注意注意: : Aii = 0Aii = 0 無向圖無向圖頂點(diǎn)頂點(diǎn)i i 的度的度: : 第第i i行或行或i i列之和列之和( (因?yàn)槭菍?duì)稱矩陣因?yàn)槭菍?duì)稱矩陣) )。 TD(v TD(vi i) )= 無向圖的總邊數(shù)無向圖的總邊數(shù)等于該矩陣上三角或下三角元素之和。等于該矩陣上三角或
15、下三角元素之和。第27頁/共142頁28 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法 有向網(wǎng)有向網(wǎng)的鄰接矩陣的鄰接矩陣設(shè)網(wǎng)具有設(shè)網(wǎng)具有 n n 個(gè)頂點(diǎn),則用個(gè)頂點(diǎn),則用 n n 行行 n n 列的矩陣列的矩陣 A A 表示表示該網(wǎng);并且該網(wǎng);并且 Aij = a Aij = a ,如果,如果i i 至至 j j 有一條弧且它的權(quán)值為有一條弧且它的權(quán)值為a a; Aij = Aij = 空空 或其它標(biāo)或其它標(biāo) 志,如果志,如果 i i 至至 j j 沒有一條沒有一條弧?;?。 $ a b $ $ $ $ b $ $ $ ba $ a $ ABCDaabbba表示成右圖矩陣第28頁/共142頁29
16、7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法 鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)#define INFINITY INT_MAX/用整型最大值代替用整型最大值代替#define MAX_VERTEX_NUM 20typedef enum DG, DN, UDG, UDN GraphKind;typedef struct ArcCellVRType adj; InfoType *info;/該弧相關(guān)信息的指針(可無)該弧相關(guān)信息的指針(可無) ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;VRType是頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖,用1或表示相鄰否;對(duì)帶權(quán)圖,則為權(quán)值類型
17、。VRType,InfoType都是要在主函數(shù)中定義的。有向圖,有向網(wǎng),無向圖,無向網(wǎng)第29頁/共142頁30 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法typedef structVertexType vexsMAX_VERTEX_NUM;/頂點(diǎn)頂點(diǎn)向量向量AdjMatrix arcs;/鄰接矩陣int vexnum, arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKind kind;/圖的種類標(biāo)志 MGraph; /鄰接矩陣表示的圖鄰接矩陣表示的圖 鄰接矩陣表示法的優(yōu)缺點(diǎn): 優(yōu)點(diǎn):各種基本操作都易于實(shí)現(xiàn),很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。 缺點(diǎn):空間浪費(fèi)嚴(yán)重。某些算法時(shí)間效率低
18、。有向圖, Kind = 0;有向網(wǎng), Kind = 1;無向圖,Kind = 2;無向網(wǎng), Kind = 3。第30頁/共142頁31 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法Status CreateUDN(MGraph &G) / 創(chuàng)建無向網(wǎng)G scanf(&G.vexnum, &G.arcnum, &IncInfo); / IncInfo為0則各邊不含其它信息for (i = 0; i G.vexnum; +i) scanf(&G.vexsi); / 輸入所有的頂點(diǎn)信息for (i = 0; i G.vexnum; +i)/ 初始化鄰接矩陣 for ( j = 0; jG.vexnu
19、m; +j) G.arcsi j = ( INFINITY, NULL ) ; / ( adj, info )for (k=0; kG.arcnum; +k)/ 輸入所有的邊 scanf(&v1, &v2, &w); / 輸入一條邊依附的兩個(gè)頂點(diǎn)和邊上的權(quán)值 i=LocateVex(G, v1); j=LocateVex(G, v2); / 查詢兩個(gè)頂點(diǎn)在圖中存儲(chǔ)的位置 G.arcsi j.adj = w; /弧的權(quán)值 if (IncInfo) Input(*G.arcsi j.info); / 輸入邊的相關(guān)信息 G.arcs ji = G.arcsi j; / 根據(jù)無向網(wǎng)的對(duì)稱性填充矩陣的對(duì)
20、稱部分return OK;第31頁/共142頁32 7.2.2 鄰接表表示法 鄰接表(Adjacency List)是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊(對(duì)有向圖是以頂點(diǎn)vi為尾的弧)。 鄰接表中的每個(gè)結(jié)點(diǎn)由三個(gè)域組成: 數(shù)據(jù)域info指向存儲(chǔ)和弧或邊相關(guān)的信息,如權(quán)值等。 鄰接點(diǎn)域adjvex指示與本條弧或邊依附的另一個(gè)頂點(diǎn)的位置 鏈域nextarc指向下一條弧或邊的結(jié)點(diǎn)adjvexnextarcinfo弧或邊結(jié)點(diǎn)弧或邊結(jié)點(diǎn)第32頁/共142頁337.2.2 鄰接表表示法datafirstarc頭結(jié)點(diǎn)頭結(jié)點(diǎn)每個(gè)鏈表附設(shè)一個(gè)每個(gè)鏈表
21、附設(shè)一個(gè)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn):data存儲(chǔ)頂點(diǎn)vi的名或其他有關(guān)的名或其他有關(guān)信息firstarc指向依附于該頂點(diǎn)的第一條弧或邊所有表頭結(jié)點(diǎn)通常以順序結(jié)構(gòu)(一維數(shù)組)的形式存儲(chǔ),以便訪問任一頂點(diǎn)的鏈表。第33頁/共142頁34 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.2 鄰接表表示法ABCD有向圖有向圖 G1A0BCD213有向圖有向圖G1的鄰接表的鄰接表0123A2BCD300 有向圖有向圖G1的逆鄰接表的逆鄰接表0123頂點(diǎn)的出度:該頂點(diǎn)所指向的鏈表的結(jié)點(diǎn)總數(shù)。頂點(diǎn)的入度:必須搜索整個(gè)鄰接表才能得到。改進(jìn):建立逆鄰接表或十字鏈表第34頁/共142頁357.2.2 鄰接表表示法 思考: 若無向圖中有n個(gè)頂點(diǎn)
22、、e條邊,則它的鄰接表需要 個(gè)頭結(jié)點(diǎn)和 個(gè)表結(jié)點(diǎn)。 在邊稀疏的情況下,用鄰接表表示圖比鄰接矩陣節(jié)省存儲(chǔ)空間。n2e第35頁/共142頁36 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.2 鄰接表表示法無無向圖向圖 G2ABCDEA4BCD244E31130201無向圖無向圖G2的鄰接表的鄰接表012301234頂點(diǎn)的度頂點(diǎn)的度:為該頂點(diǎn)所指向的鏈表中的結(jié)點(diǎn)總數(shù)。:為該頂點(diǎn)所指向的鏈表中的結(jié)點(diǎn)總數(shù)。六條邊而所有鏈表中的結(jié)點(diǎn)總數(shù)為六條邊而所有鏈表中的結(jié)點(diǎn)總數(shù)為12。改進(jìn):改進(jìn):建立鄰接多重表建立鄰接多重表第36頁/共142頁37 7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.2 鄰接表表示法#define MAX_VERTEX_N
23、UM 20typedef struct ArcNode int adjvex;/該弧所指向的頂點(diǎn)的位置 ArcNode *nextarc; /指向下一條弧的指針 InfoType *info;/該弧相關(guān)信息的指針,如網(wǎng)的權(quán)值指針 ArcNode;/表結(jié)點(diǎn)typedef struct VNode VertexType data;/頂點(diǎn)的信息 ArcNode *firstarc; /第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針 VNode, AdjListMAX_VERTEX_NUM;/頭結(jié)點(diǎn)typedef struct AdjList vertices; int vexnum,arcnum
24、;/ 圖的當(dāng)前頂點(diǎn)數(shù)、弧數(shù) int kind; /圖的種類標(biāo)志 ALGraph;第37頁/共142頁38鄰接表的優(yōu)缺點(diǎn): 優(yōu)點(diǎn):1) 容易找任一頂點(diǎn)的第一鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)。 2) 邊稀疏(ev2-v4-v8-v5-v3-v6-v7第49頁/共142頁50 7.3.1 深度優(yōu)先搜索 56724135672314從頂點(diǎn)從頂點(diǎn) 出發(fā)的搜索序列:出發(fā)的搜索序列: 5、6、2、3、1、4、7512431從頂點(diǎn)從頂點(diǎn) 出發(fā)的搜索序列:出發(fā)的搜索序列:1、2、4、3。沒有搜索。沒有搜索到所有的頂點(diǎn),必到所有的頂點(diǎn),必須另選圖中未訪須另選圖中未訪問過的頂點(diǎn),問過的頂點(diǎn),繼續(xù)進(jìn)行繼續(xù)進(jìn)行搜索。搜索。第50頁
25、/共142頁517.3.1 深度優(yōu)先搜索 數(shù)組visited存放結(jié)點(diǎn)的訪問標(biāo)記,在遍歷開始前,visited的所有成員都被設(shè)置成FALSE。 visitedi 值為FALSE:表示頂點(diǎn)i未被訪問過;TRUE:表示頂點(diǎn)i已被訪問過。第51頁/共142頁52 7.3.1 深度優(yōu)先搜索 使用的變量說明:使用的變量說明:#define TRUE 1#define FALSE 0typedef int Boolean; /Boolean是布爾類型,值是是布爾類型,值是FALSE或或TRUEBoolean visitedMAX ; / 用于標(biāo)識(shí)頂點(diǎn)是否已被訪問過用于標(biāo)識(shí)頂點(diǎn)是否已被訪問過Status (
26、* VisitFunc) (int v); / 函數(shù)變量函數(shù)變量void DFSTraverse( Graph G, Status ( * Visit)(int v) /對(duì)圖做深度優(yōu)先遍歷對(duì)圖做深度優(yōu)先遍歷int v; VisitFunc = Visit; /使用全局變量使用全局變量VisitFunc,使使DFS不必設(shè)函數(shù)指針參數(shù)不必設(shè)函數(shù)指針參數(shù) for ( v=0; v G.vexnum; +v ) visitedv = FALSE; for ( v=0; v =0 ; w = NextAdjVex(G, v, w) ) if ( ! visitedw ) DFS(G, w);算法函數(shù)Fi
27、rstAdjVex()用來找v的第一個(gè)鄰接點(diǎn)返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào)。若w是v的最后一個(gè)鄰接點(diǎn),則返回1。第53頁/共142頁54存儲(chǔ)結(jié)構(gòu)為鄰接矩陣時(shí)的NextAdjVex()int NextAdjVex(MGraph G,VertexType v,VertexType w) / 初始條件:圖G存在,v是G中某個(gè)頂點(diǎn),w是v的鄰接頂點(diǎn) / 操作結(jié)果:返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào),若w是v的最后一個(gè)鄰接頂點(diǎn),則返回-1 int i,j=0,k1,k2; k1=LocateVex(G,v); / k1為頂點(diǎn)v在圖G中的序號(hào) k2=LocateVex(G,w); /
28、k2為頂點(diǎn)w在圖G中的序號(hào) if(G.kind%2) / 網(wǎng) j=INFINITY; /無窮大 for(i=k2+1;inext) / 沒找到w或w是最后一個(gè)鄰接點(diǎn) return -1; else / p-data.adjvex=w return p-next-data.adjvex; / 返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào) 第55頁/共142頁567.3.1 深度優(yōu)先搜索 非連通圖的深度優(yōu)先遍歷CABDEGF第56頁/共142頁57上圖的鄰接矩陣及深度優(yōu)先遍歷 rowColABCDEFGA (一)01 01000B10001 00C (二)000001 (1) 0D1000001E0
29、100001 F0010000G0001 100CABDEGF第57頁/共142頁58上圖的鄰接矩陣存儲(chǔ)下的深度優(yōu)先遍歷過程 以A為起始點(diǎn)進(jìn)行DFS,在A所在行找到第一個(gè)值不為0且未被訪問的元素B,訪問之;在B所在行找第一個(gè)值不為0且未被訪問過的元素E一直到D ,訪問之;此時(shí)D所在行中的兩個(gè)非0元素對(duì)應(yīng)的頂點(diǎn)均已被訪問過。此時(shí),需返回到 ,找其所在行中下一個(gè)不為0的元素, 為其行中最后一個(gè)元素,需繼續(xù)返回到就這樣,一直返回到A(一)處,此后再無法返回。 然后排查還有沒有未被訪問過的頂點(diǎn),于是找到了C(二),訪問之;同樣找到F并訪問之,得到最終的深度優(yōu)先遍歷序列:A B E G D C F第58
30、頁/共142頁59A BC (1)DEFG1304506 16 6 234(2)0123456鄰接表結(jié)構(gòu)及深度優(yōu)先遍歷CABDEGF第59頁/共142頁60 以A為起點(diǎn),訪問之并找其鄰接表中的第一個(gè)結(jié)點(diǎn),該結(jié)點(diǎn)鄰接點(diǎn)域?yàn)?(即為頂點(diǎn)B),訪問B并找B的鄰接表的第一個(gè)結(jié)點(diǎn),此結(jié)點(diǎn)表示頂點(diǎn)A,而A已訪問過,需找其第二個(gè)結(jié)點(diǎn)(即指示頂點(diǎn)E ),訪問E這樣繼續(xù)尋找直到訪問完頂點(diǎn)D,其鄰接表所指示的頂點(diǎn)全被訪問完,此時(shí)需返回到結(jié)點(diǎn) ,其后的邊結(jié)點(diǎn)所指為頂點(diǎn)E(已被訪問),需返回到,其后已無結(jié)點(diǎn),繼續(xù)返回到 ,此后再無法返回。需逐個(gè)第排查以找到下一個(gè)還沒有被訪問的頂點(diǎn)。于是找到C,按上述方法繼續(xù)即可。鄰接
31、表結(jié)構(gòu)及深度優(yōu)先遍歷第60頁/共142頁617.3.1 深度優(yōu)先搜索 時(shí)間復(fù)雜度:時(shí)間復(fù)雜度: 對(duì)前述算法來說,對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次對(duì)前述算法來說,對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù),函數(shù),因此,遍歷圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。因此,遍歷圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。耗費(fèi)時(shí)間取決于其存儲(chǔ)結(jié)構(gòu)。耗費(fèi)時(shí)間取決于其存儲(chǔ)結(jié)構(gòu)。 鄰接矩陣(鄰接矩陣(二維數(shù)組二維數(shù)組)表示時(shí),查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為:)表示時(shí),查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為:T(n)= O(n2)第61頁/共142頁627.3.1 深度優(yōu)先搜索時(shí)間復(fù)雜度:時(shí)間復(fù)雜度: 鄰接表(鄰接表(圖的
32、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)) 調(diào)用調(diào)用DFSDFS找鄰接點(diǎn)所需時(shí)間為找鄰接點(diǎn)所需時(shí)間為O(e) O(e) (2e(若G為無向圖)或e(若G為有向圖),即O(e) ; ; 在調(diào)用在調(diào)用DFSDFS之前還需對(duì)數(shù)組之前還需對(duì)數(shù)組visited visited 進(jìn)行預(yù)處理,顯然其時(shí)間復(fù)雜進(jìn)行預(yù)處理,顯然其時(shí)間復(fù)雜度可以控制在度可以控制在O(n)O(n)內(nèi);內(nèi); 故總的時(shí)間復(fù)雜度為:故總的時(shí)間復(fù)雜度為: T(n)= O(n + e) 注:n-頂點(diǎn)數(shù), e-邊或弧數(shù)第62頁/共142頁637.3.2 廣度優(yōu)先搜索基本思想 首先,訪問初始點(diǎn)vi ,并做訪問過標(biāo)志訪問vi 的所有未被訪問過的鄰接點(diǎn)vi1,vi2,.,vit
33、,并均標(biāo)記為已訪問過然后再按照vi1,vi2,.,vit 的次序,訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn),并做標(biāo)記。依次類推,直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若圖中還有未被訪問的頂點(diǎn),則任選其一作為起點(diǎn),重新開始上述過程,直至圖中所有頂點(diǎn)都被訪問到?!跋缺辉L問的頂點(diǎn)的鄰接點(diǎn)”要先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問,也就是先到先被訪問。第63頁/共142頁64 7.3.2 廣度優(yōu)先搜索 需要特別說明的是:頂點(diǎn)的鄰接頂點(diǎn)的次序是任意的,因此廣度優(yōu)先搜索的序列可能有多種。 V1V2V3V4V5V8V6V7v1-v2-v3-v4-v5-v6-v7-v8鄰接頂點(diǎn)的訪問次序以序號(hào)為準(zhǔn),序號(hào)小
34、的先訪問。從v v1 1出發(fā)進(jìn)行搜索的訪問序列:第64頁/共142頁657.3.2 廣度優(yōu)先搜索對(duì)于廣度優(yōu)先遍歷,其關(guān)鍵之處在于怎么保證“先被訪問的頂點(diǎn)的鄰接點(diǎn)”要先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問?先到先被訪問,這正好是隊(duì)列的特點(diǎn),因此可以使用隊(duì)列來實(shí)現(xiàn)。 使用的變量說明等與深度優(yōu)先搜索相同 廣度優(yōu)先遍歷的算法第65頁/共142頁667.3.2 廣度優(yōu)先搜索 廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷圖相同深度優(yōu)先搜索遍歷圖相同 : : 鄰接矩陣鄰接矩陣 T(n)= O(n2) 鄰接表鄰接表 T(n)= O(n + e) n:頂點(diǎn)數(shù)頂點(diǎn)數(shù) e:邊邊或弧或弧數(shù)數(shù)第66頁/共142頁67
35、 7.4 圖的連通性問題7.4.1 無向圖的連通分量和生成樹 在對(duì)無向圖進(jìn)行遍歷時(shí),對(duì)于連通圖,從圖中任一頂點(diǎn)出發(fā),進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索,便可訪問到圖中所有頂點(diǎn);而對(duì)于非連通圖,則需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索。而每一次從一個(gè)新頂點(diǎn)出發(fā)搜索得到的頂點(diǎn)序列就是圖的各個(gè)連通分量中的頂點(diǎn)集。這些頂點(diǎn)集分別加上所有依附于它們的邊,便構(gòu)成了連通分量。第67頁/共142頁687.4.1 無向圖的連通分量和生成樹ABLMCDEGHKFJI無向圖無向圖GABLMCFJDEGHKI無向圖無向圖G的三個(gè)連通分量的三個(gè)連通分量第68頁/共142頁69 7.4.1 無向圖的連通分量和生成樹 在對(duì)連通圖進(jìn)行搜索時(shí),
36、搜索過程中經(jīng)歷的所有邊和圖中所有的頂點(diǎn)構(gòu)成了連通圖的一個(gè)極小連通子圖,即連通圖的生成樹。 稱由深度優(yōu)先搜索得到的生成樹為深度優(yōu)先生成樹,而由廣度優(yōu)先搜索得到的生成樹稱廣度優(yōu)先生成樹。 對(duì)于非連通圖,其中的每一個(gè)連通分量都可以通過遍歷得到一棵生成樹,所有這些連通分量的生成樹就構(gòu)成了非連通圖的生成森林。第69頁/共142頁707.4.1 無向圖的連通分量和生成樹 設(shè)E(G)E(G) 為連通圖GG中所有邊的集合,則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí),必定將E(G)E(G) 分成兩個(gè)集合T(G)T(G)和B(G)B(G),其中T(G)T(G)是遍歷圖過程中歷經(jīng)的邊的集合; B(G)B(G)是剩余的邊的集合。顯
37、然,T(G)T(G)和連通圖中所有的頂點(diǎn)構(gòu)成連通圖GG的極小連通子圖。下圖中的虛線為B(G)B(G)中的邊。 ABLMCDEGHKFJI無向圖無向圖GABLMCFJDEGHKI無向圖無向圖GG的的深度優(yōu)先生成森林深度優(yōu)先生成森林第70頁/共142頁71 7.4.1 無向圖的連通分量和生成樹 如果以孩子兄弟鏈表(Page136)作生成森林的存儲(chǔ)結(jié)構(gòu),則形成非連通圖的深度優(yōu)先生成森林的算法 typedef struct CSNode /二叉鏈表(孩子-兄弟) ElemType data; struct CSNode *firstchild, *nextsibling; CSNOde, *CSTre
38、e;第71頁/共142頁72 7.4.3 最小生成樹假設(shè)要在n個(gè)城市之間建立通信網(wǎng)絡(luò),連通n個(gè)城市只需要n-1條線路,問題是如何鋪設(shè)線路才能最節(jié)省資金?而在n個(gè)城市間最多可能有n(n-1)條線路,各個(gè)線路的費(fèi)用是不一樣的,怎么選擇這n-1條線路,使總的耗費(fèi)最少呢?如果把城市當(dāng)作圖的頂點(diǎn)看待,城市之間的通信線路看作圖的頂點(diǎn)之間的邊,邊的權(quán)值就相當(dāng)于通信線路的費(fèi)用。在n個(gè)城市之間建立n-1條通信線路實(shí)際上就是圖的一棵生成樹。第72頁/共142頁737.4.3 最小生成樹具有n個(gè)頂點(diǎn)的圖的生成樹的數(shù)目是很多的,我們的目標(biāo)是要選擇一棵具有最小代價(jià)的生成樹(Minimum Cost Spanning T
39、ree,MST)(簡(jiǎn)稱最小生成樹最小生成樹)。一棵生成樹的代價(jià)就是該樹上所有邊的權(quán)值之和。第73頁/共142頁747.4.3 最小生成樹構(gòu)造最小生成樹可以有多種算法,最常用的算法利用了最小生成樹的一種簡(jiǎn)稱為MST的性質(zhì):即假設(shè)N(V,E)是一個(gè)連通網(wǎng),U是頂點(diǎn)集V的一個(gè)非空子集,若(u,v)是一條具有最小權(quán)值(代價(jià))的邊,其中uU, v V-U,則必存在一棵包含邊(u,v)的最小生成樹。該性質(zhì)可以用反證法來證明。第74頁/共142頁757.4.3 最小生成樹證明:假設(shè)網(wǎng)N的任何一棵最小生成樹都不包含邊(u,v)。設(shè)T是連通網(wǎng)上的一棵最小生成樹,當(dāng)把邊(u,v)加入T中時(shí),T中必存在一條包含(u
40、,v)的回路;那么在這條回路上任意刪去除邊(u,v)外的一條邊(u, v),這條回路上的所有頂點(diǎn)之間以及所有頂點(diǎn)與其他頂點(diǎn)之間必定仍然有通路,從而消除了回路,并生成了一棵新的生成樹T,而(u,v)的代價(jià)必定不高于(u,v),所以T是包含(u,v)的一棵最小生成樹,這與假設(shè)矛盾。第75頁/共142頁767.4.3 最小生成樹下面介紹兩個(gè)利用MST性質(zhì)構(gòu)造最小生成樹的算法:Prim(普里姆)算法Kruskal(克魯斯卡爾)算法第76頁/共142頁77 7.4.3 最小生成樹Prim算法的基本思想:假設(shè)N(V,E)是連通網(wǎng),TE是N上最小生成樹的邊的集合。算法首先從Uu0(u0 V), TE=開始,
41、重復(fù)執(zhí)行如下操作: 在所有u U,v V-U的邊(u,v) E找一條代價(jià)最小的邊(u0, v0)并入集合TE,同時(shí)v0并入U(xiǎn),直到UV為止。 此時(shí)TE中必有n-1條邊,T(V, TE)即為N的最小生成樹。第77頁/共142頁78第78頁/共142頁P(yáng)rimPrim算法實(shí)例算法實(shí)例79(1) 在以頂點(diǎn)1為出發(fā)點(diǎn),頂點(diǎn)2, 3, 4, 5, 6為終止點(diǎn)的邊中,將權(quán)最小的邊(1, 3)作為最小生成樹的第一條邊加入TE,頂點(diǎn)3加入U(xiǎn)。則U = 1, 3,TE = (1, 3),V - U = 2, 4, 5, 6,如圖 (b)所示。第79頁/共142頁P(yáng)rimPrim算法實(shí)例算法實(shí)例80(2) 在以頂
42、點(diǎn)1, 3為出發(fā)點(diǎn),頂點(diǎn)2, 4, 5, 6為終止點(diǎn)的邊中,將權(quán)最小的邊(3, 6) 作為最小生成樹的第二條邊加入TE,頂點(diǎn)6加入U(xiǎn)。則U = 1, 3, 6,TE = (1, 3),(3, 6),V - U = 2, 4, 5,如圖 (c)所示。第80頁/共142頁81Prim算法實(shí)例81(3) 在以頂點(diǎn)1, 3, 6為出發(fā)點(diǎn),頂點(diǎn)2, 4, 5為終止點(diǎn)的邊中,將權(quán)最小的邊(6, 4) 作為最小生成樹的第三條邊加入TE,頂點(diǎn)4加入U(xiǎn)。則U = 1, 3, 6, 4,TE = (1, 3), (3, 6), (6, 4),V - U = 2, 5,如圖 (d)所示。第81頁/共142頁8282
43、Prim算法實(shí)例82(4) 在以頂點(diǎn)1, 3, 6, 4為出發(fā)點(diǎn),頂點(diǎn)2, 5為終止點(diǎn)的邊中,將權(quán)最小的邊(3, 2) 作為最小生成樹的第四條邊加入TE,頂點(diǎn)2加入U(xiǎn)。則U = 1, 3, 6, 4, 2,TE = (1, 3), (3, 6), (6, 4), (3, 2),V - U = 5,如圖7.16(e)所示。第82頁/共142頁838383Prim算法實(shí)例83(5) 在以頂點(diǎn)1, 3, 6, 4, 2為出發(fā)點(diǎn),頂點(diǎn)5為終止點(diǎn)的邊中,將權(quán)最小的邊(2, 5) 作為最小生成樹的第五條邊加入TE,頂點(diǎn)5加入U(xiǎn)。則U = 1, 3, 6, 4, 2, 5,TE = (1, 3), (3,
44、6), (6, 4), (3, 2), (2, 5),V - U = ,如圖 (f)所示。第83頁/共142頁84v1v2v4v3v5v66165556342v1v31v25v53v64v42(6) U = V,算法結(jié)束,U = 1, 3, 6, 4, 2, 5,TE = (1, 3), (3, 6), (6, 4), (3, 2), (2, 5),T=(U,TE)是連通網(wǎng)的最小生成樹。Prim算法實(shí)例第84頁/共142頁85 7.4.3 最小生成樹 Prim算法的數(shù)據(jù)結(jié)構(gòu)1 v22 v33 v44 v55 v6UV-Ukadjvexlowcostv16v11v15v1v2,v3,v4,v5,
45、v62adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v65adjvexlowcostv350v62v360v1,v3,v6v2,v4,v53adjvexlowcostv3500v360v1,v3,v6,v4v2,v51adjvexlowcost000v230v1,v3,v6,v4,v2v54adjvexlowcost00000v1,v3,v6,v4,v2,v5v1v2v4v3v5v66165556342closedgei.adjvex是最小生成樹中的頂點(diǎn)(即U中的頂點(diǎn))到i點(diǎn)為最小權(quán)值的那個(gè)頂點(diǎn)。closedgei第85頁/共142頁867.4.3 最小生成樹
46、 基 于 P r i m 算 法 的 最 小 生 成 樹 函 數(shù) 模 塊MiniSpanTree_PRIM ()的實(shí)現(xiàn)代碼如果頂點(diǎn)數(shù)為如果頂點(diǎn)數(shù)為n, n, 則該則該算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(nO(n2 2) ),與網(wǎng)中的邊數(shù)無關(guān),因此,與網(wǎng)中的邊數(shù)無關(guān),因此適合求邊稠適合求邊稠密的圖密的圖。而而KruskalKruskal算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(eloge)O(eloge)(e(e為為圖的邊數(shù)圖的邊數(shù)) )。因此后者。因此后者適合求適合求邊稀疏邊稀疏的網(wǎng)的網(wǎng)(Why?Why?)。第86頁/共142頁87下面是x*log(x)的函數(shù)圖,該圖說明克魯斯卡爾算法只適合
47、邊稀疏的網(wǎng)的最小生成樹。第87頁/共142頁88 7.4.3 最小生成樹Kruskal(克魯斯卡爾)算法的基本思想:設(shè)連通網(wǎng)N N(V,E)(V,E)。令最小生成樹的初始狀態(tài)為只有n n個(gè)頂點(diǎn)而無邊的非連通圖T T(V,)(V,),圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E E中選擇代價(jià)最小的邊,若該邊依附的頂點(diǎn)落在T T中不同的連通分量上,則將此邊加入T T中,否則舍去此邊而選擇下一條代價(jià)最小的邊,依次類推,直到T T中所有頂點(diǎn)都在同一連通分量上為止。Kruskal算法實(shí)例v1v2v4v3v5v66165556342v1v2v4v3v5v615342第88頁/共142頁89課堂作 業(yè)1. 一個(gè)具有n
48、個(gè)頂點(diǎn)的圖,最少有( )個(gè)連通分量,最多有( )個(gè)連通分量。 A.0 B. 1 C. n-1 D. n2. 在具有8個(gè)頂點(diǎn)的無向簡(jiǎn)單圖中,當(dāng)邊最少為多少( )時(shí)才能確保該圖一定是連通的?3.寫出一個(gè)將有向圖的鄰接表轉(zhuǎn)換為鄰接矩陣的算法。(提示:先建立一個(gè)空的鄰接矩陣,然后在鄰接表上順序取每個(gè)單鏈表中的表結(jié)點(diǎn),如果表結(jié)點(diǎn)不為空,則將鄰接矩陣中對(duì)應(yīng)單元置1.)第89頁/共142頁90作業(yè)答案作業(yè)答案1、2、 3、void AdjList_to_Mat(ALGraph G1,MGraph G2) for(i=0;iG1.vexnum;i+)for( j=0;jG1.vexnum;j+)G2.arcs
49、i j=0;for(i=0;iadjvex=1; p=p-nextarc; 第90頁/共142頁91 7.5 有向無環(huán)圖及其應(yīng)用定義: 一個(gè)無環(huán)的有向圖稱作有向無環(huán)圖(Directed AcyclineGraph),簡(jiǎn)稱DAG圖。 BEFGLMN有向樹有向樹BEFGLMNDAG圖圖BEFGLMN有向圖(含環(huán))有向圖(含環(huán))較有向樹更一般的特殊有向圖第91頁/共142頁92 7.5 有向無環(huán)圖及其應(yīng)用1、有向無環(huán)圖是描述含有公共子式的表達(dá)式的有效工具。 如對(duì)下述表達(dá)式:(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e)可以用二叉樹來表示。但實(shí)際上該表達(dá)式中有相同的子表達(dá)式,在二叉樹
50、中它們會(huì)重復(fù)出現(xiàn),這樣就比較浪費(fèi)空間,如果用有向無環(huán)圖則可以實(shí)現(xiàn)對(duì)相同子式的共享,從而節(jié)省存儲(chǔ)空間。*+e+ab*b+cd+ecdcd*+*+*+eabcd第92頁/共142頁93 7.5 有向無環(huán)圖及其應(yīng)用 檢查一個(gè)有向圖是否存在環(huán)要比無向圖復(fù)雜。 因?yàn)閷?duì)于無向圖來說,若深度優(yōu)先遍歷過程中遇到回邊(即指向已訪問過的頂點(diǎn)的邊),則必定存在環(huán); 而對(duì)于有向圖,這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上的頂點(diǎn)的弧。 但是,如果從有向圖上某個(gè)頂點(diǎn)v出發(fā)的遍歷,在DFS(v)結(jié)束之前出現(xiàn)一條從頂點(diǎn)u到頂點(diǎn)v的回邊,則有向圖中必定存在包含頂點(diǎn)v和u的環(huán)。第93頁/共142頁 2、有向無環(huán)圖也是
51、描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。 絕大多數(shù)的工程都可分為若干個(gè)活動(dòng)的子工程,而這些子工程之間,通常都受著一定條件的約束。 對(duì)整個(gè)工程和系統(tǒng),人們關(guān)心的是兩個(gè)方面的問題人們關(guān)心的是兩個(gè)方面的問題: 一是工程能否順利進(jìn)行一是工程能否順利進(jìn)行; 二是工程完成所必須的最短時(shí)間二是工程完成所必須的最短時(shí)間。 對(duì)應(yīng)于有向圖,即為進(jìn)行拓?fù)渑判蛲負(fù)渑判蚝颓箨P(guān)鍵路徑求關(guān)鍵路徑的操作。94第94頁/共142頁95 7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判蚱颍喝艏?X 上的關(guān)系 R 是傳遞的、自反的、反對(duì)稱的,則稱 R 是集合 X 上的偏序關(guān)系。偏序是指集合中僅有部分成員之間可比較。全序:若關(guān)系
52、R 是集合 X 上的偏序關(guān)系,如果對(duì)于每個(gè) x, y 屬于 X,必有 x R y 或 y R x ,則稱 R 是集合 X 上的全序關(guān)系。全序是指集合中全體成員之間均可比較。V2V1V4V3偏序偏序V1V3V2V4全序(拓?fù)溆行颍┤颍ㄍ負(fù)溆行颍┩負(fù)渑判颍和負(fù)渑判颍河赡硞€(gè)集合由某個(gè)集合上的上的一個(gè)一個(gè)偏序偏序得到該集合上的一個(gè)得到該集合上的一個(gè)全序全序的的操作操作。第95頁/共142頁96 7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判蛞粋€(gè)表示偏序的有向圖可用來表示一個(gè)流程圖,它或者是一個(gè)施工流程圖,或者是一個(gè)產(chǎn)品生產(chǎn)流程圖。圖中每一條有向邊表示兩個(gè)子工程之間的次序關(guān)系(領(lǐng)先關(guān)系)。 這種用頂點(diǎn)
53、表示活動(dòng),用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex Network),簡(jiǎn)稱AOV網(wǎng)。AOV網(wǎng)的主要用途:描述工程項(xiàng)目或系統(tǒng)進(jìn)行的次序。在網(wǎng)中,若從頂點(diǎn)i到頂點(diǎn)j有一條有向路徑,則i是j的前驅(qū),j就是i的后繼。在AOV網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán),因?yàn)槌霈F(xiàn)有向環(huán),就意味著某個(gè)活動(dòng)以自己為先決條件。 因此,對(duì)給定的AOV網(wǎng)需首先判斷網(wǎng)中是否有環(huán)。檢測(cè)的辦法是對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?,若網(wǎng)中所有頂點(diǎn)都在其拓?fù)溆行蛐蛄兄?,則該AOV網(wǎng)必定不存在環(huán)。第96頁/共142頁97 7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判蚨x:如果在AOV網(wǎng)中,從頂點(diǎn)vi
54、到頂點(diǎn)vj存在一條路徑,則在線性序列中,頂點(diǎn)vi一定排在頂點(diǎn)vj之前。具有這種性質(zhì)的線性序列稱為拓?fù)湫蛄型負(fù)湫蛄?,?gòu)造拓?fù)湫蛄械牟僮鞣Q為拓拓?fù)渑判驌渑判?。如下圖的一個(gè)拓?fù)湫蛄袨椋ㄔ搱D有多個(gè)拓?fù)湫蛄校?C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8)C4C5C1C2C3C7C12C9C10C11C6C8第97頁/共142頁98 7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判蛉绾芜M(jìn)行拓?fù)渑判蚰兀?(1)在有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之; (2)從圖中刪去該頂點(diǎn)和所有以它為尾的弧。 重復(fù)(1)、(2)直至全部頂點(diǎn)都已輸出,或者當(dāng)前圖中不存
55、在無前驅(qū)的頂點(diǎn)為止,后一種情況說明圖中存在環(huán)。以下圖為例:V2V5V5V1V2V4V3V6V5V2V3V5V1V4V2V3V6V5V4V2V3V5V6V1V4V3V2V5第98頁/共142頁99 7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判驅(qū)嵗龑?shí)例:下述集合 M 代表課程的集合,其中,C1代表數(shù)學(xué), C2代表程序設(shè)計(jì),C3代表離散數(shù)學(xué),C4代表匯編程序設(shè)計(jì),C5代表數(shù)據(jù)結(jié)構(gòu),C6代表結(jié)構(gòu)化程序設(shè)計(jì), C7代表編譯原理。 關(guān)系 R 課程學(xué)習(xí)的先后關(guān)系,如數(shù)學(xué)必須在離散數(shù)學(xué)之前學(xué)習(xí)。要求排一張學(xué)習(xí)的先后次序表。C1C3C2C4C6C5C7C1C3C2C7C5C6C4數(shù)學(xué)數(shù)學(xué)程序設(shè)計(jì)程序設(shè)計(jì)離散數(shù)
56、學(xué)離散數(shù)學(xué)匯編程序設(shè)計(jì)匯編程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)編譯原理編譯原理第99頁/共142頁100 7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判?如何在計(jì)算機(jī)中實(shí)現(xiàn)?需要一個(gè)數(shù)組存放所有頂點(diǎn)的入度(入度為0說明該頂點(diǎn)沒有前驅(qū))。而刪去該頂點(diǎn)及以它為尾的弧,只要使該弧的弧頭頂點(diǎn)的入度減1就可以了。由于在圖中入度為0的頂點(diǎn)數(shù)可能較多,為了避免重復(fù)檢測(cè)入度為0的頂點(diǎn),可設(shè)一棧來存放所有入度為0的頂點(diǎn)。01012345611213indegree0棧棧C1C3C2C7C5C6C4C1C21201234563446C3C4C55C6C766第100頁/共142頁101 7.5 有
57、向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判?算法如下:Status TopologicalSort(ALGraph G) 采用鄰接表存儲(chǔ) FindInDegree(G, indegree); 對(duì)各頂點(diǎn)求入度InitStack(S); 建零入度頂點(diǎn)棧Sfor ( i=0; inextarc ) k=p-adjvex; if ( !(-indegreek) ) Push(S, k); 對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1,若入度減為0 則入棧if ( countG.vexnum ) return ERROR; 該有向圖有回路 else return OK;第101頁/共142頁102 7.5 有向無環(huán)圖及其
58、應(yīng)用7.5.1 拓?fù)渑判蛩惴ǖ臅r(shí)間效率算法的時(shí)間效率:(1)建立各頂點(diǎn)的入度的時(shí)間復(fù)雜度為O(e);(2)建入度為0的棧的時(shí)間復(fù)雜度為O(n);(3)在拓?fù)渑判蜻^程中,若有向圖無環(huán),則每個(gè)頂點(diǎn)進(jìn)棧一次,出棧一次,入度減1的操作在while循環(huán)總共執(zhí)行e次,所以,總的時(shí)間復(fù)雜度為O(n+e)。當(dāng)有向圖無環(huán)時(shí),也可利用深度優(yōu)先搜索進(jìn)行拓?fù)渑判?,因?yàn)閳D中無環(huán),則由圖中某個(gè)頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索時(shí),最先退出DFS函數(shù)的頂點(diǎn)即為出度為0的頂點(diǎn),是拓?fù)溆行蛐蛄兄凶詈笠粋€(gè)頂點(diǎn)。由此,按退出DFS函數(shù)的先后記錄下來的頂點(diǎn)序列即為逆向的拓?fù)溆行蛐蛄?。?02頁/共142頁103 7.5 有向無環(huán)圖及其應(yīng)用7.
59、5.2 關(guān)鍵路徑 AOE網(wǎng)(Activity On Edge):即用邊表示活動(dòng)的網(wǎng),是帶權(quán)的有序無環(huán)圖,其中頂點(diǎn)表示事件,弧表示活動(dòng),權(quán)表示活動(dòng)持續(xù)的時(shí)間。如圖所示: 通常,AOE網(wǎng)的主要用途:(1)估算工程完成的時(shí)間;(2)找出影響工程進(jìn)度的關(guān)鍵活動(dòng)。V2V1V3V5V7V8V9V4V6a6=2a1=6a4=1a7=9a10=2a11=4a9=4a3=5a2=4a5=1a8=7AOE網(wǎng)網(wǎng)第103頁/共142頁104 7.5 有向無環(huán)圖及其應(yīng)用7.5.2 關(guān)鍵路徑 由于整個(gè)工程只有一個(gè)開始點(diǎn),一個(gè)完成點(diǎn),故在正常情況(無環(huán))下只有一個(gè)入度為0 的點(diǎn)(源點(diǎn)源點(diǎn))和一個(gè)出度為0的點(diǎn)(匯點(diǎn)匯點(diǎn))。由
60、于有些工程可并行地進(jìn)行,所以完成工程的最短時(shí)間即為從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度(路徑長(zhǎng)度指的是路徑上各持續(xù)時(shí)間之和)。 路徑最長(zhǎng)的路徑叫關(guān)鍵路徑關(guān)鍵路徑(Critical Path)。第104頁/共142頁7.5 有向無環(huán)圖及其應(yīng)用事件事件Vi的最早發(fā)生時(shí)間的最早發(fā)生時(shí)間:從開始點(diǎn)v1到vi的最長(zhǎng)路徑長(zhǎng)度。用ve(i)表示事件事件Vi的最遲發(fā)生時(shí)間的最遲發(fā)生時(shí)間:在不推遲整個(gè)工期的前提下,事件vi允許的最遲發(fā)生時(shí)間。用vl(i)表示。活動(dòng)活動(dòng)ai的最早開始時(shí)間的最早開始時(shí)間:即為ai的弧尾頂點(diǎn)(事件)的最早發(fā)生時(shí)間。用e(i)表示?;顒?dòng)活動(dòng)ai的最遲開始時(shí)間的最遲開始時(shí)間:在保證不推遲整個(gè)
61、工程的完成時(shí)間的前提下,活動(dòng)ai的最遲開始時(shí)間。用l(i)表示。105V2V1V3V5V7V8V9V4V6a6=2a1=6a4=1a7=9a10=2a11=4a9=4a3=5a2=4a5=1a8=7AOE網(wǎng)網(wǎng)v: vertexa: activitye: early l: late第105頁/共142頁106 7.5 有向無環(huán)圖及其應(yīng)用7.5.2 關(guān)鍵路徑l(i) - e(i) 意味著完成活動(dòng)ai的時(shí)間余量。關(guān)鍵活動(dòng)關(guān)鍵活動(dòng):l(i) = e(i)的活動(dòng)。 顯然,關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。因此,提前非關(guān)鍵活動(dòng)并不能加快工程的進(jìn)度。所以分析關(guān)鍵路徑的目的是判別哪些是關(guān)鍵活動(dòng),以便提高關(guān)鍵活
62、動(dòng)的工序,縮短整個(gè)工期。 判別關(guān)鍵活動(dòng)就是要找l(i) = e(i)的活動(dòng),因此必須首先求出l(i) 和 e(i),為此,必須先求出事件的最早發(fā)生時(shí)間ve(j)和最遲發(fā)生時(shí)間vl(j)。如果活動(dòng)ai由弧表示,其持續(xù)時(shí)間為dut(),則有如下的關(guān)系:e(i) = ve(j)l(i) = vl(k) - dut() 所以下面的問題就是如何求ve(j)和vl(j)了。k dut()dut()a ai ij第106頁/共142頁107 7.5 有向無環(huán)圖及其應(yīng)用7.5.2 關(guān)鍵路徑求求ve(j)和和vl(j)方法方法:(1)ve(0) = 0開始向前遞推:ve(j) = Maxve(i) + dut(
63、) T, j = 1,2,n-1, T是所有以第j個(gè)頂點(diǎn)為弧頭的弧的集合。(2)從vl(n-1) = ve(n-1)起向后遞推:vl(i) = Minvl(j) - dut() S, i = n-2,n-1,.,0,S是所有以第i個(gè)頂點(diǎn)為弧尾的弧的集合。 這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。也就是說:ve(j-1)必須在vj的所有前驅(qū)的最早發(fā)生時(shí)間求得之后才能確定vl(j-1)則必須在vj的所有后繼的最遲發(fā)生時(shí)間求得之后才能確定。第107頁/共142頁108 7.5 有向無環(huán)圖及其應(yīng)用V0Vj3 35 512128888ve(Vj) = 3、5、12、88的最大值的
64、最大值 88起點(diǎn)起點(diǎn)0 0ViVn-1vl(Vi) = 取取 10-2、10-4、10-3、10-7的最小值的最小值 3 或或 10 - 最長(zhǎng)路徑最長(zhǎng)路徑 72 24 43 37 710101010匯點(diǎn)匯點(diǎn)V0Vjve(Vj) = Maxve(i) + dut() TVuVvVwVx2 23 39 982821 12 23 36 6由源點(diǎn)至匯點(diǎn)由源點(diǎn)至匯點(diǎn)ViVn-1vl(i) = Minvl(j) - dut() S10101010匯點(diǎn)匯點(diǎn)VuVvVwVx8 88 85 51 12 21 12 29 9由匯點(diǎn)至源點(diǎn)由匯點(diǎn)至源點(diǎn)第108頁/共142頁109 7.5 有向無環(huán)圖及其應(yīng)用7.5.2
65、 關(guān)鍵路徑由此,可以得到求關(guān)鍵路徑的算法求關(guān)鍵路徑的算法:(1)輸入e條弧,建立AOE網(wǎng)。(2)從源點(diǎn)v1出發(fā),令ve0 = 0,按拓?fù)溆行蚯蟾黜旤c(diǎn)的最早發(fā)生時(shí)間vei(1in-1),如果得到的拓?fù)湫蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n,說明網(wǎng)中存在環(huán),不能求關(guān)鍵路徑,算法終止;否則執(zhí)行步驟(3)。(3)從匯點(diǎn)vn出發(fā),令vln-1 = ven-1;按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vli(n-2i0);(4)根據(jù)個(gè)各頂點(diǎn)的ve和vl值,求每條弧s的e(s)和l(s)。若某條弧滿足e(s) = l(s),則為關(guān)鍵活動(dòng)。第109頁/共142頁110 7.5 有向無環(huán)圖及其應(yīng)用7.5.2 關(guān)鍵路徑由于
66、求關(guān)鍵路徑需要拓?fù)湫蛄泻湍嫱負(fù)湫蛄校虼?,需要利用拓?fù)渑判虻姆椒?。?duì)拓?fù)渑判蛏约訉?duì)拓?fù)渑判蛏约有薷募纯汕蟮酶黜旤c(diǎn)的修改即可求得各頂點(diǎn)的ve和和vl值值,修改方法如下: (1)對(duì)vei設(shè)初值0。 (2)增加求vj的直接后繼vk的最早發(fā)生時(shí)間的操作:若vej+dut() vek,則vek = vej+dut()。 (3)為了求逆拓?fù)湫蛄校恍枰淹負(fù)湫蛄腥霔#?那么出棧的序列即為逆拓?fù)湫蛄?。?10頁/共142頁111 7.5 有向無環(huán)圖及其應(yīng)用7.5.2 關(guān)鍵路徑實(shí)例:求事實(shí)例:求事件頂點(diǎn)的最件頂點(diǎn)的最早發(fā)生時(shí)間早發(fā)生時(shí)間V1V2V3V4V5V6正向拓?fù)渑判颍赫蛲負(fù)渑判颍豪猛負(fù)渑判蛩惴ㄇ笫录旤c(diǎn)的最早發(fā)生時(shí)利用拓?fù)渑判蛩惴ㄇ笫录旤c(diǎn)的最早發(fā)生時(shí)間的執(zhí)行步驟:間的執(zhí)行步驟:1、設(shè)每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間為、設(shè)每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間為0,將入度,將入度為零的頂點(diǎn)進(jìn)棧。為零的頂點(diǎn)進(jìn)棧。2、將棧中入度為零的頂點(diǎn)、將棧中入度為零的頂點(diǎn)V取取出,并壓入另出,并壓入另一棧,用于形成逆向拓?fù)渑判虻男蛄?。一棧,用于形成逆向拓?fù)渑判虻男蛄小?、根據(jù)鄰接表找到頂點(diǎn)、根據(jù)鄰接表找到頂點(diǎn)V的所有的鄰接的所有的鄰
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 幼兒體育游戲課件
- 蘇教版四年級(jí)上冊(cè)數(shù)學(xué)-第7單元-整數(shù)四則混合運(yùn)算階段小達(dá)標(biāo)課件11
- 蘇教初中生物七下《9第3節(jié)-膳食指南與食品安全》-原創(chuàng)精美課件-4
- 27.1圖形的相似(吳麗倩)(教育精品)
- 高中化學(xué)熱力學(xué)復(fù)習(xí) 4 化學(xué)中的耦合現(xiàn)象課件
- 空調(diào)水系統(tǒng)閥門的設(shè)計(jì)與選擇
- 川教版八年級(jí)歷史下冊(cè)第8課農(nóng)村和城市的改革課件
- 五年級(jí)的上冊(cè)語音復(fù)習(xí)課 (2)課件
- DSP應(yīng)用課程設(shè)計(jì)課件 第4講 利用DSP實(shí)現(xiàn)信號(hào)濾波
- 同33同角三角函數(shù)的基本關(guān)系(公開課)-PPT
- 16橋[1] (2)(教育精品)
- 高中化學(xué) 3.2.3 鐵的重要化合物 氧化性還原性判斷課件 新人教版必修1 (12)
- 記承天寺夜游(教育精品)
- 端午的鴨蛋(PPT)(教育精品)
- 人教版《節(jié)約用水》課件