數(shù)據(jù)結(jié)構(gòu) 第七章-圖2.ppt

1、2020/11/3,1,第7章 圖,圖是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼。,2,【重點掌握】： 圖的兩種遍歷方法：遍歷的定義、深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法； 應(yīng)用圖的遍歷算法判斷圖的連通性及求圖的生成樹； 用Prim、Kruskal算法求圖的最小生成樹； 用Dijkstra算法求解單源最短路徑問題；用Floyd算法求所有頂點間的最短路徑問題； 利用AOV網(wǎng)進行拓撲排序；利用AOE網(wǎng)求關(guān)鍵路徑問題； 【掌 握】： 掌握圖的定義和術(shù)語； 圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法、在實際問題中的求解效率。,3,7.3 圖的遍歷,7.3 圖的遍歷：從圖的某頂點

2、出發(fā)，訪問圖中所有頂點，并且每個頂點僅訪問一次。,圖結(jié)構(gòu)的遍歷復(fù)雜性： （1）在圖結(jié)構(gòu)中，沒有一個“自然”的首結(jié)點，圖中的任意一個頂點都可以作為第一個被訪問的結(jié)點 （2）在非連通圖中，從一個頂點出發(fā)，只能訪問它所在的連通分量上的所有頂點，因此，還需考慮如何選取下一個出發(fā)點以訪問圖中的其余連通分量 （3）在圖結(jié)構(gòu)中，如果有回路存在，那么一個頂點被訪問后，有可能沿回路又回到該頂點，考慮如何避免重復(fù)訪問 （4）在圖結(jié)構(gòu)中，一個頂點可以和其他多個頂點鄰接，當(dāng)這樣的頂點訪問過后，考慮如何選取下一個要訪問的頂點的問題,4,圖的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。,7.3.1 深度優(yōu)先搜索,方法： （

3、1）從圖的某一頂點V0出發(fā)，訪問此頂點； （2）依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到。 若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問到。,5,若圖的存儲結(jié)構(gòu)為鄰接表，則 訪問鄰接點的順序不唯一， 深度優(yōu)先序列不是唯一的,V0,V1,V3,V4,V7,V2,V5,V6,求圖G以V0為起點的的深度優(yōu)先序列（設(shè)存儲結(jié)構(gòu)為鄰接矩陣）,6,void DFS(Graph G, int v) /* 從第v個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖G*/ /* v是頂點在一維數(shù)組中的位置，假設(shè)G是非空圖*/ v

4、isitedv =1; Visit(v); /*訪問第v個頂點*/ for ( w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w) ) if (!visitedw) DFS(G, w); /*對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS*/ ,輔助數(shù)組：int visitedMax_Vertex_Num ; 訪問標(biāo)志數(shù)組,全局變量，初始時所有分量全為0，visitedv=1表示頂點v已被訪問.,visited,深度優(yōu)先遍歷算法:,7.3 圖的遍歷,7,7.3 圖的遍歷,在鄰接表存儲結(jié)構(gòu)上實現(xiàn)深度優(yōu)先搜索:,void DFSTraverseAL(ALGraph

5、 G) /*深度優(yōu)先遍歷以鄰接表存儲的圖G*/ int i; for (i=0;iG.vexnum; + i) visitedi=0; /*標(biāo)志數(shù)組初始化*/ for(i=0;iG.vexnum;+i) if (!visitedi) DFSAL(G,i); /*Vi未訪問過，從Vi開始DFS搜索*/ ,8,void DFSAL(ALGraph G, int i) /*從第v個頂點出發(fā)，遞歸地深度優(yōu)先遍歷圖G*/ /* v是頂點的序號，假設(shè)G是用鄰接表存儲*/ EdgeNode *p; int w; visitedi =1; Visit(i); /*訪問第v個頂點*/ for (p=G.vert

6、icesi.firstarc;p;p=p-nextarc) w=p-adjvex; /*w是v的鄰接頂點的序號*/ if (!visitedw) DFSAL(G, w); /*若w尚未訪問, 遞歸調(diào)用DFS*/ /*DFSAL*/,7.3 圖的遍歷,9,在遍歷時，對圖中每個頂點至多調(diào)用一次DFS函數(shù)，因為一旦某個頂點被標(biāo)志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結(jié)構(gòu)。 用鄰接矩陣做圖的存儲結(jié)構(gòu)時，查找各個頂點的鄰接點所需的時間為O(n2)，其中n為圖中頂點數(shù)。當(dāng)以鄰接矩陣做存儲結(jié)構(gòu)時，深度優(yōu)先搜索遍歷圖的時間復(fù)

7、雜度為O(n2+n)。 當(dāng)以鄰接表做圖的存儲結(jié)構(gòu)時，找鄰接點所需時間為O(e)，其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。因此，當(dāng)以鄰接表做存儲結(jié)構(gòu)時，深度優(yōu)先搜索遍歷圖的時間復(fù)雜度為O(n+e)。,7.3 圖的遍歷,10,圖中某頂點v出發(fā)： 1）訪問頂點v ； 2）訪問v的所有未被訪問的鄰接點w1 ,w2 , wk ； 3）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；,7.3.2 廣度優(yōu)先遍歷,7.3 圖的遍歷,11,V0,V1,V2, V3,V4,V7,V5,V6,若圖的存儲結(jié)構(gòu)為鄰接表，則 訪問鄰接點的順序不唯一， 深度優(yōu)先序

8、列不是唯一的,求圖G以V0為起點的的廣度優(yōu)先序列（設(shè)存儲結(jié)構(gòu)為鄰接矩陣）, 先被訪問的頂點，其鄰接點也要先被訪問 設(shè)一隊列保存已訪問的頂點,12, 在鄰接表存儲結(jié)構(gòu)上的廣度優(yōu)先搜索,V0,V1,V2,V3,V4,V7,V5,V6,V1,V2,V3,V0,V4,V7,V5,V6,7.3 圖的遍歷,13,void BFSTraverse(MGraph G) /*從v出發(fā)，廣度優(yōu)先遍歷連通圖G*/ /*使用輔助隊列Q和訪問標(biāo)志數(shù)組visited*/ for (v=0; vG.vexnum; +i) visitedv=0; InitQueue(Q, G.vexnum); /*初始化空的輔助隊列Q*/

9、for (v=0;vG.vexnum;+v) if(!visitedv) /*若v尚未訪問*/ visitedv=1; Visit(v); EnQueue(Q,v); while (!QueueEmpty_Sq(Q) DeQueue(Q,u); /*隊頭元素出隊,并賦值給u*/ /*訪問u所有未被訪問的鄰接點*/ for(w=0; wG.vexnum; w+;) if (G.arcsu,w.adj /*while*/ /*BFSTraverse*/,7.3 圖的遍歷,14,第七 章 圖,15,7.4.1 生成樹,生成樹：包含了無向圖G所有頂點的極小連通子圖。 1）“極小”含義：一個有n個頂點的

10、連通圖的生成樹有n-1條邊，刪除任何一條邊，子圖不再連通；在生成樹中再加一條邊必然形成回路。（生成樹包含了圖中的所有頂點，但只有足以構(gòu)成生成樹的n-1條邊） 2）一個圖可以有許多棵不同的生成樹； 3）生成樹中任意兩個頂點間的路徑是唯一的； 4）含n個頂點n-1條邊的圖不一定是生成樹。,7.4 最小的生成樹,16,7.4 最小的生成樹,生成樹的含義：n個頂點的圖最多可存在n(n-1)/2條邊線路。求生成樹是為了在網(wǎng)絡(luò)中連通n個頂點而選擇最少的邊(n1)。 例如：一個通信網(wǎng)絡(luò)中，節(jié)點代表了路由器，為了使各路由器之間是連通的（數(shù)據(jù)可達），且不形成回路(數(shù)據(jù)回到發(fā)送方)，則需建立該網(wǎng)絡(luò)的生成樹。,17

11、,求生成樹的方法：利用遍歷算法。 從連通圖中的任一頂點出發(fā)進行遍歷時，除出發(fā)點外，其余頂點必須通過一條邊才能到達，所以遍歷過程中經(jīng)歷的邊有n-1條，它和n個頂點組成了連通圖的一棵生成樹。 由深度優(yōu)先搜索得到的是深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的是廣度優(yōu)先生成樹。,18,深度遍歷：V0V1V3V4V7V2 V5V6,7.4 最小的生成樹,19,廣度遍歷： V0 V1 V2 V3 V4 V7 V5 V6,7.4 最小的生成樹,20,7.4.2 最小生成樹的概念,由生成樹的定義可知，無向連通圖的生成樹不是惟一的。 問題的提出：設(shè)要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點表示城市，權(quán)表示城市間建立通信線路所

12、需花費代價。希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費的總代價）最小最小代價生成樹。,7.4 最小的生成樹,21, 最小生成樹定義：對于一個網(wǎng)絡(luò)，它的所有生成樹中邊權(quán)值最小的生成樹稱為最小生成樹。 問題分析：n個城市間建立通信網(wǎng)，如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費（各邊權(quán)值之和）最小。即：如何在保證n點連通的前題下最節(jié)省經(jīng)費?,22,1. Prim 法基本步驟 設(shè)連通網(wǎng)絡(luò)G=V,E。集合U存放G的最小生成樹中的頂點，集合T存放最小生成樹之外的頂點。 (1)從G中選擇某一頂點u0出發(fā)，在與它關(guān)聯(lián)的邊中選擇一個邊權(quán)最小的邊(u0,v);將

13、頂點v加入最小生成樹的頂點集合U，在集合T 中刪除該頂點； (2)用頂點v到集合T中頂點的邊權(quán)“更新”原集合U中頂點到集合T中頂點的最小邊權(quán)； (3)從一個頂點在U中，而另一個頂點在T中的各條邊中選擇權(quán)值最小的邊(u,v),把頂點v加入到集合U 中。 (4)重復(fù)(2) 、(3)，直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U中為止。,7.4.3 構(gòu)造最小生成樹的Prim算法,7.4 最小的生成樹,23,U= V1 ,7.4 最小的生成樹,2. 過程演示,24,7.4 最小的生成樹,Prim 算法的時間復(fù)雜度為O(n2),25,7.4.3 構(gòu)造最小生成樹的Kruskal算法,1.基本思想：按網(wǎng)中權(quán)

14、值遞增的順序構(gòu)造最小生成樹。 2.基本步驟 1）設(shè)連通網(wǎng)G=(V,E)，令最小生成樹初始狀態(tài)是只有n個頂點而無邊的非連通圖T=(V,)，每個頂點自成一個連通分量； 2）在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊； 3）依此類推，直至T中所有頂點都在同一連通分量上為止。,7.4 最小的生成樹,26,7.4 最小的生成樹,3. 過程演示,27,7.4 最小的生成樹,Kruskal 算法的時間復(fù)雜度為O(ne)。,28,29,交通咨詢系統(tǒng)、通訊網(wǎng)、計算機網(wǎng)絡(luò)中經(jīng)常要尋找兩結(jié)點間最短路徑。例如：交通咨詢系統(tǒng)中：咨詢A到B

15、的最短路徑；計算機網(wǎng)中如何發(fā)送E-mail才最節(jié)省費用（使E-mail由A到B沿最短路徑傳送）。 設(shè)用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中： 頂點表示城市 邊表示城市間的交通聯(lián)系 權(quán)表示此線路的長度或沿此線路運輸所花的時間或費用等 這類問題歸結(jié)為從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑最短路徑。路徑上的第一個頂點為源點，最后一個頂點為終點。,問題的提出:,7.5 最短路徑,30, 最短路徑問題：如果從圖中某一頂點(源點)到達另一頂點(終點)的路徑可能不止一條，如何找到一條路徑使沿此路徑上各邊上的權(quán)值總和達到最小。,31,從一個源點到其他各點的最短路徑,1.

16、 問題的提法：給定一個帶權(quán)有向圖D與源點v，求從v到D中其它頂點的最短路徑。,7.5 最短路徑,2. 迪杰斯特拉算法（Dijkstra） （1）基本思想 為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依此類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。,32,依據(jù)算法的基本思想把V分成兩組： （1）S：已求出最短路徑的頂點的集合 （2）V-S=T：尚未確定最短路徑的頂點集合 將T中頂點按如下規(guī)則加入到S中： （1）按遞增的次序產(chǎn)生最短路徑：從源點V0到S中各頂點的最短路徑長度都不大

17、于從V0到T中任何頂點的最短路徑長度; （2）待求的最短路徑最多以已求出最短路徑的頂點為中間點：從V0到某頂點的最短路徑中，只將S中的頂點作為中間點,33,（2）Dijkstra 算法的基本步驟 設(shè)V0是源點，初使時令S=V0,T=其余頂點，T中頂點對應(yīng)的距離值若存在，邊權(quán)值為弧上的權(quán)值；若不存在，邊權(quán)值為。 1）從T中選取一個其距離值最小的頂點W，加入S； 2） 對T中頂點的距離值進行修改：先求出V0到Vi中間只經(jīng)S中結(jié)點的最短路徑；若加進W作中間頂點后從V0到Vi的距離值 比 不加W的路徑要短，則修改此距離值； 上述最短路徑中長度最小者即為下一條長度最短的路徑； 將所求最短路徑的終點加入S

18、中； 3）重復(fù)2）直到S中包含所有頂點，即S=V為止。,7.5 最短路徑,34,1）圖用帶權(quán)鄰接矩陣存儲； 2）引入一個輔助數(shù)組dist。它的每一個分量disti表示當(dāng)前找到的從源點v0 到終點vi 的最短路徑的長度 初始狀態(tài)： 若從源點v0 到頂點vi有邊，則disti為該邊上的權(quán)值； 若從源點v0 到頂點vi 沒有邊，則disti為 。 3）數(shù)組path表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0 到某終點無路徑，則用-1 作為該結(jié)點前一頂點的序號 4)數(shù)組s標(biāo)識V0 到該結(jié)點的最短路徑是否求出。0表示沒求出，1表示已求出。,7.5 最短路徑,(3) 算法實現(xiàn),35,7

19、.5 最短路徑,2,60,0,0,30,1,3,50,1,0,10,1,2,2,60,1,0,30,1,3,50,1,0,10,1,4,3,90,0,0,30,1,3,50,0,0,10,1,3,0,100,0,0,30,0,1,60,0,0,10,1,1,0,100,0,0,30,0,-1,0,0,10,0,0,P4,d4,S4,P3,d3,S3,P2,d2,S2,P1,d1,S1,頂點4,頂點3,頂點2,頂點1,選取點,0 1 2 3 4,36,如何從表中讀取源點0到終點的最短路徑？ 以頂點4為例： (1) V0到頂點4的最短路徑為60。 (2) path4=2 path2=3 path3

20、=0； 反過來排列，得到路徑0, 3, 2, 4，即V0到頂點V4的最短路徑。,7.5 最短路徑,37, Dijkstra 算法的時間復(fù)雜度為O(n2),38,39,7.6.1 有向無環(huán)圖的概念,1. 有向無環(huán)圖（directed acycline graph）：沒有回路的有向圖。 含有公共子式的表達式 例如：表達式(a+b)*(a+b-e/f), 流程圖： 工程流程、生產(chǎn)過程中工序流程、程序流程、課程的流程。常用的兩種有向無環(huán)圖是：AOV網(wǎng)，AOE網(wǎng)。,7.6 有向無環(huán)圖及其應(yīng)用,40,7.6.2 AOV網(wǎng)與拓撲排序,1. AOV網(wǎng) (Activity On Vertex network)

21、用頂點表示活動，邊表示活動的順序關(guān)系的有向圖稱為AOV網(wǎng)。 在AOV網(wǎng)中，若從頂點i到頂點j有一條有向路徑。則頂點i是頂點j的前驅(qū)，j是i的后繼。若是網(wǎng)中一條弧，則i是j的直接前驅(qū)，j是i的直接后繼。 在AOV網(wǎng)中，每一條弧表示了活動之間存在的制約關(guān)系。 注：AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件。 例如：計算機專業(yè)的學(xué)生必須學(xué)習(xí)一系列的基本課和專業(yè)課。學(xué)生應(yīng)按照怎樣的順序來學(xué)習(xí)呢？ 可以把這個問題看做一個大的工程，其活動就是學(xué)習(xí)每一門課程。,7.6 有向無環(huán)圖及其應(yīng)用,41,C1、C2是獨立于其它課程的基礎(chǔ)課，而另一些課程必須在學(xué)完作為它的基礎(chǔ)課后才能開始，即有先行課。先行

22、條件規(guī)定了課程之間的優(yōu)先關(guān)系。,計算機專業(yè)的課程設(shè)置及其關(guān)系,7.6 有向無環(huán)圖及其應(yīng)用,42,頂點表示課程，弧表示前提條件活動。若課程i是課程j的先行課，則必然存在弧。由此得到如下AOV網(wǎng)：,在安排學(xué)習(xí)順序時，必須保證在學(xué)習(xí)某門課前，已經(jīng)學(xué)習(xí)了其先行課。,如何設(shè)置這些課程的學(xué)習(xí)順序，才能無矛盾、順利地完成學(xué)業(yè)？,7.6 有向無環(huán)圖及其應(yīng)用,43,2. 拓撲排序 拓撲序列：有向圖D的一個頂點序列稱作一個拓撲序列，對于該序列中任兩頂點v、u，若在D中v是u前趨，則在序列中v也是u前趨。 拓撲排序：把AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的領(lǐng)先關(guān)系排列成一個線性序列的過程。,拓撲排序的應(yīng)用：判斷工程流

23、程的是否合理.,利用拓撲排序檢測AOV網(wǎng)中是否存在環(huán)：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)。,7.6 有向無環(huán)圖及其應(yīng)用,44,3.拓撲排序算法 （1）在AOV網(wǎng)中選一個沒有前驅(qū)的頂點v并將其輸出； （2）從網(wǎng)中刪除頂點v和所有以v為尾的?。?（3）重復(fù)(1)、(2)，直至全部頂點均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點為止。,7.6 有向無環(huán)圖及其應(yīng)用,45,拓撲序列：C1,7.6 有向無環(huán)圖及其應(yīng)用,46,拓撲序列：C1，C2,拓撲序列：C1,7.6 有向無環(huán)圖及其應(yīng)用,47,拓撲序列：C1，C2,拓撲序列：C1，C2，C3,7.6

24、 有向無環(huán)圖及其應(yīng)用,48,拓撲序列：C1，C2，C3,拓撲序列：C1，C2，C3，C9,7.6 有向無環(huán)圖及其應(yīng)用,49,拓撲序列：C1，C2，C3，C9,拓撲序列：C1，C2，C3，C9，C4,拓撲序列：C1，C2，C3，C9，C4，C5,拓撲序列：C1，C2，C3，C9，C4，C5，C7,拓撲序列：C1，C2，C3，C9，C4，C5，C7，C10，C6，C8，C11,一個AOV網(wǎng)的拓撲序列不是唯一的。,7.6 有向無環(huán)圖及其應(yīng)用,50,拓撲排序算法: （1）在AOV網(wǎng)中選一個沒有前驅(qū)的頂點v并將其輸出； （2）從網(wǎng)中刪除頂點v和所有以v為尾的??； （3）重復(fù)(1)、(2)，直至全部頂點均

25、已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點為止。,7.6 有向無環(huán)圖及其應(yīng)用, 拓撲排序方法的另一種等價描述： （1） 選擇一入度為0頂點v，輸出； （2） 將v鄰接到的頂點的入度減1； （3） 重復(fù)(1)、(2)，直至全部頂點均已輸出;或圖中沒有入度為0的頂點為止。,51,拓撲排序的數(shù)據(jù)結(jié)構(gòu)： 以鄰接表存儲有向圖，并在頂點結(jié)點中增加該頂點的入度信息。 算法： 1）為方便查找入度為0的元素，將鄰接表中所有入度為0的頂點進棧 2）棧非空時，輸出棧頂元素Vj并退棧； 3）在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧； 重復(fù)上述操作直至?？諡橹?。若?？諘r輸出的頂點個數(shù)不是n，

26、則有向圖有環(huán)；否則，拓撲排序完畢。,52,7.6 有向無環(huán)圖及其應(yīng)用,53,輸出序列：5,7.6 有向無環(huán)圖及其應(yīng)用,54,輸出序列：5,7.6 有向無環(huán)圖及其應(yīng)用,55,輸出序列：5,7.6 有向無環(huán)圖及其應(yīng)用,56,輸出序列：5,7.6 有向無環(huán)圖及其應(yīng)用,57,輸出序列：5,7.6 有向無環(huán)圖及其應(yīng)用,58,輸出序列：5,7.6 有向無環(huán)圖及其應(yīng)用,59,輸出序列：5 0,7.6 有向無環(huán)圖及其應(yīng)用,60,輸出序列： 5 0,7.6 有向無環(huán)圖及其應(yīng)用,61,輸出序列： 5 0,7.6 有向無環(huán)圖及其應(yīng)用,62,輸出序列： 5 0,7.6 有向無環(huán)圖及其應(yīng)用,63,輸出序列： 5 0,7

27、.6 有向無環(huán)圖及其應(yīng)用,64,輸出序列： 5 0,7.6 有向無環(huán)圖及其應(yīng)用,65,輸出序列： 5 0,7.6 有向無環(huán)圖及其應(yīng)用,66,輸出序列： 5 0,7.6 有向無環(huán)圖及其應(yīng)用,67,輸出序列： 5 0 2,7.6 有向無環(huán)圖及其應(yīng)用,68,輸出序列： 5 0 2,7.6 有向無環(huán)圖及其應(yīng)用,69,輸出序列： 5 0 2,7.6 有向無環(huán)圖及其應(yīng)用,70,輸出序列： 5 0 2,7.6 有向無環(huán)圖及其應(yīng)用,71,輸出序列： 5 0 2,7.6 有向無環(huán)圖及其應(yīng)用,72,輸出序列： 5 0 2,7.6 有向無環(huán)圖及其應(yīng)用,73,輸出序列： 5 0 2 1,7.6 有向無環(huán)圖及其應(yīng)用,7

28、4,輸出序列：5 0 2 1,7.6 有向無環(huán)圖及其應(yīng)用,75,輸出序列：5 0 2 1 3,7.6 有向無環(huán)圖及其應(yīng)用,76,輸出序列：5 0 2 1 3,7.6 有向無環(huán)圖及其應(yīng)用,77,輸出序列：5 0 2 1 3,7.6 有向無環(huán)圖及其應(yīng)用,78,輸出序列：5 0 2 1 3,7.6 有向無環(huán)圖及其應(yīng)用,79,輸出序列：5 0 2 1 3 4,7.6 有向無環(huán)圖及其應(yīng)用,80,輸出序列：5 0 2 1 3 4,7.6 有向無環(huán)圖及其應(yīng)用,81,拓撲排序算法分析: 建鄰接表：T(n)=O(n+e) 搜索入度為0的頂點的時間：T(n)=O(n) 拓撲排序：T(n)=O(n+e),7.6 有

29、向無環(huán)圖及其應(yīng)用,82,7.7 AOE網(wǎng)和關(guān)鍵路徑 AOE網(wǎng)(Activity On Edges) 如果在無有向環(huán)的帶權(quán)有向圖中, 用有向邊表示一個工程中的各項活動(Activity), 用邊上的權(quán)值表示活動的持續(xù)時間(Duration), 用頂點表示事件(Event)，每個事件表示在它之前的活動已完成，在它之后的活動可以開始. 這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò)，簡稱AOE網(wǎng)。 AOE網(wǎng)在某些工程估算方面非常有用。 用途1：計算完成整個工程至少需要多少時間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))? 用途2：為縮短完成工程所需的時間, 應(yīng)當(dāng)加快哪些活動?,7.6 有向無環(huán)圖及其應(yīng)用,83,頂點表示事件,邊表示活動

30、,事件Vj發(fā)生 表示ak已結(jié)束,事件Vi發(fā)生 表示活動ak可以開始,事件 V1表示整個工程開始 事件 V6表示整個工程結(jié)束,7.6 有向無環(huán)圖及其應(yīng)用,84,說明：AOV網(wǎng)和AOE網(wǎng)，用都能表示工程各子工程的流程，一個用頂點表示活動，一個用邊表示活動，但AOV網(wǎng)側(cè)重表示活動的前后次序，AOE網(wǎng)除表示活動先后次序，還表示了活動的持續(xù)時間等，因此可利用AOE網(wǎng)解決工程所需最短時間及哪些子工程拖延會影響整個工程按時完成等問題。實際應(yīng)用中采用那一種圖，取決于要求解的問題。,AOE網(wǎng)具有兩個性質(zhì): (1) 只有在某頂點所代表的事件發(fā)生之后，從該頂點出發(fā)的弧所代表的活動才能開始; (2) 只有在進入一個頂

31、點的各弧所代表的活動都已經(jīng)結(jié)束，該頂點所代表的事件才能發(fā)生。,7.6 有向無環(huán)圖及其應(yīng)用,85,2. 關(guān)鍵路徑(Critical Path) 在AOE網(wǎng)中, 有些活動順序進行，有些活動并行進行。 整個工程結(jié)束的條件：從源點到終點的有向路徑可能不止一條，其長度也不盡相同，但只有各條路徑上所有活動都完成了，整個工程才算完成。 關(guān)鍵路徑：完成整個工程所需的時間取決于從源點到終點的最長路徑長度（該路徑上所有活動的持續(xù)時間之和）。這條路徑長度最長的路徑就叫做關(guān)鍵路徑。,7.6 有向無環(huán)圖及其應(yīng)用,86, 關(guān)鍵路徑長度是整個工程所需的最短工期,即要縮短整個工期，必須加快關(guān)鍵活動的進度。,87,3. 關(guān)鍵路

32、徑的確定,設(shè)活動ai用弧表示，其持續(xù)時間記為：dut()。,(1)事件Vk 的最早可能開始時間Vek 是從源點V0 到頂點Vk的最長路徑長度。決定了所有從頂點發(fā)出的弧所代表的活動能夠開工的最早時間. 根據(jù)AOE網(wǎng)的性質(zhì)，只有進入VK的所有活動（1jn-1)都結(jié)束時, Vk代表的事件才能發(fā)生。計算Vk的的最早可能開始時間方法如下:,從Ve1=0開始遞推，Vek = Maxvej + dut(),7.6 有向無環(huán)圖及其應(yīng)用,88,(2)事件Vk的最遲允許開始時間Vlk 是在保證終點Vn-1 在Ven-1 時刻完成的前提下(即不拖延工期)，事件Vk的允許的最遲開始時間。,從Vln=Ven開始遞推，V

33、lk = Minvlj dut(),設(shè)弧代表從Vk出發(fā)的活動，為了不拖延工期，Vk發(fā)生的最遲時間必須保證不推遲從事件Vk出發(fā)的所有活動的終點Vj (2jn)的最遲時間,7.6 有向無環(huán)圖及其應(yīng)用,89,(3)活動ai的最早可能開始時間 ei 設(shè)活動 ai 由弧表示，根據(jù)AOE網(wǎng)的性質(zhì)，只有事件Vk發(fā)生了，活動ai才能開始。也就是說，活動ai的最早開始時間等于是vk的最早發(fā)生時間。因此, ek = Vei。,(4) 活動 ai的最遲開始時間li li是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。 設(shè)活動ai 由弧表示，根據(jù)AOE網(wǎng)的性質(zhì)，ai的最遲開始時間要保證時間vj的最遲發(fā)生時間不拖后。 li=Vlj - dut(),(5) 關(guān)鍵活動 活動ai的時間余量 為li - ei（最遲可能開始時間和最早允許開始時間的差）。 定義li = ei的活動是沒有時間余量的關(guān)鍵活動。,7.6 有向無環(huán)圖及其應(yīng)用,90,求關(guān)鍵路徑步驟 求Ve(i) 求Vl(j) 求e(i) 求l(i) 計算l(i)-e(i),V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7