數(shù)據(jù)結(jié)構(gòu)與算法12

1、數(shù)據(jù)結(jié)構(gòu)與算法1Chapter 10圖-22拓?fù)渑判驅(qū)τ谕負(fù)浞诸惖难芯?，主要涉及的?shù)據(jù)結(jié)構(gòu)是無環(huán)路有向圖。不存在有向環(huán)路的有向圖簡稱為無環(huán)路有向圖。1234無環(huán)路有向圖1234有環(huán)路有向圖3拓?fù)渑判蛴?jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。4 C1 高等數(shù)學(xué) C2 程序設(shè)計(jì)基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)

2、據(jù)結(jié)構(gòu) C3, C2 C5 高級(jí)語言程序設(shè)計(jì) C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計(jì)算機(jī)原理 C8 C1C8C9C7C3C4C2C5C6學(xué)生課程學(xué)習(xí)工程圖5拓?fù)渑判蚝虯OV網(wǎng)絡(luò)可以用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)的關(guān)系。Vi 必須先于活動(dòng)Vj 進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)(Activity On Vertices)。 在AOV網(wǎng)絡(luò)中，如果活動(dòng)Vi必須在活動(dòng)Vj之前進(jìn)行，則存在有向邊，AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)絡(luò)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先

3、決條件。因此，對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。6拓?fù)渑判蚝虯OV網(wǎng)絡(luò)檢測有向環(huán)的一種方法是對(duì)AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn) (代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前導(dǎo)和后繼關(guān)系都能得到滿足。 這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)浞诸?，也叫拓?fù)渑判颉Ｈ绻ㄟ^拓?fù)浞诸惸軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?，則該AOV網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓?fù)溆行蛐蛄?，則說明AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。7給定一個(gè)無環(huán)路有向圖G=(V,E) , 各結(jié)點(diǎn)的編號(hào)為v=

4、(1,2, ,n)。要求對(duì)每一個(gè)結(jié)點(diǎn) i 重新進(jìn)行編號(hào)，使得若 i 是 j 的前導(dǎo)，則有l(wèi)abelilabelj。即拓?fù)浞诸愂菍o環(huán)路有向圖排成一個(gè)線性序列，使當(dāng)從結(jié)點(diǎn) i 到結(jié)點(diǎn) j 存在一條邊，則在線性序列中，將 i 排在 j 的前面。 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C1C8C9C7C3C4C2C5C68輸入AOV網(wǎng)絡(luò)。令 n 為頂點(diǎn)個(gè)數(shù)。 在AOV網(wǎng)絡(luò)中選一個(gè)入度為0的頂點(diǎn), 并輸出之; 從圖中刪去該頂點(diǎn), 同時(shí)刪去所有它發(fā)出的有向邊; 重復(fù)以上

5、1、2 步, 直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)浞诸愅瓿?；或圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點(diǎn)，它們都有直接前導(dǎo)，再也找不到入度為0的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。拓?fù)渑判蛩惴?拓?fù)浞诸惖倪^程-1(a)無環(huán)有向圖(b)輸出頂點(diǎn)4(c)輸出頂點(diǎn)0(d)輸出頂點(diǎn)340310拓?fù)浞诸惖倪^程-2(e)輸出頂點(diǎn)2(f)輸出頂點(diǎn)1(g)輸出頂點(diǎn)0(h)拓?fù)浞诸愅瓿?03215 最后得到的拓?fù)溆行蛐蛄袨?4 , 0 , 3 , 2 , 1 , 5 。它滿足圖中給出的所有前導(dǎo)和后繼關(guān)系，對(duì)于本來沒有這種關(guān)系的頂點(diǎn)，如C0、C4和C2，也排出了先后次序關(guān)系。11

6、AOE網(wǎng)絡(luò)（Activity On Edge）以頂點(diǎn)代表事件，有向邊代表活動(dòng)，有向邊的權(quán)表示一向活動(dòng)所需的時(shí)間。頂點(diǎn)所代表的事件是指它的入邊代表的活動(dòng)都以完成，由它的出邊代表的活動(dòng)可以開始這樣的一種狀態(tài)。AOE網(wǎng)絡(luò)常常用來估算一項(xiàng)工程的完成時(shí)間。AOE網(wǎng)絡(luò)只有一個(gè)開始頂點(diǎn)（入度為0）和一個(gè)結(jié)束頂點(diǎn)（出度為0）。關(guān)鍵路徑和AOE網(wǎng)絡(luò)v6源點(diǎn)起始點(diǎn)v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v712只有在某個(gè)頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊代表的活動(dòng)才能開始;只有在進(jìn)入某一頂點(diǎn)的各有向邊代表的

7、活動(dòng)已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生；表示實(shí)際工程計(jì)劃的AOE網(wǎng)應(yīng)該是無環(huán)的，并且存在唯一的入度為0的開始頂點(diǎn)（源點(diǎn)）和唯一的出度為0的結(jié)束點(diǎn)（匯點(diǎn)）。AOE網(wǎng)的性質(zhì)v6源點(diǎn)起始點(diǎn)v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v713AOE網(wǎng)研究的主要問題 如果用AOE 網(wǎng)表示一項(xiàng)工程，那么僅僅考慮各個(gè)子工程之間的優(yōu)先關(guān)系還不夠，更多地是關(guān)心整個(gè)工程完成的最短時(shí)間是多少，哪些活動(dòng)的延遲將影響整個(gè)工程進(jìn)度,而加速這些活動(dòng)能否提高整個(gè)工程的效率,因此AOE網(wǎng)有待研究的問題是:(1) 完成整個(gè)工程至少需要多

8、少時(shí)間？(2) 哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？v6源點(diǎn)起始點(diǎn)v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v714路徑長度、關(guān)鍵路徑、關(guān)鍵活動(dòng)路徑長度：是指從源點(diǎn)到匯點(diǎn)路徑上所有活動(dòng)的持續(xù)時(shí)間之和。關(guān)鍵路徑：在AOE網(wǎng)中，由于有些活動(dòng)可以并行，所以完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最大路徑長度。因此，把從源點(diǎn)到匯點(diǎn)具有最大長度的路徑稱為關(guān)鍵路徑。一個(gè)AOE中，關(guān)鍵路徑可能不只一條。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。v6源點(diǎn)起始點(diǎn)v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1

9、a3=1a6=9a7=8a8=4a10=4a9=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v715 事件Vj 的最早可能發(fā)生時(shí)間VE(j) 是從源點(diǎn)V1 到頂點(diǎn)Vj 的最長路徑長度?；顒?dòng)ai 的最早可能開始時(shí)間 E(k) 設(shè)活動(dòng)ai 在邊上, 則E(i)也是從源點(diǎn)V1到頂點(diǎn)Vj 的最長路徑長度。這是因?yàn)槭录j發(fā)生表明以Vj為起點(diǎn)的所有活動(dòng)ai可以立即開始。因此, E(i) = VE(j) .( 1 ) 關(guān)鍵路徑和關(guān)鍵活動(dòng)性質(zhì)分析：（與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量）v6源點(diǎn)起始點(diǎn)v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v716事

10、件Vk的最遲發(fā)生時(shí)間VL(k) 是在保證匯點(diǎn)Vn在VE(n)時(shí)刻完成的前提下，事件Vk的允許的最遲開始時(shí)間。 在不推遲工期的情況下，一個(gè)事件 最遲發(fā)生時(shí)間VL(k)應(yīng)該等于匯點(diǎn)的最早發(fā)生時(shí)間VE(n )減去從Vk到Vn的最大路徑長度。v6源點(diǎn)起始點(diǎn)v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2匯點(diǎn)結(jié)束點(diǎn)AOE網(wǎng)v717 活動(dòng)ai 的最遲允許開始時(shí)間 L(i) 是指在不會(huì)引起工期延誤的前提下，活動(dòng)ai允許的最遲開始時(shí)間。 因?yàn)槭录k發(fā)生表明以Vk為終點(diǎn)的入邊所表示的所有活動(dòng)均已完成，所以事件Vk的最遲發(fā)生時(shí)間VL(k)也是

11、所有以Vk為終點(diǎn)的入邊所表示的活動(dòng)ai可以最遲完成時(shí)間。 顯然，為不推遲工期，活動(dòng)ai的最遲開始時(shí)間L(i)應(yīng)該是ai的最遲完成時(shí)間VL(k)減去ai的持續(xù)時(shí)間，即 L(i) = VL(k) - ACTjk .( 2 ) 其中, ACTjk是活動(dòng)ai 的持續(xù)時(shí)間（ 上的權(quán)）。VjVkai18時(shí)間余量 L(i) - E(i) L(i) - E(i)表示活動(dòng) ak 的最早可能開始時(shí)間和最遲允許開始時(shí)間的時(shí)間余量。 關(guān)鍵路徑上的活動(dòng)都滿足：L(i) = E(i) .( 3 ) L(i) = E(i)表示活動(dòng)是沒有時(shí)間余量的關(guān)鍵活動(dòng)。 由上述分析知，為找出關(guān)鍵活動(dòng)，需要求各個(gè)活動(dòng)的E(i)與 L(i)

12、，以判別一個(gè)活動(dòng)ai是否 滿足L(i) = E(i)。 E(i)和L(i)可有公式 (1)和(2)。而VE(k) 和VL(k)可由拓?fù)浞诸愃惴ǖ玫健?利用拓?fù)浞诸愃惴ㄇ箨P(guān)鍵路徑和關(guān)鍵活動(dòng)。19Step1(前進(jìn)階段)：從源點(diǎn)V1出發(fā)，令VE(1) = 0，按拓?fù)湫蛄写涡蚯蟪銎溆喔黜旤c(diǎn)事件的最早發(fā)生時(shí)間: 利用拓?fù)浞诸愃惴ㄇ箨P(guān)鍵路徑和關(guān)鍵活動(dòng) 其中T是以頂點(diǎn)Vk為尾的所有邊的頭頂點(diǎn)的集合(2kn)如果網(wǎng)中有回路，不能求出關(guān)鍵路徑則算法中止；否則轉(zhuǎn)Step2。其中S是以頂點(diǎn)Vj為頭的所有邊的尾頂點(diǎn)的集合(2jn-1)jTVE(k) = max VE(j)+ACTjk Step2(回退階段)：從匯點(diǎn)V

13、n出發(fā)，令VL(n) = VE(n)，按逆拓 撲有序求其余各頂點(diǎn)的最晚發(fā)生時(shí)間：kSVL(j) = min VL(k)+ACTjk 20Step3： 求每一項(xiàng)活動(dòng)ai的最早開始時(shí)間: E( i ) = VE( j ) 最晚開始時(shí)間: L( i ) = VL( k ) - ACTjk 若某條邊滿足E( i ) = L( i )，則它是關(guān)鍵活動(dòng)。為了簡化算法, 可以在求關(guān)鍵路徑之前已經(jīng)對(duì)各頂點(diǎn)實(shí)現(xiàn)拓?fù)渑判? 并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號(hào)。不是任意一個(gè)關(guān)鍵活動(dòng)的加速一定能使整個(gè)工程提前。想使整個(gè)工程提前，要考慮各個(gè)關(guān)鍵路徑上所有關(guān)鍵活動(dòng)。21例1:活動(dòng)e(i)l(i)l(i)-e(i)a

14、0a1a2a3a4a5a6a7a8a9a1000002204466046259478177071141617215150注：Ve(i)：事件最早可能發(fā)生時(shí)間 源點(diǎn)到達(dá)該事件的最長路經(jīng)Vl(i)：事件最遲發(fā)生時(shí)間 VE(n) - maxLik e(i)：活動(dòng)最早可能開始時(shí)間 Ve( 活動(dòng)起點(diǎn) ) l(i)：活動(dòng)最遲允許開始時(shí)間 Vl( 活動(dòng)終點(diǎn) ) - ai 事件vevlv0v1v2v3v4v5v6v7v80066465977711161715151919v6源點(diǎn)起始點(diǎn)v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2匯點(diǎn)結(jié)束點(diǎn)

15、AOE網(wǎng)v722123654a1=3a2=2a4=3a3=2a5=4a6=1a7=2a8=3例2:頂點(diǎn)Ve(i)Vl(i)活動(dòng)e(i)l(i)l(i)-e(i)123456a1a2a3a4a5a6a7a8032668042678003326621044276510110103注：事件最早可能發(fā)生時(shí)間Ve(i) 源點(diǎn)到達(dá)該事件的最長路經(jīng)事件最遲發(fā)生時(shí)間Vl(i) VE(n)-maxLik活動(dòng)最早可能開始時(shí)間 e(i) Ve(活動(dòng)起點(diǎn))活動(dòng)最遲允許開始時(shí)間 l(i) Vl(活動(dòng)終點(diǎn))-ai 23單源最短路徑D1 D2 D3 D4 D5 10 30 100D 10 30 100 50 20 10 2

16、0 60 C集合 S = 1 1, 2, 3, 4, 5 20124351010030105060V0Dijkstra算法基本思想：集合S的 初值為S=1D為各頂點(diǎn)當(dāng)前最小路徑從V-S中選擇頂點(diǎn)w，使Dw的值最小 并將 w加入集合 S，則w的最短路徑已 求出。調(diào)整其他各結(jié)點(diǎn)的當(dāng)前最小路徑 Dk=minDk, Dw+Cwk直到S中包含所有頂點(diǎn)2412435101003010502060V0循環(huán) S w D2 D3 D4 D5初態(tài) 1 - 10 30 100 1 1,2 2 10 60 30 100 2 1,2,4 4 10 50 30 90 3 1,2,4,3 3 10 50 30 60 4 1

17、,2,4,3,55 10 50 30 60算法的逐步求精過程：算法：Void Dijkstra( G ) S = 1 ; for( i=2; i=n; i+ ) Di = C1i; for( i=1; in; i+ ) 從V-S中選出一個(gè)頂點(diǎn)w,使Dw最?。?S = S + w ; for ( V-S中的每一個(gè)頂點(diǎn)v ) Dv=min( Dv, Dw+Cwv ); 25循環(huán) S w D1 D2 D3 D4 D5初態(tài) 0 - 10 30 100 1 0,2 2 10 60 30 100 2 0,2,4 4 10 50 30 90 3 0,2,4,3 3 10 50 30 60 4 0,2,4,3

18、,5 5 10 50 30 60 5 0,2,4,3,5,1 1 10 50 30 6050324100601030105020V015D0 D1 D2 D3 D4 D5 10 30 100D 10 30 100 5 50 10 20 60 C例題26每一對(duì)頂點(diǎn)間的最短路徑基本思想： 假設(shè)求頂點(diǎn)vi到頂點(diǎn)vj的最短路徑。如果從 vi 到 vj 存在一條長度為Cij的路徑，該路徑不一定是最短路徑，尚需進(jìn)行 n 次試探。首先考慮路徑 (vi,v0,vj) 是否存在。如果存在，則比較 (vi,vj) 和 (vi,v0,vj) 的路徑長度取長度較短者為從vi到vj的中間頂點(diǎn)的序號(hào)不大于0的最短路徑。假

19、設(shè)在路徑上再增加一個(gè)頂點(diǎn)v1,也就是說，如果 (vi,vj)和 (v1,vj) 分別是當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于0的最短路徑,那么 (vi,v1,vj)就是有可能是從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑。 將它和已經(jīng)得到的從vi到vj中間頂點(diǎn)序號(hào)不大于0的最短路徑相比較，從中選出中間頂點(diǎn)的序號(hào)不大于1的最短路徑，在增加一個(gè)頂點(diǎn)v2, 繼續(xù)進(jìn)行試探。 一般情況下，若 (vi,vk) 和 (vk,vj) 分別是從 vi到vk和從vk到Vj的中間頂點(diǎn)序號(hào)不大于 k-1 的最短路徑，則將 (vi,vk,vj) 和已經(jīng)得到的從 vi到 vj且中間頂點(diǎn)序號(hào)不大于k-1的最短路徑相比較，其長度較短者便是從vi到 vj 的中間頂點(diǎn)的序號(hào)不大于