[工學(xué)]數(shù)據(jù)機(jī)構(gòu)課件第7章圖(編輯修改稿)
2024-11-15 00:01 本頁面
【文章內(nèi)容簡介】 7=4 a1=6 求事件的最早發(fā)生時(shí)間 ve(i) 從 ve(0) = 0 開始向前遞推 ve(j) = Max{ve(i) + dut( )} ∈ T， j = 1， 2， … ， n – 1 其中， T 是所有以第 j 個頂點(diǎn)為頭的弧的集合 i， j 〈 〉 i， j 〈 〉 i V1 V2 V3 V4 V5 a2=5 a3=8 a4=4 a5=4 a1=6 求事件的最遲發(fā)生時(shí)間 vl(i) 從 vl(n – 1) = ve(n – 1) 開始向后遞推 vl(i) = Min{vl(j) – dut( )} ∈ S， j = 1， 2， … ， n – 1 其中， S 是所有以第 i 個頂點(diǎn)為尾的弧的集合 i， j 〈 〉 i， j 〈 〉 j V2 V3 V4 V5 V1 a3=2 a4=9 a5=3 a1=4 a2=6 V2 V5 V4 V6 V1 V3 a4=3 a7=2 a8=1 a3=2 a1=3 a2=2 a5=4 a6=3 0 頂點(diǎn) ve vl V1 V2 V3 V4 V5 V6 3 2 6 6 8 0 4 2 6 7 8 0 1 0 0 3 4 3 4 2 2 2 5 6 6 6 7 1 0 1 1 0 3 0 1 活動 e l l – e a1 a2 a3 a4 a5 a6 a7 a8 √ √ √ V4 V6 V1 V3 a7=2 a2=2 a5=4 Status ToplogicalOrder(ALGraph G , stack amp。T) { FindInDegree(G , indegree)。 InitStack(S)。 for(i = 0； i ； ++i) if(!indegree[i]) Push(S， i)； InitStack(T)。 count=0。 ve[0..]=0。 while(!StackEmpty(S)) { …… } if(count) return ERROR。 else return OK。 } while (!StackEmpty(S) ) { Pop (S , j )。 Push (T , j )。 ++count。 for(p=[j].firstarc 。 p 。 p=pnextarc) { k=padjvex。 if(indegree[k]==0) Push(S,k)。 if(ve[j]+*(pinfo)ve[k]) ve[k]=ve[j]+*(pinfo)。 } } status CriticalPath(ALGraph G) { if(!ToplogicalOrder(G,T)) return ERROR。 vl[0..]=ve[0..]。 while(!StackEmpty(T)) //求各頂點(diǎn) vl 值 for(Pop(T,j),p=[j].firstarc。p。p=pnextarc) { k=padjvex。 dut=*(pinfo)。 if(vl[k]dutvl[j]) vl[j]=vl[k]dut。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1