1、有向無環(huán)圖： 一個無環(huán)的有向圖，簡稱DAG圖。 P179 圖7.22、7.23 DAG圖： 描述含有公共子式的表達式及工程或系統(tǒng)的進行過程時的有效工具。 活動：一個較大的工程被劃分成許多子工程，這些子工程被稱作活動?；顒又g，存在某種約束，如：某些子工程的開始必須在另外一些子工程完成之后。 關(guān)心問題： 1.工程能否順利進行 2.估算 整個工程完成所必須的最短時間,7.5有向無環(huán)圖及其應(yīng)用 拓撲排序 問題提出：學(xué)生選修課程問題 頂點表示課程 有向弧表示先決條件，若課程i是j的先決條件，則圖中有弧 學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)拓撲排序 定義 AOV網(wǎng)用頂點表示活動，用

2、弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng) 若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼 AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件,拓撲排序把AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程叫 檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán) 拓撲排序的方法 在有向圖中選一個沒有前驅(qū)的頂點且輸出之 從圖中刪除該頂點和所有以它為尾的弧 重復(fù)上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅(qū)

3、的頂點為止,拓撲序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一個AOV網(wǎng)的拓撲序列不是唯一的,算法實現(xiàn) 以鄰接表作存儲結(jié)構(gòu) 設(shè)置一個包含n個元素的一維數(shù)組indegree，保存AOV網(wǎng)中每個頂點的入度值。 把鄰接表中所有入度為0的頂點進棧 棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1，即indegreek-1；若Vk的入度為0則進棧 重復(fù)上述操作直至?？諡橹?。若?？諘r輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓撲排序完畢,算法描述,

4、1,6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6 1,輸出序列：6 1,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1 3,4,3,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3 2,4,2,輸出序列：6 1 3 2,4,輸出序列：6

5、1 3 2 4,4,輸出序列：6 1 3 2 4,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4 5,5,輸出序列：6 1 3 2 4 5,算法分析-算法7.12,建鄰接表：T(n)=O(e) 搜索入度為0的頂點的時間：T(n)=O(n) 拓撲排序：T(n)=O(n+e),關(guān)鍵路徑 問題提出,把工程計劃表示為有向圖，用頂點表示事件，弧表示活動； 每個事件表示在它之前的活動已完成，在它之后的活動可以開始,例 設(shè)一個工程有11項活動，9個事件 事件 V1表示整個工程開始 事件V9表示整個工程結(jié)束 問題：（1）完成整項工程至少需要多少時間？ （2）哪

6、些活動是影響工程進度的關(guān)鍵？,定義 AOE網(wǎng)(Activity On Edge)也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間 路徑長度路徑上各活動持續(xù)時間之和 關(guān)鍵路徑路徑長度最長的路徑叫 Ve(j)表示事件Vj的最早發(fā)生時間 Vl(j)表示事件Vj的最遲發(fā)生時間 e(i)表示活動ai的最早開始時間 l(i)表示活動ai的最遲開始時間 l(i)-e(i)表示完成活動ai的時間余量 關(guān)鍵活動關(guān)鍵路徑上的活動叫，即l(i)=e(i)的活動,問題分析 如何找e(i)=l(i)的關(guān)鍵活動？,設(shè)活動ai用弧表示，其持續(xù)時間記為：dut() 則有：（

7、1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,(1)從Ve(1)=0開始遞推,(2)從Vl(n)=Ve(n)開始遞推,求關(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 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11, ,算法實現(xiàn) 以鄰接表作存儲結(jié)構(gòu) 從源點V1出發(fā)，令Ve1=0,按拓撲序列求各頂點的Vei 從匯點Vn出發(fā)，令Vln=Ven,按

8、逆拓撲序列求其余各頂點的Vli 根據(jù)各頂點的Ve和Vl值，計算每條弧的ei和li,找出ei=li的關(guān)鍵活動,算法描述 1-輸入頂點和弧信息，建立其鄰接表 計算每個頂點的入度 2-對其進行拓撲排序 2.1-排序過程中求頂點的Vei 2.2-將得到的拓撲序列進棧 3-按逆拓撲序列求頂點的Vli 4-計算每條弧的ei和li,找出ei=li的關(guān)鍵活動,Status TopologicalOrder(ALGraph G, Stack / TopologicalOrder,Status CriticalPath(ALGraph G) / 算法7.14, G為有向網(wǎng)，輸出G的各項關(guān)鍵活動。 Stack T; int a,j,k,el,ee,dut; char tag; ArcNode *p; if (!TopologicalOrder(G, T) return ERROR; for(a=0; anextarc) k=p-adjvex; dut=p-info; /dut if (vlk-dut nextarc) k=p-adjvex;dut=p-info; ee = vej; el = vlk-dut; tag = (ee=el) ? * : ;