上傳人：1***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：向**（實(shí)名認(rèn)證）

IP屬地：廣東

IP屬地：廣東 上傳時(shí)間：2024-12-06 格式：PPT 頁數(shù)：14 大?。?8.41KB 積分：24 舉報(bào) 版權(quán)申訴

拓?fù)渑判?/p>

頂點(diǎn)表示活動(dòng)（或任務(wù)）,有向邊表示活動(dòng)（或任務(wù)）之間的先后關(guān)系,稱這樣的有向圖為AOV網(wǎng)(ActivityOnVertexNetwork)。所謂拓?fù)湫蛄?，就是把AOV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，該序列滿足如下條件:若AOV網(wǎng)中存在邊<Vi,Vj>，則在該序列中，Vi必位于Vj之前。構(gòu)造AOV網(wǎng)的拓?fù)湫蛄械牟僮鞅环Q為拓?fù)渑判?。引?.1設(shè)圖G=(V,E)是非循環(huán)圖,V(G)≠?,則G中一定存在入度為零的頂點(diǎn)。證明:由于V(G)≠?,故一定有頂點(diǎn)v∈V(G).如果v的入度不為零，那么從v開始，沿有向邊的反方向就可以一直訪問下去。由于G是非循環(huán)圖，故訪問過程中，經(jīng)歷的頂點(diǎn)不能再次出現(xiàn)；又G的頂點(diǎn)個(gè)數(shù)有限，故該過程一定能夠終止，且終止的頂點(diǎn)的入度為零。證畢。?需要注意的是，并非所有AOV網(wǎng)的頂點(diǎn)都可排成拓?fù)湫蛄?。?duì)于存在回路的網(wǎng)，就無法找到其頂點(diǎn)的拓?fù)渑判?。如下圖所示的AOV網(wǎng)，它的拓?fù)湫蛄袘?yīng)該滿足:_x001A_??_x001B_0_x001B_在_x001A_??_x001B_1_x001B_之前，_x001A_??_x001B_1_x001B_在_x001A_??_x001B_2_x001B_之前，_x001A_??_x001B_2_x001B_在_x001A_??_x001B_0_x001B_之前，顯然不存在這樣的線性序列。對(duì)于任何無回路的AOV網(wǎng),其頂點(diǎn)均可排成拓?fù)湫蛄?并且其拓?fù)湫蛄形幢匚ㄒ?。拓?fù)渑判蛩惴ǖ幕静襟E是:1）從網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)且輸出之；2）從網(wǎng)中刪除該頂點(diǎn)及其所有出邊；3）執(zhí)行(1)(2)，直至所有頂點(diǎn)已輸出，或網(wǎng)中剩余頂點(diǎn)入度均不為0（說明網(wǎng)中存在回路，無法繼續(xù)拓?fù)渑判?。因此拓?fù)渑判蛩惴捎脕砼袛嘤邢驁D是否存在回路）。我們假定AOV網(wǎng)用鄰接表的形式存儲(chǔ)。為實(shí)現(xiàn)拓?fù)渑判蛩惴?，事先需做好兩?xiàng)準(zhǔn)備工作:1）建立一個(gè)數(shù)組count[]，count[i]的元素值取對(duì)應(yīng)頂點(diǎn)i的入度；2）建立一個(gè)堆棧，棧中存放入度為0的頂點(diǎn)，當(dāng)一個(gè)頂點(diǎn)的入度為0，就將其壓入棧。事實(shí)上,我們可以不為該頂點(diǎn)棧另外分配存儲(chǔ)空間,而是直接利用入度為0的頂點(diǎn)的count[]數(shù)組元素的值來模擬堆棧的壓入和彈出。（1）設(shè)置一個(gè)“棧頂指針”top，以指示當(dāng)前“棧頂”位置（這里的“?！笔悄M的，實(shí)際并不存在真正的堆棧）；（2）初始化“?！睍r(shí)，top值設(shè)為-1，表示“?！笨?，對(duì)應(yīng)如下語句:top=-1;（3）當(dāng)頂點(diǎn)i的入度為0，應(yīng)該進(jìn)“棧”時(shí)，將“棧頂指針”所指的頂點(diǎn)序號(hào)放在count[i]中，并更新“棧頂指針”top，令其指向頂點(diǎn)i:count[i]=top;top=i;（4）當(dāng)應(yīng)該從“棧”中彈出一個(gè)頂點(diǎn)時(shí)，把原“棧頂”位置記錄下來，top退到“次棧頂”。j=top;top=count[top];入度為0的頂點(diǎn)均要被壓入“?！?故每一次“彈出”的頂點(diǎn)（top所指向的頂點(diǎn)）入度都是0,顯然,頂點(diǎn)的被彈出次序?qū)嶋H是“棧頂”指針top的變化次序,也就是拓?fù)渑判驎r(shí)頂點(diǎn)的輸出次序。如果“棧頂指針”top值變成-1,而頂點(diǎn)卻未被全部輸出,說明網(wǎng)中有回路,此時(shí)算法強(qiáng)制終止拓?fù)渑判?。算法TopoOrder(n) FORi=1TOnDOcount[i]0.FORi=1TOnDO (padjacent(Head[i]). WHILEp≠????????DO(count[VerAdj(p)]count[VerAdj(p)]+1. plink(p).))top-1. FORi=1TOnDO IFcount[i]=0THEN(count[i]top.topi.) FORi=1TOnDO IFtop=-1THEN (PRINT"Thereisacycleinnetwork!".RETURN.)ELSE (jtop. topcount[top] PRINT"j". padjacent(Head[j]). WHILEp≠????????DO (kVerAdj(p). count[k]count[k]-1. IFcount[k]=0THEN (count[k]top.topk.)