數(shù)據(jù)結(jié)構(gòu) 圖PPT課件

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)； 而對于圖來說，圖中任意兩個(gè)結(jié)點(diǎn)之間都可以直接相關(guān)。BCADE姓 名學(xué) 號 性 別年 齡 健康情況王小林790631男 18 健康陳 紅790632女 20 一般劉建平790633男 21 健康張立立790634男 17 神經(jīng)衰弱 . . .第2頁/共142頁 圖的用途極其廣泛，已滲入到語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)等其他分支學(xué)科當(dāng)中。 在本課程當(dāng)中，我們主要討論如何在計(jì)算機(jī)上實(shí)現(xiàn)圖的操作，因此主要學(xué)習(xí)圖的存儲結(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)的偶對。 E可以是空集，若E為空，則G中只有頂點(diǎn)沒有邊。 在圖中，數(shù)據(jù)元素通常稱為頂點(diǎn)(vertex)。第4頁/共142頁57.1 圖的定義和術(shù)語 若頂點(diǎn)之間的偶對是有方向的，稱此圖為有向圖(digraph); 有方向偶對用尖括號括起來，并稱之為弧(arc)。如v, wV，E，則是有向圖中從頂點(diǎn)v到頂點(diǎn)w的一條弧，v是弧尾(tail)(始點(diǎn))，w是弧頭(head)(終點(diǎn))。ABCD有向圖有向圖 G1第5頁/共142頁 若頂點(diǎn)之間的偶對是無方向的，稱此圖為無向圖(undigraph). 無方向偶對用圓括括起來，通常稱之為邊(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 =（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)到其自身的弧或邊，那么： 對于有n個(gè)頂點(diǎn)的無向圖，邊的最大數(shù)目為:n(n-1)/2 對于n個(gè)頂點(diǎn)的有向圖，弧的最大數(shù)目為:n(n-1)第8頁/共142頁97.1 圖的定義和術(shù)語幾種圖的定義：完全圖(Completed 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)：對于無向圖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ù)語每條邊或弧都帶權(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)一般地，對于無向圖和有向圖，如果頂點(diǎn)vi的度記為TD(vi)，那么一個(gè)有n個(gè)項(xiàng)點(diǎn)，e條邊或弧的圖，niivTDe12/ )( 圖論中，有一個(gè)十分簡單但有很有用的關(guān)于頂點(diǎn)的度的定理，即握手定理：第12頁/共142頁137.1 圖的定義和術(shù)語 路徑：在圖中從頂點(diǎn)v v到頂點(diǎn)v v所經(jīng)過的所有頂點(diǎn)的序列。有向圖的路徑也是有向的。 路徑長度：路徑上的邊或弧的數(shù)目。 簡單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 回路或環(huán)：序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎ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無向圖無向圖G2的子圖的子圖第14頁/共142頁15 7.1 圖的定義和術(shù)語連通：在無向圖中，如果從v到v存在路徑，則稱v和v是連通的。連通圖：無向圖G中如果任意兩個(gè)頂點(diǎn)vi,vj之間都是連通的。連通分量：無向圖中的極大連通子圖。強(qiáng)連通圖：在有向圖G中，如果對于每一對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è)連通分量連通分量( (無向圖無向圖中的中的極大連通子圖極大連通子圖)第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è)連通圖的生成樹，是含有該連通圖的全部頂點(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 圖的存儲結(jié)構(gòu)22第22頁/共142頁23 7.2 圖的存儲結(jié)構(gòu)圖存儲的特殊性： 頂點(diǎn)之間的關(guān)系無法用他們在內(nèi)存中的存儲位置來表示。 用多重鏈表來表示圖是自然的事情，它用一個(gè)由一個(gè)數(shù)據(jù)域和多個(gè)指針域組成的結(jié)點(diǎn)表示圖中的一個(gè)頂點(diǎn)。其中數(shù)據(jù)域存放該頂點(diǎn)的信息，指針域存放指向其鄰接點(diǎn)的地址。 常用的存儲方法有：鄰接矩陣表示法鄰接表表示法十字鏈表表示法鄰接多重表表示法第23頁/共142頁24 7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法（鄰接矩陣表示法） 圖需要存儲的信息：頂點(diǎn)和?。ɑ蜻叄?。 圖的數(shù)組表示法：用兩個(gè)數(shù)組分別存放圖中頂點(diǎn)的信息（數(shù)據(jù)元素）和圖中弧或邊的信息（數(shù)據(jù)元素之間的關(guān)系）。 頂點(diǎn)信息的存儲方法：一維數(shù)組頂點(diǎn)類型：整型、字符型等 弧或邊信息的存儲方法：二維數(shù)組即鄰接矩陣弧或邊的信息類型：無權(quán)圖: 0或1；有權(quán)圖（網(wǎng)）: 權(quán)值類型第24頁/共142頁25 7.2 圖的存儲結(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 至至 j j 沒有一條弧。沒有一條弧。 注意注意：Aii = 0Aii = 0。頂點(diǎn)頂點(diǎn) 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 圖的存儲結(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 至至 j j 沒有一條邊。沒有一條邊。 0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE表示成右圖矩陣無向圖的鄰接矩陣是對稱矩陣，有向圖的鄰接矩陣不一定是對稱矩陣。第26頁/共142頁277.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法：無向圖的鄰接矩陣無向圖的鄰接矩陣 注意注意: : Aii = 0Aii = 0 無向圖無向圖頂點(diǎn)頂點(diǎn)i i 的度的度: : 第第i i行或行或i i列之和列之和( (因?yàn)槭菍ΨQ矩陣因?yàn)槭菍ΨQ矩陣) )。 TD(v TD(vi i) )= 無向圖的總邊數(shù)無向圖的總邊數(shù)等于該矩陣上三角或下三角元素之和。等于該矩陣上三角或下三角元素之和。第27頁/共142頁28 7.2 圖的存儲結(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 7.2 圖的存儲結(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)系類型。對無權(quán)圖，用1或表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。VRType，InfoType都是要在主函數(shù)中定義的。有向圖，有向網(wǎng)，無向圖，無向網(wǎng)第29頁/共142頁30 7.2 圖的存儲結(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í)間效率低。有向圖， Kind = 0；有向網(wǎng)， Kind = 1；無向圖，Kind = 2；無向網(wǎng)， Kind = 3。第30頁/共142頁31 7.2 圖的存儲結(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.vexnum; +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)在圖中存儲的位置 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)的對稱性填充矩陣的對稱部分return OK;第31頁/共142頁32 7.2.2 鄰接表表示法 鄰接表（Adjacency List）是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。對圖中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊（對有向圖是以頂點(diǎn)vi為尾的?。?。 鄰接表中的每個(gè)結(jié)點(diǎn)由三個(gè)域組成： 數(shù)據(jù)域info指向存儲和弧或邊相關(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è)鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)：data存儲頂點(diǎn)vi的名或其他有關(guān)的名或其他有關(guān)信息firstarc指向依附于該頂點(diǎn)的第一條弧或邊所有表頭結(jié)點(diǎn)通常以順序結(jié)構(gòu)（一維數(shù)組）的形式存儲，以便訪問任一頂點(diǎn)的鏈表。第33頁/共142頁34 7.2 圖的存儲結(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)、e條邊，則它的鄰接表需要 個(gè)頭結(jié)點(diǎn)和 個(gè)表結(jié)點(diǎn)。 在邊稀疏的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間。n2e第35頁/共142頁36 7.2 圖的存儲結(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 圖的存儲結(jié)構(gòu)7.2.2 鄰接表表示法#define MAX_VERTEX_NUM 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;/ 圖的當(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頁/共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)識頂點(diǎn)是否已被訪問過用于標(biāo)識頂點(diǎn)是否已被訪問過Status ( * VisitFunc) (int v); / 函數(shù)變量函數(shù)變量void DFSTraverse( Graph G, Status ( * Visit)(int v) /對圖做深度優(yōu)先遍歷對圖做深度優(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ù)FirstAdjVex()用來找v的第一個(gè)鄰接點(diǎn)返回v的（相對于w的）下一個(gè)鄰接頂點(diǎn)的序號。若w是v的最后一個(gè)鄰接點(diǎn)，則返回1。第53頁/共142頁54存儲結(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的(相對于w的)下一個(gè)鄰接頂點(diǎn)的序號，若w是v的最后一個(gè)鄰接頂點(diǎn)，則返回-1 int i,j=0,k1,k2; k1=LocateVex(G,v); / k1為頂點(diǎn)v在圖G中的序號 k2=LocateVex(G,w); / k2為頂點(diǎn)w在圖G中的序號 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的(相對于w的)下一個(gè)鄰接頂點(diǎn)的序號 第55頁/共142頁567.3.1 深度優(yōu)先搜索 非連通圖的深度優(yōu)先遍歷CABDEGF第56頁/共142頁57上圖的鄰接矩陣及深度優(yōu)先遍歷 rowColABCDEFGA (一）01 01000B10001 00C (二）000001 (1) 0D1000001E0100001 F0010000G0001 100CABDEGF第57頁/共142頁58上圖的鄰接矩陣存儲下的深度優(yōu)先遍歷過程 以A為起始點(diǎn)進(jìn)行DFS，在A所在行找到第一個(gè)值不為0且未被訪問的元素B，訪問之；在B所在行找第一個(gè)值不為0且未被訪問過的元素E一直到D ，訪問之；此時(shí)D所在行中的兩個(gè)非0元素對應(yīng)的頂點(diǎn)均已被訪問過。此時(shí)，需返回到 ，找其所在行中下一個(gè)不為0的元素， 為其行中最后一個(gè)元素，需繼續(xù)返回到就這樣，一直返回到A（一）處，此后再無法返回。 然后排查還有沒有未被訪問過的頂點(diǎn)，于是找到了C（二），訪問之；同樣找到F并訪問之，得到最終的深度優(yōu)先遍歷序列:A B E G D C F第58頁/共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ù)即可。鄰接表結(jié)構(gòu)及深度優(yōu)先遍歷第60頁/共142頁617.3.1 深度優(yōu)先搜索 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度： 對前述算法來說，對圖中每個(gè)頂點(diǎn)至多調(diào)用一次對前述算法來說，對圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)，函數(shù)，因此，遍歷圖的過程實(shí)質(zhì)上是對每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。因此，遍歷圖的過程實(shí)質(zhì)上是對每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。耗費(fèi)時(shí)間取決于其存儲結(jié)構(gòu)。耗費(fèi)時(shí)間取決于其存儲結(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ù)雜度： 鄰接表（鄰接表（圖的鏈?zhǔn)酱鎯Y(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之前還需對數(shù)組之前還需對數(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，并均標(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)的訪問次序以序號為準(zhǔn)，序號小的先訪問。從v v1 1出發(fā)進(jìn)行搜索的訪問序列：第64頁/共142頁657.3.2 廣度優(yōu)先搜索對于廣度優(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 7.4 圖的連通性問題7.4.1 無向圖的連通分量和生成樹 在對無向圖進(jìn)行遍歷時(shí)，對于連通圖，從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點(diǎn)；而對于非連通圖，則需從多個(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 無向圖的連通分量和生成樹 在對連通圖進(jìn)行搜索時(shí)，搜索過程中經(jīng)歷的所有邊和圖中所有的頂點(diǎn)構(gòu)成了連通圖的一個(gè)極小連通子圖，即連通圖的生成樹。 稱由深度優(yōu)先搜索得到的生成樹為深度優(yōu)先生成樹，而由廣度優(yōu)先搜索得到的生成樹稱廣度優(yōu)先生成樹。 對于非連通圖，其中的每一個(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)是剩余的邊的集合。顯然，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）作生成森林的存儲結(jié)構(gòu)，則形成非連通圖的深度優(yōu)先生成森林的算法 typedef struct CSNode /二叉鏈表（孩子-兄弟） ElemType data; struct CSNode *firstchild, *nextsibling; CSNOde, *CSTree;第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 Tree，MST)(簡稱最小生成樹最小生成樹)。一棵生成樹的代價(jià)就是該樹上所有邊的權(quán)值之和。第73頁/共142頁747.4.3 最小生成樹構(gòu)造最小生成樹可以有多種算法，最常用的算法利用了最小生成樹的一種簡稱為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,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=開始，重復(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) 在以頂點(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頁8282Prim算法實(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, 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,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 最小生成樹 基 于 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ù)圖，該圖說明克魯斯卡爾算法只適合邊稀疏的網(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個(gè)頂點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有（ ）個(gè)連通分量。 A.0 B. 1 C. n-1 D. n2. 在具有8個(gè)頂點(diǎn)的無向簡單圖中，當(dāng)邊最少為多少（ ）時(shí)才能確保該圖一定是連通的？3.寫出一個(gè)將有向圖的鄰接表轉(zhuǎn)換為鄰接矩陣的算法。（提示：先建立一個(gè)空的鄰接矩陣，然后在鄰接表上順序取每個(gè)單鏈表中的表結(jié)點(diǎn)，如果表結(jié)點(diǎn)不為空，則將鄰接矩陣中對應(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.arcsi 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)，簡稱DAG圖。 BEFGLMN有向樹有向樹BEFGLMNDAG圖圖BEFGLMN有向圖（含環(huán)）有向圖（含環(huán)）較有向樹更一般的特殊有向圖第91頁/共142頁92 7.5 有向無環(huán)圖及其應(yīng)用1、有向無環(huán)圖是描述含有公共子式的表達(dá)式的有效工具。 如對下述表達(dá)式：(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e)可以用二叉樹來表示。但實(shí)際上該表達(dá)式中有相同的子表達(dá)式，在二叉樹中它們會(huì)重復(fù)出現(xiàn)，這樣就比較浪費(fèi)空間，如果用有向無環(huán)圖則可以實(shí)現(xiàn)對相同子式的共享，從而節(jié)省存儲空間。*+e+ab*b+cd+ecdcd*+*+*+eabcd第92頁/共142頁93 7.5 有向無環(huán)圖及其應(yīng)用 檢查一個(gè)有向圖是否存在環(huán)要比無向圖復(fù)雜。 因?yàn)閷τ跓o向圖來說，若深度優(yōu)先遍歷過程中遇到回邊（即指向已訪問過的頂點(diǎn)的邊），則必定存在環(huán)； 而對于有向圖，這條回邊有可能是指向深度優(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)圖也是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過程的有效工具。 絕大多數(shù)的工程都可分為若干個(gè)活動(dòng)的子工程，而這些子工程之間，通常都受著一定條件的約束。 對整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問題人們關(guān)心的是兩個(gè)方面的問題： 一是工程能否順利進(jìn)行一是工程能否順利進(jìn)行； 二是工程完成所必須的最短時(shí)間二是工程完成所必須的最短時(shí)間。 對應(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 是傳遞的、自反的、反對稱的，則稱 R 是集合 X 上的偏序關(guān)系。偏序是指集合中僅有部分成員之間可比較。全序：若關(guān)系 R 是集合 X 上的偏序關(guān)系，如果對于每個(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)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex Network)，簡稱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)以自己為先決條件。 因此，對給定的AOV網(wǎng)需首先判斷網(wǎng)中是否有環(huán)。檢測的辦法是對有向圖構(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到頂點(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)前圖中不存在無前驅(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ù)學(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ù)檢測入度為0的頂點(diǎn)，可設(shè)一棧來存放所有入度為0的頂點(diǎn)。01012345611213indegree0棧棧C1C3C2C7C5C6C4C1C21201234563446C3C4C55C6C766第100頁/共142頁101 7.5 有向無環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判?算法如下：Status TopologicalSort(ALGraph G) 采用鄰接表存儲 FindInDegree(G, indegree); 對各頂點(diǎn)求入度InitStack(S); 建零入度頂點(diǎn)棧Sfor ( i=0; inextarc ) k=p-adjvex; if ( !(-indegreek) ) Push(S, k); 對i號頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1，若入度減為0 則入棧if ( countG.vexnum ) return ERROR; 該有向圖有回路 else return OK;第101頁/共142頁102 7.5 有向無環(huán)圖及其應(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.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)）。由于有些工程可并行地進(jìn)行，所以完成工程的最短時(shí)間即為從開始點(diǎn)到完成點(diǎn)的最長路徑的長度（路徑長度指的是路徑上各持續(xù)時(shí)間之和）。 路徑最長的路徑叫關(guān)鍵路徑關(guān)鍵路徑（Critical Path）。第104頁/共142頁7.5 有向無環(huán)圖及其應(yīng)用事件事件Vi的最早發(fā)生時(shí)間的最早發(fā)生時(shí)間：從開始點(diǎn)v1到vi的最長路徑長度。用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è)工程的完成時(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)鍵活動(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() 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的最大值的最大值 88起點(diǎn)起點(diǎn)0 0ViVn-1vl(Vi) = 取取 10-2、10-4、10-3、10-7的最小值的最小值 3 或或 10 - 最長路徑最長路徑 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 關(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)鍵路徑由于求關(guān)鍵路徑需要拓?fù)湫蛄泻湍嫱負(fù)湫蛄?，因此，需要利用拓?fù)渑判虻姆椒?。對拓?fù)渑判蛏约訉ν負(fù)渑判蛏约有薷募纯汕蟮酶黜旤c(diǎn)的修改即可求得各頂點(diǎn)的ve和和vl值值，修改方法如下： （1）對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的所有的鄰接的所有的鄰