第七章圖圖基本概念圖存放表示圖遍歷與連通性最小生成樹最短路徑活動網(wǎng)絡(luò)1數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第1頁7.1圖基本概念圖定義

圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間關(guān)系集合組成一個數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x某個數(shù)據(jù)對象}

是頂點(diǎn)有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是頂點(diǎn)之間關(guān)系有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y(tǒng)一條通路。2數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第2頁

有向圖與無向圖完全圖3數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第3頁

鄰接頂點(diǎn)

假如(u,v)是E(G)中一條邊，則稱u與v互為鄰接頂點(diǎn)。子圖

設(shè)有兩個圖G＝(V,E)和G’＝(V’,E’),若V’V且E’

E,則稱圖G’是圖G子圖。4數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第4頁頂點(diǎn)度

一個頂點(diǎn)v度是與它相關(guān)聯(lián)邊條數(shù)，記作TD(v)。頂點(diǎn)v入度

是以v為終點(diǎn)(弧頭)有向邊條數(shù),記作ID(v);頂點(diǎn)v

出度是以v為始點(diǎn)(弧尾)有向邊條數(shù),記作OD(v)。路徑

在圖G＝(V,E)中,若從頂點(diǎn)

vi出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)

vp1,vp2,…,vpm，抵達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vi

vp1vp2...vpm

vj)

為從頂點(diǎn)vi到頂點(diǎn)vj路徑。它經(jīng)過邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E邊。5數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第5頁路徑長度非帶權(quán)圖路徑長度是指此路徑上邊條數(shù)。帶權(quán)圖路徑長度是指路徑上各邊權(quán)之和。簡單路徑

若路徑上各頂點(diǎn)v1,v2,...,vm均不相互重復(fù),則稱這么路徑為簡單路徑。回路

若路徑上第一個頂點(diǎn)v1與最終一個頂點(diǎn)vm重合,則稱這么路徑為回路或環(huán)。簡單回路

除了第一個頂點(diǎn)和最終一個頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)回路叫簡單回路

6數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第6頁例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，17數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第7頁7.2圖存放結(jié)構(gòu)1）存放特點(diǎn)在圖鄰接矩陣表示中，有一個統(tǒng)計各個頂點(diǎn)信息頂點(diǎn)表；還有一個表示各個頂點(diǎn)之間關(guān)系鄰接矩陣。2）鄰接矩陣設(shè)圖A=(V,E)是一個有n個頂點(diǎn)圖，則圖鄰接矩陣是一個二維數(shù)組A[n][n]，定義：7.2.1鄰接矩陣(AdjacencyMatrix)表示法8數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第8頁9數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第9頁

網(wǎng)絡(luò)鄰接矩陣10數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第10頁3）數(shù)據(jù)類型描述#defineMaxVNum100/*最大頂點(diǎn)數(shù)設(shè)為100*/typedefXXXVertexType;/*頂點(diǎn)類型*/鄰接矩陣類型：typedefintEdgeType;/*邊權(quán)值設(shè)為整型*/typedefstructArcCell{VertexTypeadj;InfoType*Info;//存弧相關(guān)信息}ArcCell,AdjMatrix[MaxVNum][MaxVNum]圖類型：typedefstruct{VertexTypevexs[MaxVNum];/*頂點(diǎn)表*/AdjMatrixarcs;/*鄰接矩陣，即邊表*/intvexnum,arcnum;/*圖頂點(diǎn)數(shù)和邊數(shù)*/}Mgragh;/*Maragh是以鄰接矩陣存放圖*/11數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第11頁4）圖創(chuàng)建

思緒：12數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第12頁7.2.2鄰接表(AdjacencyList)1)存放特點(diǎn)對于圖G中每個頂點(diǎn)vi，把全部鄰接于vi頂點(diǎn)vj鏈成一個單鏈表，這個單鏈表稱為頂點(diǎn)vi鄰接表；將全部點(diǎn)鄰接表表頭放到數(shù)組中，就組成了圖鄰接表

13數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第13頁特點(diǎn)無向圖中頂點(diǎn)Vi度為第i個單鏈表中結(jié)點(diǎn)數(shù)有向圖中頂點(diǎn)Vi出度為第i個單鏈表中結(jié)點(diǎn)個數(shù)頂點(diǎn)Vi入度為整個單鏈表中鄰接點(diǎn)域值是i結(jié)點(diǎn)個數(shù)逆鄰接表：有向圖中對每個結(jié)點(diǎn)建立以Vi為頭弧單鏈表例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnext14數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第14頁15數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第15頁2）數(shù)據(jù)類型描述＃defineMaxVerNum100/*最大頂點(diǎn)數(shù)為100*/鄰接表類型：typedefstructArcNode{intadjvex;/*鄰接點(diǎn)域*/InfoType*Info;/*表示邊上信息域info*/structArcNode*next;/*指向下一個鄰接點(diǎn)指針域*/}ArcNode;表頭結(jié)點(diǎn)類型：typedefstructVnode{VertexTypevertex;/*頂點(diǎn)域*/ArcNode*firstedge;/*邊表頭指針*/}Vnode,AdjList[MaxVertexNum];圖類型：

typedefstruct{AdjListvertices;/*鄰接表*/intvexnum,arcnum;/*頂點(diǎn)數(shù)和邊數(shù)*/}ALGraph;/*ALGraph是以鄰接表方式存放圖類型*/16數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第16頁7.2.3十字鏈表(OrthogonalList)

十字鏈表是有向圖另一個鏈?zhǔn)酱娣沤Y(jié)構(gòu)，它實際上是鄰接表與逆鄰接表結(jié)合1)存放特點(diǎn)圖中每一條弧有一個結(jié)點(diǎn)，把弧頭相同弧連在同一鏈表上,弧尾相同弧也連在同一鏈表上。結(jié)點(diǎn)結(jié)構(gòu)為：頂點(diǎn)結(jié)點(diǎn)為鏈表頭結(jié)點(diǎn)，其結(jié)構(gòu)為：17數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第17頁7.2.4鄰接多重表(AdjacencyMultilist)鄰接多重表是無向圖另一個鏈?zhǔn)酱娣沤Y(jié)構(gòu)1)存放特點(diǎn)圖中每一條邊用一個邊結(jié)點(diǎn)表示，其結(jié)構(gòu)為：每個頂點(diǎn)用一個結(jié)點(diǎn)表示，其結(jié)構(gòu)為：markivexilinkjvexjlinkdatafirstedge18數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第18頁

在鄰接多重表中,全部依附于同一個頂點(diǎn)邊都鏈接在同一個單鏈表中。

鄰接多重表結(jié)構(gòu)例aecbd1234acdb5e121434323552^^^^^19數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第19頁7.3圖遍歷與連通性從圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中全部頂點(diǎn)，且使每個頂點(diǎn)僅被訪問一次，叫做圖遍歷(GraphTraversal)。為了防止重復(fù)訪問，可設(shè)置一個標(biāo)志頂點(diǎn)是否被訪問過輔助數(shù)組visited[]，它初始狀態(tài)為0，在圖遍歷過程中，一旦某一個頂點(diǎn)i

被訪問，就馬上讓visited[i]為1，預(yù)防它被屢次訪問。20數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第20頁7.3.1深度優(yōu)先搜索DFS1）基本思想：任選圖中一個頂點(diǎn)v,訪問此頂點(diǎn),并作訪問標(biāo)識。從v出發(fā)，訪問它任一未被訪問過鄰接頂點(diǎn)w，作訪問標(biāo)識，并以w為新出發(fā)點(diǎn)，繼續(xù)進(jìn)行深度優(yōu)先搜索。當(dāng)某個頂點(diǎn)全部鄰接頂點(diǎn)都被訪問過后，則退回到前一次剛訪問過頂點(diǎn)k，從k另一個沒有被訪問鄰接頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索。重復(fù)上述過程,直到圖中全部頂點(diǎn)都被訪問過為止21數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第21頁深度優(yōu)先搜索示例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V522數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第22頁深度優(yōu)先搜索示例遍歷結(jié)果：A、B、D、C例23數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第23頁2）算法實現(xiàn)難點(diǎn)：怎樣標(biāo)識已訪問結(jié)點(diǎn)v?怎樣查找v全部鄰接點(diǎn)？處理方法：設(shè)置一個布爾向量數(shù)組visited[n]，初值為0。若序號為i結(jié)點(diǎn)已被訪問過，則visited[i]=1。依據(jù)圖存放方式不一樣，采取對應(yīng)方法查找：鄰接矩陣：vi鄰接點(diǎn)是鄰接矩陣中第i行上非0元素對應(yīng)列值，若A[i][j]<>0，則vj為vi鄰接點(diǎn)。鄰接表：是以G.vertices[i]為表頭結(jié)點(diǎn)單鏈表上全部結(jié)點(diǎn)。24數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第24頁V1V2V4V5V3V7V6V8例1234V1V3V4V2vexdatafirstarc2783^^^adjvexnext5V56^482^V6V7V86787^^^深度遍歷：V1V3V7V6V2V4V8V525數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第25頁3）算法分析圖中有n個頂點(diǎn)，e條邊。因為總共有2e個邊結(jié)點(diǎn)，所以掃描邊時間為O(e)。而且對全部頂點(diǎn)遞歸訪問1次，所以遍歷圖時間復(fù)雜性為O(n+e)。假如用鄰接矩陣表示圖，則查找每一個頂點(diǎn)全部邊，所需時間為O(n)，則遍歷圖中全部頂點(diǎn)所需時間為O(n2)。26數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第26頁7.3.2廣度優(yōu)先搜索BFS1）基本思想：任選圖中一個頂點(diǎn)v，訪問此頂點(diǎn)，并作訪問標(biāo)識。從v出發(fā)，依次訪問v各個未曾被訪問過鄰接頂點(diǎn)w1,w2,…,wt，并作訪問標(biāo)識。然后再次序訪問w1,w2,…,wt全部還未被訪問過鄰接頂點(diǎn)，并作訪問標(biāo)識?！绱俗鱿氯?直到圖中全部頂點(diǎn)都被訪問到為止27數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第27頁廣度優(yōu)先搜索示例例V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V6V7V8V528數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第28頁廣度優(yōu)先搜索示例遍歷結(jié)果：A、B、C、D例29數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第29頁為了實現(xiàn)逐層訪問，算法中使用了一個隊列，以記憶正在訪問這一層和上一層頂點(diǎn)，方便于向下一層訪問。2）算法實現(xiàn)開始標(biāo)志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結(jié)束NNYY30數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第30頁

BFS開始訪問Vi,置標(biāo)志求V鄰接點(diǎn)WW存在嗎V下一鄰接點(diǎn)WW訪問過結(jié)束NYNY初始化隊列Vi入隊隊列空嗎隊頭V出隊訪問W,置標(biāo)志W(wǎng)入隊NaaY31數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第31頁假如使用鄰接表表示圖，則循環(huán)總時間代價為d1+d2+…+dn=O(e)，其中di是頂點(diǎn)i度。假如使用鄰接矩陣，則對于每一個被訪問過頂點(diǎn)，循環(huán)要檢測矩陣中n個元素，總時間代價為O(n2)。3）算法分析32數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第32頁7.4圖連通性與生成樹7.4.1圖連通性問題連通圖與連通分量

在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通。假如圖中任意一對頂點(diǎn)都是連通,則稱此圖是連通圖。非連通圖極大連通子圖叫做連通分量。強(qiáng)連通圖與強(qiáng)連通分量

在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖極大強(qiáng)連通子圖叫做強(qiáng)連通分量。33數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第33頁連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例24513634數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第34頁7.4.2最小生成樹

1）圖生成樹連通圖G一個子圖假如是一棵包含G全部頂點(diǎn)樹（全部頂點(diǎn)均由邊連接在一起，但不存在回路,有n-1條邊），則該子圖稱為G生成樹。生成樹是連通圖極小連通子圖。所謂極小是指：若在樹中任意增加一條邊，則將出現(xiàn)一個回路；若去掉一條邊，將會使之變成非連通圖。使用不一樣遍歷圖方法，能夠得到不一樣生成樹35數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第35頁說明一個圖能夠有許多棵不一樣生成樹全部生成樹含有以下共同特點(diǎn)：生成樹頂點(diǎn)個數(shù)與圖頂點(diǎn)個數(shù)相同生成樹是圖極小連通子圖一個有n個頂點(diǎn)連通圖生成樹有n-1條邊生成樹中任意兩個頂點(diǎn)間路徑是唯一在生成樹中再加一條邊必定形成回路含n個頂點(diǎn)n-1條邊圖不一定是生成樹GHKI36數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第36頁V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V837數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第37頁例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林38數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第38頁

問題提出——要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)——城市權(quán)——城市間建立通信線路所需花費(fèi)代價

生成樹各邊權(quán)值總和稱為生成樹權(quán)。權(quán)最小生成樹稱為最小生成樹。2)結(jié)構(gòu)最小生成樹

問題分析n個城市間,最多可設(shè)置n(n-1)/2條線路n個城市間建立通信網(wǎng),只需n-1條線路問題轉(zhuǎn)化為：怎樣在可能線路中選擇n-1條，能把全部城市（頂點(diǎn)）均連起來，且總花費(fèi)各邊權(quán)值之和）最小165432713179181275241039數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第39頁最小生成樹主要性質(zhì)：

設(shè)G=（V，E）是一個連通網(wǎng)絡(luò)，U是頂點(diǎn)集V一個真子集。若（u，v）是G中全部一個頂點(diǎn)在U,另一個頂點(diǎn)不在U邊中，含有最小權(quán)值一條邊，則一定存在G一棵最小生成樹包含此邊。uvUV—U40數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第40頁①普里姆(Prim)算法普里姆算法基本思想：假設(shè)圖G={V,E}，所求最小生成樹T=(U,TE),其中U=V,TEE從連通網(wǎng)絡(luò)G={V,E}中某一頂點(diǎn)u0

出發(fā)，選擇與它關(guān)聯(lián)含有最小權(quán)值邊(u0,v)，將其頂點(diǎn)加入到生成樹頂點(diǎn)集合U中。以后每一步從一個頂點(diǎn)在U中，而另一個頂點(diǎn)不在U中各條邊中選擇權(quán)值最小邊(u,v),把它頂點(diǎn)加入到集合U中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中全部頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。41數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第41頁

算法實現(xiàn):(略)

算法分析：

上述算法初始化時間是O(1)，k循環(huán)中有兩個循環(huán)語句，其時間大致為：

令O(1)為某一正常數(shù)C，展開上述求和公式可知其數(shù)量級仍是n平方。所以，整個算法時間復(fù)雜性是O(n2)42數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第42頁②克魯斯卡爾(Kruskal)算法克魯斯卡爾算法基本思想：設(shè)有一個有n個頂點(diǎn)連通網(wǎng)絡(luò)G={V,E}，最初先結(jié)構(gòu)一個只有n個頂點(diǎn)，沒有邊非連通圖T={V,},圖中每個頂點(diǎn)自成一個連通分量。在E中選取一條含有最小權(quán)值邊(u,v)，若該邊兩個頂點(diǎn)落在兩個不一樣連通分量上，則將此邊加入到T中；不然將此邊舍去，重新選擇一條權(quán)值最小邊。如此上步，直到T中全部頂點(diǎn)在同一個連通分量上為止。43數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第43頁應(yīng)用克魯斯卡爾算法結(jié)構(gòu)最小生成樹過程例16543265135664251654321234544數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第44頁7.5有向無環(huán)圖及其應(yīng)用計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小工程外，普通都把工程分為若干個叫做“活動”子工程。比如，計算機(jī)專業(yè)學(xué)生學(xué)習(xí)就是一個工程，每一門課程學(xué)習(xí)就是整個工程一些活動。其中有些課程要求先修課程，有些則不要求。7.5.1活動網(wǎng)絡(luò)(ActivityNetwork)

用頂點(diǎn)表示活動網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))45數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第45頁

C1

高等數(shù)學(xué)C2程序設(shè)計基礎(chǔ)C3離散數(shù)學(xué)C1,C2

C4數(shù)據(jù)結(jié)構(gòu)C3,C2C5高級語言程序設(shè)計C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普通物理C1C9計算機(jī)原理C8

課程代號課程名稱先修課程46數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第46頁學(xué)生課程學(xué)習(xí)工程圖47數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第47頁能夠用有向圖表示一個工程。在這種有向圖中，用頂點(diǎn)表示活動，用有向邊<Vi,Vj>表示活動間優(yōu)先關(guān)系，Vi必須先于活動Vj

進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動AOV網(wǎng)絡(luò)(ActivityOnVertices)。在AOV網(wǎng)絡(luò)中，假如活動Vi必須在活動Vj之前進(jìn)行，則存在有向邊<Vi,Vj>，AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)絡(luò)中假如出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。所以，對給定AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。48數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第48頁檢測有向環(huán)一個方法是對AOV網(wǎng)絡(luò)結(jié)構(gòu)它拓?fù)溆行蛐蛄小＜磳⒏鱾€頂點(diǎn)(代表各個活動)排列成一個線性有序序列，使得AOV網(wǎng)絡(luò)中全部應(yīng)存在前驅(qū)和后繼關(guān)系都能得到滿足。拓?fù)渑判颍簭哪硞€集合上一個偏序得到該集合上一個全序，這個操作稱為拓?fù)渑判颉?）拓?fù)渑判?9數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第49頁比如，對學(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到拓?fù)溆行蛐蛄袨镃1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C650數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第50頁2）進(jìn)行拓?fù)渑判蚍椒?/p>

輸入AOV網(wǎng)絡(luò)，令n為頂點(diǎn)個數(shù)在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)頂點(diǎn)（即此頂點(diǎn)入度為0）,并輸出之；從圖中刪去該頂點(diǎn),同時刪去全部它發(fā)出有向邊;重復(fù)以上兩步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；或圖中還有未輸出頂點(diǎn)，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)頂點(diǎn)了。這時AOV網(wǎng)絡(luò)中必定存在有向環(huán)。51數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第51頁C0C1C2C3C4C5例：拓?fù)渑判蜻^程(a)有向無環(huán)圖(b)輸出頂點(diǎn)C4(c)輸出頂點(diǎn)C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d)輸出頂點(diǎn)C352數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第52頁C1C2C5(e)輸出頂點(diǎn)C2C5C1(f)輸出頂點(diǎn)C1C5(g)輸出頂點(diǎn)C5(h)拓?fù)渑判蛲瓿?3數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第53頁AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C2C3C4C5

destnext

C0C1C2C30C4C50012345countdataadj

130103

1

30

5

1

50

0

1

50在鄰接表中增設(shè)了一個count域，統(tǒng)計各個頂點(diǎn)入度。入度為零頂點(diǎn)即無前驅(qū)頂點(diǎn)。54數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第54頁3）拓?fù)渑判蛩惴ㄈ攵葹?頂點(diǎn)即為沒有前驅(qū)頂點(diǎn)。刪除頂點(diǎn)及對應(yīng)弧操作可轉(zhuǎn)換為弧頭頂點(diǎn)入度減1。為防止重復(fù)檢驗入度為0頂點(diǎn)，在算法中使用一個鏈?zhǔn)綏⑷攵葹?頂點(diǎn)鏈接在一起，供選擇和輸出無前驅(qū)頂點(diǎn)。只要出現(xiàn)入度為零頂點(diǎn)，就將它加入棧中。55數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第55頁算法描述使用這種棧拓?fù)渑判蛩惴軌蛎枋鲆韵拢?1)建立入度為零頂點(diǎn)棧;輸出頂點(diǎn)計數(shù)器=0(2)當(dāng)入度為零頂點(diǎn)棧不空時,重復(fù)執(zhí)行從棧中取出頂點(diǎn)元素,并輸出之;計數(shù)器+1從AOV網(wǎng)絡(luò)中刪去這個頂點(diǎn)和它發(fā)出邊,邊終頂點(diǎn)入度減1;假如邊終頂點(diǎn)入度減至0,則該頂點(diǎn)進(jìn)入度為零頂點(diǎn)棧;(3)假如輸出頂點(diǎn)個數(shù)少于AOV網(wǎng)絡(luò)頂點(diǎn)個數(shù),則匯報網(wǎng)絡(luò)中存在有向環(huán)。56數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第56頁分析此拓?fù)渑判蛩惴芍?，假如AOV網(wǎng)絡(luò)有n個頂點(diǎn)，e條邊，在拓?fù)渑判蜻^程中，搜索入度為零頂點(diǎn)，建立鏈?zhǔn)綏Ｋ枰獣r間是O(n)。在正常情況下，有向圖有n個頂點(diǎn)，每個頂點(diǎn)進(jìn)一次棧，出一次棧，共輸出n次。頂點(diǎn)入度減一運(yùn)算共執(zhí)行了e次。所以總時間復(fù)雜度為O(n+e)。4）算法分析57數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第57頁7.5.2用邊表示活動網(wǎng)絡(luò)(AOE網(wǎng)絡(luò))假如在無環(huán)帶權(quán)有向圖中

用有向邊表示一個工程中活動(Activity)用邊上權(quán)值表示活動連續(xù)時間(Duration)用頂點(diǎn)表示事件(Event)則這么有向圖叫做用邊表示活動網(wǎng)絡(luò)，簡稱AOE(ActivityOnEdges)網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)在一些工程估算方面非常有用。比如，能夠使人們了解：

(1)完成整個工程最少需要多少時間(假設(shè)沒有環(huán))?(2)為縮短完成工程所需時間,應(yīng)該加緊哪些活動?58數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第58頁在AOE網(wǎng)絡(luò)中,有些活動次序進(jìn)行，有些活動并行進(jìn)行。從源點(diǎn)到各個頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)有向路徑可能不止一條。這些路徑長度也可能不一樣。完成不一樣路徑活動所需時間即使不一樣，但只有各條路徑上全部活動都完成了，整個工程才算完成。所以，完成整個工程所需時間取決于從源點(diǎn)到匯點(diǎn)最長路徑長度，即在這條路徑上全部活動連續(xù)時間之和。這條路徑長度最長路徑就叫做關(guān)鍵路徑(CriticalPath)。1）關(guān)鍵路徑59數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第59頁1324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10要找出關(guān)鍵路徑，必須找出關(guān)鍵活動，即不按期完成就會影響整個工程完成活動。關(guān)鍵路徑上全部活動都是關(guān)鍵活動。所以，只要找到了關(guān)鍵活動，就能夠找到關(guān)鍵路徑.比如，下列圖就是一個AOE網(wǎng)。60數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第60頁2）怎樣求關(guān)鍵路徑定義幾個與計算關(guān)鍵活動相關(guān)量：事件Vi

最早發(fā)生時間Ve(i)是從源點(diǎn)V0

到頂點(diǎn)Vi最長路徑長度。事件Vi最遲發(fā)生時間Vl[i]是在確保匯點(diǎn)Vn

在Ve[n]時刻完成前提下，事件Vi允許最遲開始時間。活動ak最早開始時間e[k]：設(shè)活動ak在邊<Vi,Vj>上，則e[k]是從源點(diǎn)V0到頂點(diǎn)Vi最長路徑長度。所以,e[k]=Ve[i]?；顒觓k最遲開始時間l[k]是在不會引發(fā)時間延誤前提下,該活動允許最遲開始時間。l[k]=Vl[j]-dur(<i,j>)其中,dur(<i,j>)是完成ak所需時間。61數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第61頁時間余量l[k]-e[k]表示活動ak最早開始時間和最遲開始時間時間余量。l[k]==e[k]表示活動ak是沒有時間余量關(guān)鍵活動。為找出關(guān)鍵活動,需要求各個活動e[k]與l[k]，以判別是否l[k]==e[k].為求得e[k]與l[k]，需要先求得從源點(diǎn)V0到各個頂點(diǎn)Vi

Ve[i]和Vl[i]。62數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第62頁求Ve[i]遞推公式從Ve[1]=0開始，向前遞推

<Vi,Vj>S2,j=2,,n

其中S2是全部指向頂點(diǎn)Vi有向邊<Vj

,Vi

>集合從Vl[n]=Ve[n]開始，反向遞推

<Vi,Vj>S1,j=n-1,n-2,,1其中S1是全部從頂點(diǎn)Vi發(fā)出有向邊<Vi

,Vj

>集合這兩個遞推公式計算必須分別在拓?fù)溆行蚣澳嫱負(fù)溆行蚯疤嵯逻M(jìn)行。63數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第63頁

算法分析

在拓?fù)渑判蚯骎e[i]和逆拓?fù)溆行蚯骎l[i]時,所需時間為O(n+e),求各個活動e[k]和l[k]時所需時間為O(e),總共花費(fèi)時間依然是O(n+e)。64數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第64頁7.6最短路徑(ShortestPath)問題提出:用帶權(quán)有向圖表示一個交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間交通聯(lián)絡(luò)權(quán)——表示沿此線路運(yùn)輸所花時間或費(fèi)用等

問題：從某頂點(diǎn)出發(fā)，沿圖抵達(dá)另一頂點(diǎn)所經(jīng)過路徑中，各邊上權(quán)值之和最小一條路徑——最短路徑最短路徑：假如從圖中某一頂點(diǎn)(稱為源點(diǎn))抵達(dá)另一頂點(diǎn)(稱為終點(diǎn))路徑可能不止一條，怎樣找到一條路徑，使得沿此路徑各邊上權(quán)值總和抵達(dá)最小。問題解法單源最短路徑—Dijkstra算法任意頂點(diǎn)對之間最短路徑—Floyd算法65數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE課件第65頁7.6.1單源最短路徑問題問題提法：

給定一個帶權(quán)有向圖D與源點(diǎn)v，求從v到