5-6有向無環(huán)圖及應(yīng)用v第五章圖AOV網(wǎng)與拓?fù)渑判驅(qū)W什么？AOE網(wǎng)與關(guān)鍵路徑5-6-1AOV網(wǎng)與拓?fù)渑判騰第五章圖AOV網(wǎng)的定義什么是工程？工程有什么共性？幾乎所有的工程都可以分為若干個(gè)稱作活動(dòng)的子工程，某些活動(dòng)之間通常存在一定的約束條件AOV網(wǎng)（頂點(diǎn)表示活動(dòng)的網(wǎng)）：在一個(gè)表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系A(chǔ)OV網(wǎng)中出現(xiàn)回路意味著什么？活動(dòng)之間的優(yōu)先關(guān)系是矛盾的AOV網(wǎng)（activityonvertexnetwork）拓?fù)湫蛄械亩xv1v0v3v5v4v2v6拓?fù)湫蛄校涸O(shè)有向圖G=(V，E)具有n個(gè)頂點(diǎn)，則頂點(diǎn)序列v0,v1,…,vn-1

稱為一個(gè)拓?fù)湫蛄?，?dāng)且僅當(dāng)滿足下列條件：若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在頂點(diǎn)vj之前拓?fù)湫蛄?：v0v1v2v3v4v5v6拓?fù)渑判颍簩?duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^程拓?fù)湫蛄?：v0v1v3v2v4v5v6使得AOV網(wǎng)中所有應(yīng)該存在的前驅(qū)和后繼關(guān)系都能得到滿足基本思想算法：拓?fù)渑判騎opSort輸入：AOV網(wǎng)G=(V，E)輸出：拓?fù)湫蛄?/p>

1.重復(fù)下述操作，直到輸出全部頂點(diǎn)，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)

1.1從AOV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并且輸出；

1.2從AOV網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的??；v1v0v3v5v4v2v6拓?fù)湫蛄校簐0v1v3v4v2v5v6算法：拓?fù)渑判騎opSort輸入：AOV網(wǎng)G=(V，E)輸出：拓?fù)湫蛄?/p>

1.重復(fù)下述操作，直到輸出全部頂點(diǎn)，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)

1.1從AOV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并且輸出；

1.2從AOV網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的??；圖采用什么存儲(chǔ)結(jié)構(gòu)呢？鄰接表存儲(chǔ)結(jié)構(gòu)算法：拓?fù)渑判騎opSort輸入：AOV網(wǎng)G=(V，E)輸出：拓?fù)湫蛄?/p>

1.重復(fù)下述操作，直到輸出全部頂點(diǎn)，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)

1.1從AOV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并且輸出；

1.2從AOV網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的??；在鄰接表中，如何求頂點(diǎn)的入度？頂點(diǎn)表中增加入度域圖采用什么存儲(chǔ)結(jié)構(gòu)呢？鄰接表存儲(chǔ)結(jié)構(gòu)

invertexfirstEdgev0v1v3v2v4v503

∧03

∧012345325

∧

v0

v1

v2

v3v4v5

5

∧0

∧∧3013

02如何查找沒有前驅(qū)的頂點(diǎn)？設(shè)置?；蜿?duì)列（哪個(gè)更好？）v1v4S在鄰接表中，如何求頂點(diǎn)的入度？頂點(diǎn)表中增加入度域圖采用什么存儲(chǔ)結(jié)構(gòu)呢？鄰接表存儲(chǔ)結(jié)構(gòu)算法描述算法：TopSort輸入：有向圖G=(V，E)輸出：拓?fù)湫蛄?.棧S初始化；累加器count初始化；2.掃描頂點(diǎn)表，將入度為0的頂點(diǎn)壓棧；3.當(dāng)棧S非空時(shí)循環(huán)

3.1j=棧頂元素出棧；輸出頂點(diǎn)j；count++；

3.2對(duì)頂點(diǎn)j的每一個(gè)鄰接點(diǎn)k執(zhí)行下述操作：3.2.1將頂點(diǎn)k的入度減1；3.2.2如果頂點(diǎn)k的入度為0，則將頂點(diǎn)k入棧；4.if(count<vertexNum)輸出有回路信息；圖：帶入度的鄰接表?xiàng)＃喝攵葹?的頂點(diǎn)（編號(hào)）v0v1v3v2v4v5

invertexfirstEdge03

∧03

∧012345325

∧

v0

v1

v2

v3v4v5

5

∧0

∧∧

3013

0214SvoidTopSort(

){inti,j,k,count=0,S[MaxSize],top=-1;for(i=0;i<vertexNum;i++)if(adjList[i].in==0)S[++top]=i;算法實(shí)現(xiàn)v0v1v3v2v4v5

invertexfirstEdge03

∧03

∧012345325

∧

v0

v1

v2

v3v4v5

5

∧0

∧∧

3013

0214S0212while(top!=-1){j=S[top--];cout<<adjList[j].vertex;count++;p=adjList[j].firstEdge;while(p!=nullptr){k=p->adjvex;adjList[k].in--;if(adjList[k].in==0)S[++top]=k;p=p->next;}Page04算法實(shí)現(xiàn)v0v1v3v2v5

invertexfirstEdge03

∧03

∧012345325

∧

v0

v1

v2

v3v4v5

5

∧0

∧∧

3002

0112S21Page05while(top!=-1){j=S[top--];cout<<adjList[j].vertex;count++;p=adjList[j].firstEdge;while(p!=nullptr){k=p->adjvex;adjList[k].in--;if(adjList[k].in==0)S[++top]=k;p=p->next;}驗(yàn)證算法voidTopSort(){inti,j,k,count=0,S[MaxSize],top=-1;EdgeNode*p=nullptr;

for(i=0;i<vertexNum;i++)/*掃描頂點(diǎn)表*/if(adjList[i].in==0)S[++top]=i;if(count<vertexNum)cout<<"有回路”;}O(n)時(shí)間復(fù)雜度？O(n+e)O(e)p=adjList[j].first;while(p!=nullptr)/*描頂點(diǎn)表，找出頂點(diǎn)j的所有出邊*/{k=p->adjvex;adjList[k].in--;if(adjList[k].in==0)S[++top]=k;/*將入度為0的頂點(diǎn)入棧*/p=p->next;}

while(top!=-1)/*當(dāng)棧中還有入度為0的頂點(diǎn)時(shí)*/{j=S[top--];cout<<adjList[j].vertex;count++;

}算法實(shí)現(xiàn)5-6-2AOE網(wǎng)與關(guān)鍵路徑v第五章圖AOE網(wǎng)的定義什么是工程？工程有什么共性？幾乎所有的工程都可以分為若干個(gè)稱作活動(dòng)的子工程活動(dòng)之間存在某些制約關(guān)系每個(gè)活動(dòng)通常需要一個(gè)持續(xù)的時(shí)間AOE網(wǎng)（邊表示活動(dòng)的網(wǎng)）：在一個(gè)表示工程的帶權(quán)有向圖中，用頂點(diǎn)表示事件，用有向邊表示活動(dòng)，邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間v1v0v3v2a0=4a1=3a4=6a3=4a2=2源點(diǎn)：整個(gè)工程的開始點(diǎn)，其入度為0終點(diǎn)：整個(gè)工程的結(jié)束點(diǎn)，其出度為0AOE網(wǎng)（activityonedgenetwork）v1v0v3v2a0=4a1=3a4=6a3=4a2=2事件

事件含義v0

源點(diǎn)，整個(gè)工程開始v1

活動(dòng)

a0完成，活動(dòng)

a2和

a4可以開始v2

活動(dòng)

a1和

a2完成，活動(dòng)

a3可以開始v3

活動(dòng)

a3和

a4完成，整個(gè)工程結(jié)束AOE網(wǎng)的性質(zhì)：（1）只有在進(jìn)入某頂點(diǎn)的各活動(dòng)都已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生（2）只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各活動(dòng)才能開始AOE網(wǎng)的定義v1v0v3v2a0=4a1=3a4=6a3=4a2=2（1）

完成整個(gè)工程至少需要多少時(shí)間?（2）為縮短完成工程所需的時(shí)間，

應(yīng)當(dāng)加快哪些活動(dòng)?AOE網(wǎng)能夠解決什么問題？這個(gè)AOE網(wǎng)的最短工期是多少？v1v0v3v2a0=4a1=3a4=6a3=4a2=2關(guān)鍵路徑：AOE網(wǎng)中從源點(diǎn)到終點(diǎn)的最長(zhǎng)路徑關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)不按期完成關(guān)鍵活動(dòng)就會(huì)影響整個(gè)工程的進(jìn)度AOE網(wǎng)的定義基本思想v1v0v3v2a0=4a1=3a4=6a3=4a2=2如何求關(guān)鍵路徑呢？求關(guān)鍵活動(dòng)如何求關(guān)鍵活動(dòng)呢？關(guān)鍵活動(dòng)為什么是關(guān)鍵的？關(guān)鍵活動(dòng)的開始時(shí)間不能推遲關(guān)鍵活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間相等算法：關(guān)鍵路徑算法輸入：帶權(quán)有向圖

G=(V，E)輸出：關(guān)鍵活動(dòng)1.計(jì)算各個(gè)活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間2.計(jì)算各個(gè)活動(dòng)的時(shí)間余量，時(shí)間余量為0即為關(guān)鍵活動(dòng)算法：關(guān)鍵路徑算法輸入：帶權(quán)有向圖

G=(V，E)輸出：關(guān)鍵活動(dòng)1.計(jì)算各個(gè)事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間；2.計(jì)算各個(gè)活動(dòng)的最早開始時(shí)間和最晚開始時(shí)間；3.計(jì)算各個(gè)活動(dòng)的時(shí)間余量，時(shí)間余量為0即為關(guān)鍵活動(dòng)；設(shè)帶權(quán)有向圖

G=(V，E)含有n

個(gè)頂點(diǎn)e

條邊，設(shè)置4個(gè)一維數(shù)組：（1）事件的最早發(fā)生時(shí)間ve[n]（2）事件的最遲發(fā)生時(shí)間vl[n]：（3）活動(dòng)的最早開始時(shí)間ae[e]（4）活動(dòng)的最晚開始時(shí)間al[e]存儲(chǔ)結(jié)構(gòu)（1）事件的最早發(fā)生時(shí)間ve[n]AOE網(wǎng)的性質(zhì)：只有進(jìn)入

vk的所有活動(dòng)<vj,vk>都結(jié)束，vk代表的事件才能發(fā)生ve[0]=0ve[k]=max{ve[j]+len<vj,vk>}(<vj,vk>∈p[k])p[k]：所有到達(dá)vk的有向邊v1v0v3v2a0=4a1=3a4=6a3=4a2=2事件v2的最早發(fā)生時(shí)間是多少？ve[2]=max{ve[0]+a1,ve[1]+a2}={0+3,4+2}=6運(yùn)行實(shí)例v1v3v0v2ve[k]04610（2）事件的最遲發(fā)生時(shí)間vl[n]vl[n-1]=ve[n-1]vl[k]=min{vl[j]-len<vk,vj>}（<vk,vj>∈s[k]）s[k]：所有從vk發(fā)出的有向邊v1v0v3v2a0=4a1=3a4=6a3=4a2=2事件v3的最遲發(fā)生時(shí)間是多少？vl[2]=vl[3]–a3=6vl[3]=ve[3]=10事件v2的最遲發(fā)生時(shí)間是多少？事件v0的最遲發(fā)生時(shí)間是多少？ve[0]=min{ve[1]–a0,ve[2]–a1}={4–4,6–3}=0運(yùn)行實(shí)例AOE網(wǎng)的性質(zhì)：只有進(jìn)入

vk的所有活動(dòng)<vj,vk>都結(jié)束，vk代表的事件才能發(fā)生v1v0v3v2a0=4a1=3a4=6a3=4a2=2vl[n-1]=ve[n-1]vl[k]=min{vl[j]-len<vk,vj