拓?fù)渑判蚺c關(guān)鍵路徑第一頁，共五十八頁，2022年，8月28日有向無環(huán)圖：一個無環(huán)的有向圖，簡稱DAG圖。P179圖7.22、7.23DAG圖：

描述含有公共子式的表達(dá)式及工程或系統(tǒng)的進(jìn)行過程時的有效工具。活動：一個較大的工程被劃分成許多子工程，這些子工程被稱作活動。活動之間，存在某種約束，如：某些子工程的開始必須在另外一些子工程完成之后。關(guān)心問題： 1.工程能否順利進(jìn)行 2.估算整個工程完成所必須的最短時間 第二頁，共五十八頁，2022年，8月28日7.5有向無環(huán)圖及其應(yīng)用拓?fù)渑判騿栴}提出：學(xué)生選修課程問題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判?/p>

定義AOV網(wǎng)——用頂點(diǎn)表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動以自己為先決條件第三頁，共五十八頁，2022年，8月28日拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程叫~檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個沒有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止第四頁，共五十八頁，2022年，8月28日例課程代號課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12第五頁，共五十八頁，2022年，8月28日C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--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)的拓?fù)湫蛄胁皇俏ㄒ坏牡诹摚参迨隧摚?022年，8月28日C1C2C3C4C5C6C7C8C9C10C11C12第七頁，共五十八頁，2022年，8月28日C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2（2）第八頁，共五十八頁，2022年，8月28日C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3（3）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4（4）第九頁，共五十八頁，2022年，8月28日C6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9C6C8C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7（6）第十頁，共五十八頁，2022年，8月28日C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）第十一頁，共五十八頁，2022年，8月28日算法實(shí)現(xiàn)以鄰接表作存儲結(jié)構(gòu)設(shè)置一個包含n個元素的一維數(shù)組indegree，保存AOV網(wǎng)中每個頂點(diǎn)的入度值。把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1，即indegree[k]-1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至棧空為止。若棧空時輸出的頂點(diǎn)個數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叺谑摚参迨隧摚?022年，8月28日32104算法描述例1234560122indegree

firstarc

5

5

4

3^^^

adjvex

nextarc3^

2

5^

2

40123456^top16toptop第十三頁，共五十八頁，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next3^

2

5^

2

40123456^輸出序列：63210416toptop第十四頁，共五十八頁，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next3^

2

5^

2

40123456^輸出序列：6321041topp第十五頁，共五十八頁，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6321041topp第十六頁，共五十八頁，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6321041topp第十七頁，共五十八頁，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6321041topp第十八頁，共五十八頁，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6321041topp=NULL第十九頁，共五十八頁，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：61321041toptop第二十頁，共五十八頁，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104topp第二十一頁，共五十八頁，2022年，8月28日0102indegree

First

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104topp4第二十二頁，共五十八頁，2022年，8月28日0102indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104p4top第二十三頁，共五十八頁，2022年，8月28日0102indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104p4top第二十四頁，共五十八頁，2022年，8月28日0002indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104p4top3第二十五頁，共五十八頁，2022年，8月28日0002indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104p4top3第二十六頁，共五十八頁，2022年，8月28日0002indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104p4top3第二十七頁，共五十八頁，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104p4top3第二十八頁，共五十八頁，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：6132104p=NULL4top3第二十九頁，共五十八頁，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：613321044top3第三十頁，共五十八頁，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^輸出序列：613321044topp第三十一頁，共五十八頁，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：613321044topp第三十二頁，共五十八頁，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：613321044topp第三十三頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：613321044topp2第三十四頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：613321044topp2第三十五頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：613321044top2p=NULL第三十六頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：6132321044top2p=NULL第三十七頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：6132321044topp=NULL第三十八頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：61324321044top第三十九頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^輸出序列：6132432104topp第四十頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^輸出序列：6132432104topp5第四十一頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^輸出序列：6132432104topp=NULL5第四十二頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^輸出序列：61324532104top5第四十三頁，共五十八頁，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^輸出序列：61324532104topp=NULL第四十四頁，共五十八頁，2022年，8月28日算法分析--算法7.12建鄰接表：T(n)=O(e)搜索入度為0的頂點(diǎn)的時間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)第四十五頁，共五十八頁，2022年，8月28日關(guān)鍵路徑問題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始例設(shè)一個工程有11項(xiàng)活動，9個事件事件V1——表示整個工程開始事件V9——表示整個工程結(jié)束問題：（1）完成整項(xiàng)工程至少需要多少時間？（2）哪些活動是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第四十六頁，共五十八頁，2022年，8月28日定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點(diǎ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)的活動第四十七頁，共五十八頁，2022年，8月28日問題分析如何找e(i)=l(i)的關(guān)鍵活動？設(shè)活動ai用弧<j,k>表示，其持續(xù)時間記為：dut(<j,k>)則有：（1）e(i)=Ve(j)

（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開始遞推(2)從Vl(n)=Ve(n)開始遞推第四十八頁，共五十八頁，2022年，8月28日求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動ell-e00002266046258377077071031616014140033第四十九頁，共五十八頁，2022年，8月28日算法實(shí)現(xiàn)以鄰接表作存儲結(jié)構(gòu)從源點(diǎn)V1出發(fā)，令Ve[1]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的Ve[i]從匯點(diǎn)Vn出發(fā)，令Vl[n]=Ve[n],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vl[i]根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動第五十頁，共五十八頁，2022年，8月28日算法描述1-輸入頂點(diǎn)和弧信息，建立其鄰接表計(jì)算每個頂點(diǎn)的入度2-對其進(jìn)行拓?fù)渑判?.1-排序過程中求頂點(diǎn)的Ve[i]2.2-將得到的拓?fù)湫蛄羞M(jìn)棧3-按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]4-計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動第五十一頁，共五十八頁，2022年，8月28日StatusTopologicalOrder(ALGraphG,Stack&T){//算法7.13//有向網(wǎng)G采用鄰接表存儲結(jié)構(gòu)，求各頂點(diǎn)事件的最早發(fā)生時間ve(全局變量)。

//T為拓?fù)湫蛄卸c(diǎn)棧，S為零入度頂點(diǎn)棧。

//若G無回路，則用棧T返回G的一個拓?fù)湫蛄校液瘮?shù)值為OK，否則為ERROR。

StackS;intcount=0,k;charindegree[40];ArcNode*p;InitStack(S);FindInDegree(G,indegree);//對各頂點(diǎn)求入度indegree[0..vernum-1]for(intj=0;j<G.vexnum;++j)//建零入度頂點(diǎn)棧Sif(indegree[j]==0)Push(S,j);//入度為0者進(jìn)棧

InitStack(T);//建拓?fù)湫蛄许旤c(diǎn)棧Tcount=0;for(inti=0;i<G.vexnum;i++)ve[i]=0;//初始化

while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;//j號頂點(diǎn)入T棧并計(jì)數(shù)

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;//對j號頂點(diǎn)的每個鄰接點(diǎn)的入度減1if(--indegree[k]==0)Push(S,k);//若入度減為0，則入棧

if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;}//for*(p->info)=dut(<j,k>)}//whileif(count<G.vexnum)returnERROR;//該有向網(wǎng)有回路

elsereturnOK;}//TopologicalOrder第五十二頁，共五十八頁，2022年，8月28日StatusCriticalPath(ALGraphG){//算法7.14,G為有向網(wǎng)，輸出G的各項(xiàng)關(guān)鍵活動。StackT;inta,j,k,el,ee,dut;chartag;ArcNode*p;if(!TopologicalOrder(G,T))returnERROR;for(a=0;a<G.vexnum;a++)