20拓撲排序和關(guān)鍵路徑-資料下載頁
2025-07-25 15:49本頁面
【正文】 ALGragh G, Stack amp。T){ ………… while (!EmptyStack(S)) { Pop(S, v)。 Push(T,j)。++count。 //j號頂點入棧 T for (p=[j].firstarc。 p。 p=pnextarc){ k=padjvex。 if(indegree(k)==) Push(S,k)。 //入度 1為 0，則入棧 if((ve[j]+*(pinfo))ve[k]) ve[k]= ve[j]+*(pinfo) }//for }//while if (count) return ERROR。 else return OK。 } 關(guān)鍵路徑算法 Status CriticalPath( ALGragh G){//輸出 G的關(guān)鍵活動 if(!) ToplogicalOrder(G,T) return ERROR。 vl[0.. ] =ve[0..]。//用 ve初始化 vl while(!stackEmpty(T)){ pop(T,j)。 for(p=[j].firstarc。p。p=pnextarc){ k=padjvex。 dut=*(pinfo)。 if(vl[k]dutvl[j]) vl[j]=vl[k]dut。 }//end of for }//end of while ………… }//end of CriticalPath 關(guān)鍵路徑算法 Status CriticalPath( ALGragh G){//輸出 G的關(guān)鍵活動 ………… for(j=0。j。++j) for (p=[j].firstarc。 p。 p=pnextarc){ k=padjvex。 dut=*(pinfo)。 ee=ve[j]。el=vl[k]dut。 tag=(ee=el)?’*’:’’。 printf(j,k,dut,ee,el,tag)。 }//end of for(p) }//end of status 關(guān)鍵路徑算法 Status CriticalPath( ALGragh G){//輸出 G的關(guān)鍵活動 ………… for(j=0。j。++j) for (p=[j].firstarc。 p。 p=pnextarc){ k=padjvex。 dut=*(pinfo)。 ee=ve[j]。el=vl[k]dut。 tag=(ee=el)?’*’:’’。 printf(j,k,dut,ee,el,tag)。 }//end of for(p) }//end of status 關(guān)鍵路徑算法分析 ： O(n+e) 。 這種情況下只有同時提高所有關(guān)鍵路徑上的活動的速度，才能使整個工期縮短。 小結(jié)和作業(yè) 本節(jié)主要內(nèi)容： 3. 拓撲排序算法 小結(jié)和作業(yè) 思考題： 下列關(guān)于 AOE網(wǎng)的敘述中，不正確的是（ ）。 A．關(guān)鍵活動不按期完成就會影響整個工程的完成時間 B．任何一個關(guān)鍵活動提前完成，那么整個工程將會提 前完成 C．所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成 D．某些關(guān)鍵活動提前完成，那么整個工程將會提前完成 作業(yè)： ，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1