拓撲排序和關(guān)鍵路徑

關(guān)于拓撲排序和關(guān)鍵路徑AOV-網(wǎng)

用頂點表示活動，用邊來表示活動之間的先后關(guān)系的有向圖稱為頂點活動網(wǎng)，簡稱AOV-網(wǎng)。例如，計算機專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。7.5.1拓撲排序第2頁,共32頁，2024年2月25日，星期天

C1

高等數(shù)學(xué)

C2

程序設(shè)計基礎(chǔ)

C3

離散數(shù)學(xué)C1,C2

C4

數(shù)據(jù)結(jié)構(gòu)C3,C2C5

高級語言程序設(shè)計C2C6

編譯方法C5,C4C7

操作系統(tǒng)C4,C9C8

普通物理C1C9

計算機原理C8

課程代號課程名稱先修課程第3頁,共32頁，2024年2月25日，星期天學(xué)生課程學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C2第4頁,共32頁，2024年2月25日，星期天在AOV網(wǎng)絡(luò)中不能出現(xiàn)回路,即環(huán)。如果出現(xiàn)了環(huán)，則意味著某項活動應(yīng)以自己作為先決條件，這是荒謬的。因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。第5頁,共32頁，2024年2月25日，星期天檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造它的拓撲有序序列。即將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)全部頂點的拓撲有序序列的運算就叫做拓撲排序。如果通過拓撲排序能將AOV網(wǎng)絡(luò)的所有頂點都排入一個拓撲有序的序列中,則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。第6頁,共32頁，2024年2月25日，星期天如果AOV網(wǎng)絡(luò)中存在環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。例如,對學(xué)生選課工程圖進行拓撲排序,得到的拓撲有序序列為

C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第7頁,共32頁，2024年2月25日，星期天拓撲排序的方法①

輸入AOV網(wǎng)絡(luò)。令n為頂點個數(shù)。 ②在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點,并輸出之;③從圖中刪去該頂點,同時刪去所有它發(fā)出的有向邊;④重復(fù)以上②、③步,直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點,但已跳出處理循環(huán)。說明圖中還剩下一些頂點,它們都有直接前驅(qū)。這時網(wǎng)絡(luò)中必存在有向環(huán)。第8頁,共32頁，2024年2月25日，星期天C0C1C4C3C2C5拓撲排序的過程(a)有向無環(huán)圖C4C5C1C0C3(b)輸出頂點C2C1C4C5C3(c)輸出頂點C0C2C0C4C5C1C3(d)輸出頂點C3第9頁,共32頁，2024年2月25日，星期天C1C4C5(e)輸出頂點C4C5C1(f)輸出頂點C1C5(g)輸出頂點C5

最后得到的拓撲有序序列為C2,C0,C3,C4,C1,C5

。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點，如C2和C4，也排出了先后次序關(guān)系。(h)拓撲排序完成第10頁,共32頁，2024年2月25日，星期天AOV網(wǎng)絡(luò)及其鄰接表表示C0C1C4C3C2C5C0C1C2C30C4C50012345indegreedatafirstarc

1301031adjvexnextarc30501500150第11頁,共32頁，2024年2月25日，星期天在鄰接表中增設(shè)一個數(shù)組indegree[]，記錄各頂點入度。在拓撲排序前前,初始化入度數(shù)組。入度為零的頂點即無前驅(qū)頂點。在算法中,使用棧存放入度為零的頂點,供選擇和輸出無前驅(qū)的頂點。第12頁,共32頁，2024年2月25日，星期天拓撲排序算法可描述如下：入度為零的頂點入棧;當(dāng)棧不空時,重復(fù)執(zhí)行

從頂點棧中退出一個頂點,并輸出之;

從AOV網(wǎng)絡(luò)中刪去這個頂點和它發(fā)出的邊,邊的終頂點入度減一;

如果邊的終頂點入度減至0,則該頂點進棧;

如果輸出頂點個數(shù)少于AOV網(wǎng)絡(luò)的頂點個數(shù),則報告網(wǎng)絡(luò)中存在有向環(huán)。第13頁,共32頁，2024年2月25日，星期天拓撲排序的算法voidTopologicalSort(ALGraphG){FindInDegree(G,indegree);//初始化indegree[]InitStack(S);for(i=0;i<G.vexnum;i++)//入度為零的頂點

if(indegree[i]==0)Push(S,i);//進棧

count=0;//對輸出頂點計數(shù)

第14頁,共32頁，2024年2月25日，星期天while(!StackEmpty(S)){

Pop(S,i);//退棧

cout<<i<<G.vertices[i].data;//輸出i號頂點

count++;//并計數(shù)

//掃描i號頂點的每個鄰接點

for(p=G.vertices[i].

firstarc;p;p=p->nextarc){k=p->adjvex;

if(--indegree[k]==0)//頂點入度減1 Push(S,k);//頂點的入度減至零,進棧

}}}第15頁,共32頁，2024年2月25日，星期天7.5.2關(guān)鍵路徑一、AOE網(wǎng)如果在有向無環(huán)圖中,用有向邊表示一個工程中的活動(Activity),

用邊上權(quán)值表示活動持續(xù)時間(Duration),

用頂點表示事件,

則這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò),簡稱AOE(ActivityOnEdges)網(wǎng)。第16頁,共32頁，2024年2月25日，星期天AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個工程至少需要多少時間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?為縮短完成工程所需的時間,應(yīng)當(dāng)加快哪些活動?第17頁,共32頁，2024年2月25日，星期天從源點到匯點的路徑可能不止一條，并且這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同,但只有各條路徑上所有活動都完成了,整個工程才算完成。因此,完成整個工程所需的時間取決于從源點到匯點的最長路徑長度,即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(CriticalPath)。第18頁,共32頁，2024年2月25日，星期天要找出關(guān)鍵路徑，必須找出關(guān)鍵活動,即不按期完成就會影響整個工程完成的活動。關(guān)鍵路徑上的所有活動都是關(guān)鍵活動。因此,只要找到了關(guān)鍵活動,就可以找到關(guān)鍵路徑。例如,下圖就是一個AOE網(wǎng)。V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1第19頁,共32頁，2024年2月25日，星期天二、相關(guān)術(shù)語①

事件Vi

的最早發(fā)生時間ve(i)

是從源點V0

到頂點Vi的最長路徑長度。②

事件Vi的最遲發(fā)生時間vl(i)

在不推遲整個工程完成的前提下，事件Vi

的最遲發(fā)生時間。③

活動ai的最早開始時間

e(i)④

活動ai

的最遲開始時間

l(i)

表示在不推遲整個工程完成的前提下，活動ai最遲必須開始進行的事件。第20頁,共32頁，2024年2月25日，星期天⑤

時間余量

l(i)–e(i)

表示活動

ai的最早可能開始時間和最遲允許開始時間的時間余量。

l(i)=e(i)的活動稱為關(guān)鍵活動。第21頁,共32頁，2024年2月25日，星期天三、怎樣求關(guān)鍵路徑？

如何找e(i)=l(i)的關(guān)鍵活動？為找出關(guān)鍵活動,需要求各個活動的e(i)

與l(i)，以判別是否l(i)=e(i)。設(shè)活動ai由弧<Vj,Vk>表示，且活動持續(xù)時間記為dut(<j,k>),

則

e(i)=ve(j)

l(i)=vl(k)-dut(<j,k>)VjVkai第22頁,共32頁，2024年2月25日，星期天

如何求ve(i)和vl(i)？求ve(i)的遞推公式

從

ve(0)=0開始，向前遞推

<i,j

>T,i=1,2,,n-1

T

是所有以第j個頂點為頭的弧的集合。例，求右圖中頂點V6的最早發(fā)生時間。V3V4V5V6a6=3a7=2a8=1266第23頁,共32頁，2024年2月25日，星期天V1V2V3V4V5V6頂點vevl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1032668第24頁,共32頁，2024年2月25日，星期天求vl(i)的遞推公式從vl(n-1)=ve(n-1)開始，反向遞推

<i,j>S,i=n-2,n-3,,0S是所有以第i個頂點為尾的弧的集合。

例，求右圖中頂點V1的最遲發(fā)生時間。V1V3V2a1=3a2=224第25頁,共32頁，2024年2月25日，星期天V1V2V3V4V5V6頂點vevl032668V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1042678042678第26頁,共32頁，2024年2月25日，星期天a1a2a3a4a5a6a7a8活動ell-e

011000341220253660671341V1V3V2V4a1=3a2=2V5V6a6=3a7=2a4=3a3=2a5=4a8=1V1V2V3V4V5V6頂點vevl032668042678第27頁,共32頁，2024年2月25日，星期天四、算法實現(xiàn)實現(xiàn)步驟：

①輸入e條弧<j,k>，建立AOE-網(wǎng)的存儲結(jié)構(gòu)；

②從源點v0出發(fā)，令ve[0]=0，按拓撲有序求其余各頂點的最早發(fā)生時間ve[i]（1≤i≤n-1）。如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟③。

③從匯點vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓撲有序求其余各頂點的最遲發(fā)生時間vl[i]（n-2≥i≥2）；

④根據(jù)各頂點的ve和vl的值，求每條弧s的最早發(fā)生時間e(s)和最遲發(fā)生時間l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動。第28頁,共32頁，2024年2月25日，星期天

算法實現(xiàn)StatusTopologicalOrder(ALGraphG,Stack&T){

//求各頂點事件的最早發(fā)生時間ve（全局變量），T為拓撲序列頂點棧

FindInDegree(G,indegree)；//對各頂點求入度

InitStack(T)；count=0；ve[0..G.vexnum-1]=0；//初始化

while(!StackEmpty(S))//S為零入度頂點棧

{Pop(S,j)；push(T,j)；++count；//j號頂點入T棧并計數(shù)

for(p=G.vertices[j].firstarc；p；p=p→nextarc){k=p→adjvex；//對j號頂點的每個鄰接點的入度減1

if(--indegree[k]==0)push(S,k)；

if(ve[j]+*(p→info)>ve[k])ve[k]=ve[j]+*(p→info)；

}

}

if(count<G.vexnum)returnERROR；//該有向網(wǎng)有回路

elsereturnOK；

}第29頁,共32頁，2024年2月25日，星期天StatusCriticalPath(ALGraphG){

//G為有向網(wǎng)，輸出G的各項關(guān)鍵活動

if(!TopologicalOrder(G,T)returnERROR;

vl[0.