數(shù)據(jù)結(jié)構(gòu)與算法(吳躍)ch4-4

1、4.4.3 關(guān)鍵路徑問題提出把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始例 設(shè)一個工程有11項活動，9個事件事件 V1表示整個工程開始事件V9表示整個工程結(jié)束問題：（1）完成整項工程至少需要多少時間？ （2）哪些活動是影響工程進度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4定義vAOE網(wǎng)(Activity On Edge)也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間v路徑長度路徑上各活動持續(xù)時間之和v關(guān)

2、鍵路徑路徑長度最長的路徑叫vVe(j)表示事件Vj的最早發(fā)生時間vVl(j)表示事件Vj的最遲發(fā)生時間ve(i)表示活動ai的最早開始時間vl(i)表示活動ai的最遲開始時間vl(i)-e(i)表示完成活動ai的時間余量v關(guān)鍵活動關(guān)鍵路徑上的活動叫，即l(i)=e(i)的活動問題分析v如何找e(i)=l(i)的關(guān)鍵活動？設(shè)活動ai用弧表示，其持續(xù)時間記為：dut()則有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkaiv如何求Ve(j)和Vl(j)？事件的最早、最遲發(fā)生時間(1)從Ve(1)=0開始向前遞推為頭的弧的集合是所有以其中jTnjTjijidutiVeMax

3、jVei2 ,),()()(2)從Vl(n)=Ve(n)開始向后遞推為尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(求關(guān)鍵路徑步驟v求Ve(i)v求Vl(j)v求e(i)v求l(i)v計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動 e l l-e00002266046258377077071031616014140

4、033算法實現(xiàn)v以鄰接表作存儲結(jié)構(gòu)v從源點V1出發(fā)，令Ve1=0,按拓?fù)湫蛄星蟾黜旤c的Veiv從匯點Vn出發(fā)，令Vln=Ven,按逆拓?fù)湫蛄星笃溆喔黜旤c的Vliv根據(jù)各頂點的Ve和Vl值，計算每條弧的ei和li,找出ei=li的關(guān)鍵活動鄰接表結(jié)點：typedef struct node int vex; /頂點域 int length; struct node *next; /鏈域JD;表頭結(jié)點：typedef struct tnode int vexdata; int in; /入度域 struct node *link; /鏈域TD;TD gM; /g0不用算法描述v輸入頂點和弧信息，建立

5、其鄰接表v計算每個頂點的入度v對其進行拓?fù)渑判騦排序過程中求頂點的Veil將得到的拓?fù)湫蛄羞M棧v按逆拓?fù)湫蛄星箜旤c的Vliv計算每條弧的ei和li,找出ei=li的關(guān)鍵活動Ch6_20.c987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 944.4.4 最短路

6、徑問題提出用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：頂點表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中， 各邊上權(quán)值之和最小的一條路徑最短路徑從某個源點到其余各頂點的最短路徑51643208562301371732913長度最短路徑813192120v迪杰斯特拉(Dijkstra)算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中，保證：（1）從源點V0到S中各頂點的最短路徑長度都不

7、大于 從V0到T中任何頂點的最短路徑長度 （2）每個頂點對應(yīng)一個距離值 S中頂點：從V0到此頂點的最短路徑長度 T中頂點：從V0到此頂點的只包括S中頂點作中間 頂點的最短路徑長度依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的 直接路徑的權(quán)值；或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和（反證法可證）v求最短路徑步驟l初使時令 S=V0,T=其余頂點，T中頂點對應(yīng)的距離值u若存在，為弧上的權(quán)值u若不存在，為l從T中選取一個其距離值為最小的頂點W，加入Sl對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值l重復(fù)上述步驟，直到S中包含所

8、有頂點，即S=V為止1383032V2:813-133032V1:13-13302220V3:13-192220V4:19終點 從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329v算法實現(xiàn)l圖用帶權(quán)鄰接矩陣存儲adl數(shù)組dist存放當(dāng)前找到的從源點V0到每個終點的最短路徑長度，其初態(tài)為圖中直接路徑權(quán)值l數(shù)組pre表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號v算法描述627543185623013717329017020605079032308131addist0

9、 1 2 3 4 5 60 13 8 30 32pre0 1 2 3 4 5 60 1 1 0 1 0 1(1)k=1Ch6_5.c1133122 20221941215111長度最短路算法分析：T(n)=O(n)每一對頂點之間的最短路徑v方法一：每次以一個頂點為源點，重復(fù)執(zhí)行Dijkstra算法n次 T(n)=O(n)v方法二：弗洛伊德(Floyd)算法l算法思想：逐個頂點試探法l求最短路徑步驟u初始時設(shè)置一個n階方陣，令其對角線元素為0，若存在弧，則對應(yīng)元素為權(quán)值；否則為u逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值u所有頂

10、點試探完畢，算法結(jié)束例ACB2643110 4 116 0 23 0初始：路徑：AB ACBA BCCA0 4 66 0 23 7 0加入V2：路徑：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入V1：路徑：AB ACBA BCCA CAB0 4 65 0 23 7 0加入V3：路徑：AB ABCBCA BCCA CABl算法實現(xiàn)u圖用鄰接矩陣存儲ulength存放最短路徑長度upathij是從Vi到Vj的最短路徑上Vj前一頂點序號l算法描述例132264311初始：0 4 116 0 23 0length=0 1 12 0 23 0 0path=加入V1：0 4 11

11、6 0 23 7 0length=0 1 12 0 23 1 0path=加入V2：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入V3：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=Ch6_6.cl算法分析：T(n)=O(n)4.5廣義表的定義ADT Glist 數(shù)據(jù)對象數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet為某個數(shù)據(jù)對象 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in基本操作基本操作 ADT Glist 廣義表是遞歸定義的線型結(jié)構(gòu)，

12、其中， 為原子或為子表。 第一個元素 為表頭，其余元素組成的表 稱作表尾，n是表的長度12(,.,)nLS i1( 2, 3.)n基本操作：結(jié)構(gòu)的創(chuàng)建和銷毀： InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);狀態(tài)函數(shù)： GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);插入和刪除操作： InsertFirst_GL(&L, e); DeleteFirst_GL(&L,

13、&e);遍歷： Traverse_GL(L, Visit();比如A=（ ） A是一個空表，長度為0B=（e）列表B只有一個原子e，B的長度為1C=(a,(b,c,d)列表C的長度為2，兩個元素分別是原子a和子表(b,c,d)D=(A,B,C)列表D的長度為3，3個元素都是列表，D=( ),(e),(a,(b,c,d)E=(a,E)是一個遞歸表，長度為2，E相當(dāng)于一個無限的列表E=(a,(a,(a,)我們可以看出（1）列表的元素可以是子表，而子表的元素還可以是子表，因此列表是一個多層次的結(jié)構(gòu)，如圖表示（2）列表可以為其他列 表共享，如A、B、C是 D的子表，那么D可以不 列出子表的值（

14、3）列表可以是一個遞歸的表任何一個非空列表其表頭可能是原子，也可能是列表，表尾必定是列表 GetHead(B)=e GetTail(B)=(）GetHead(D)=AGetHead(D)=(B,C)( )和( )不同，前者是空表，長度為0，后者長度為1，表頭、表尾均為空表（）廣義表的存儲結(jié)構(gòu)通常采用頭、尾指針的鏈表結(jié)構(gòu)，如圖所示。typedef enumATOM,LISTElemTag;/ATOM=0原子， / LIST=1列表typedef enumATOM,LISTElemTag;/ATOM=0原子， / LIST=1子表typedef struct GLNode ElemTag tag;

15、 union AtomType atom;/atom是原子結(jié)點的值域，AtomType由用戶定義 struct struct GLNode *hp,*tp)ptr;/ptr是表結(jié)點的指針域，ptr.hp和ptr.tp分別指向表頭和表尾 *GList頭尾表示法特點：最上層的表結(jié)點數(shù)即為廣義表的長度； 層次清楚；實現(xiàn)遞歸容易；表結(jié)點數(shù)目多，與廣義表中括號對的數(shù)目不匹配。另一種結(jié)點結(jié)構(gòu)的鏈表typedef enumATOM,LISTElemTag;/ATOM=0原子， / LIST=1子表typedef struct GLNode ElemTag tag; union AtomType atom;/原子結(jié)點的值域 struct GLNode *hp;/表結(jié)點的表頭指針 struct GLNode *tp;/相當(dāng)于線性鏈表的next，指向下一個元素結(jié)點*GListm元多項式的表示線性表表示m元多項式的不足結(jié)點設(shè)置m+1項，存儲空間浪費；若按實際變元數(shù)分配，結(jié)點大小不均，操作不便。對m值不同的多項式，結(jié)點大小不同，存儲管理不便。