上傳人：1***

認(rèn)證信息

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

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

IP屬地：廣東

IP屬地：廣東 上傳時(shí)間：2023-09-15 格式：DOCX 頁(yè)數(shù)：3 大?。?8.38KB 積分：12 舉報(bào) 版權(quán)申訴

有向圖中有偏誤的拓?fù)渑判蛩惴?/p>

事實(shí)上，大多數(shù)人使用圖紙來(lái)表達(dá)項(xiàng)目的結(jié)構(gòu)。圖中用頂點(diǎn)表示活動(dòng)(子工程),用有向邊表示活動(dòng)間的優(yōu)先關(guān)系,這樣的有向圖被稱為AOV網(wǎng)(activityonvertexnetwork)。在AOV網(wǎng)中,如果從頂點(diǎn)i到頂點(diǎn)j之間存在一條有向路徑,則稱頂點(diǎn)i是頂點(diǎn)j的前趨,或稱頂點(diǎn)j是頂點(diǎn)i的后繼。如果〈i,j〉是網(wǎng)中的一條弧,則稱i是j的直接前趨,或稱j是i的直接后繼。一個(gè)頂點(diǎn)如果沒(méi)有前趨頂點(diǎn),則該頂點(diǎn)所表示的子工程可獨(dú)立于整個(gè)工程,即該子工程的開(kāi)工不受其他子工程的約束。否則,一個(gè)子工程的開(kāi)工必須以其前趨頂點(diǎn)所代表的子工程的完工為前提條件。一個(gè)AOV網(wǎng)中如果存在回路,這就意味著某個(gè)子工程的開(kāi)工要以自身的完工為前提條件,這顯然是矛盾的。所以,我們要對(duì)某個(gè)工程的施工流程進(jìn)行可行性論證,首先必須檢測(cè)相應(yīng)的AOV網(wǎng)是否存在回路,而這個(gè)工作,就是由拓?fù)渑判騺?lái)完成的。因此,拓?fù)渑判蛩惴ǖ难芯亢陀懻撌呛苡袑?shí)際意義的。1拓?fù)渑判蜻^(guò)程使AOV網(wǎng)中的各個(gè)頂點(diǎn)排成一個(gè)線性序列,該序列保持各個(gè)頂點(diǎn)原有的優(yōu)先關(guān)系,而對(duì)于原先沒(méi)有先后關(guān)系的頂點(diǎn)則建立起人為的先后關(guān)系,這個(gè)排序過(guò)程稱為拓?fù)渑判?。拓?fù)渑判虻乃惴ㄋ枷胪ǔＪ侨缦旅枋龅?1)在AOV網(wǎng)中選一個(gè)沒(méi)有前趨的頂點(diǎn)且輸出之。2)在網(wǎng)中刪去該頂點(diǎn)及其所發(fā)出的弧。3)重復(fù)1),2),直至輸出全部沒(méi)有前趨的頂點(diǎn)。當(dāng)過(guò)程結(jié)束時(shí),如果網(wǎng)中的所有頂點(diǎn)均已輸出,則說(shuō)明網(wǎng)中不存在回路,否則說(shuō)明網(wǎng)中存在回路,相應(yīng)的工程是不可行的。2表頭點(diǎn)對(duì)點(diǎn)編碼拓?fù)渑判蜉^經(jīng)典的算法是采用鄰接鏈表作為AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)。這種結(jié)構(gòu)可用PASCAL語(yǔ)言說(shuō)明如下:對(duì)應(yīng)于圖1的AOV網(wǎng),相應(yīng)的鄰接鏈表如圖2所示。在這種鄰接鏈表中,表頭結(jié)點(diǎn)的vex域中存放的是相應(yīng)頂點(diǎn)的入度。于是,選取沒(méi)有前趨的頂點(diǎn)即是掃描表頭結(jié)點(diǎn)數(shù)組,尋找入度為0的頂點(diǎn);刪除從某頂點(diǎn)所發(fā)出的弧即為把該弧所到達(dá)頂點(diǎn)的入度減1。為了提高算法的執(zhí)行效率,對(duì)表頭結(jié)點(diǎn)數(shù)組可只掃描一遍,把檢測(cè)到的所有入度為0的頂點(diǎn)存入一個(gè)棧中;同時(shí),為了節(jié)省存儲(chǔ)空間,把這個(gè)棧就建立在表頭結(jié)點(diǎn)的入度域值已為0的那些單元上。這個(gè)算法的時(shí)、空復(fù)雜性均為O(n+e)(其中n,e分別為AOV網(wǎng)的頂點(diǎn)數(shù)和邊數(shù)),是一個(gè)很不錯(cuò)的算法。我們?cè)诮虒W(xué)中,為了啟發(fā)學(xué)生的思維,提出了若干改進(jìn)的做法,針對(duì)下面兩種情況對(duì)存儲(chǔ)結(jié)構(gòu)作出改變。1aov網(wǎng)的存儲(chǔ)結(jié)構(gòu)分析這時(shí),可采用如下的存儲(chǔ)結(jié)構(gòu):采用上述存儲(chǔ)結(jié)構(gòu),記錄中next是一個(gè)集合類型的變量,該集合變量中的元素即是相關(guān)頂點(diǎn)發(fā)出弧所對(duì)應(yīng)的到達(dá)頂點(diǎn)。對(duì)于圖1的AOV網(wǎng),其存儲(chǔ)結(jié)構(gòu),如圖3所示。相應(yīng)的程序如下所示:由于集合變量是用一個(gè)位串來(lái)表示的,其運(yùn)算速度也較快。所以,在上述情況下,此程序的時(shí)、空復(fù)雜度是有所減小的。2到達(dá)中心和進(jìn)入中心在這樣的存儲(chǔ)結(jié)構(gòu)里,如果頂點(diǎn)i所發(fā)出的弧是〈i,j1〉,〈i,j2〉,…,〈i,jl〉,(l<=max2),則把以上這些弧的到達(dá)頂點(diǎn)j1,j2,…jl依此存放在數(shù)組al[i].next的各個(gè)分量中。在這個(gè)程序中,當(dāng)一個(gè)沒(méi)有前趨的頂點(diǎn)K(棧頂元素)被輸出后,由于從頂點(diǎn)K發(fā)出的弧所到達(dá)的頂點(diǎn)號(hào)依此存放在al[k].next各個(gè)分量中,所以,刪除從頂點(diǎn)K所發(fā)出的弧即將數(shù)組al[k].next各分量中的頂點(diǎn)的入度減1,程序結(jié)構(gòu)清晰,易于理解。3ov網(wǎng)的e條有向邊AOV網(wǎng)也可以用一個(gè)鄰接矩陣來(lái)表示。相應(yīng)于圖1的AOV網(wǎng),可以用矩陣A的鄰接矩陣加以表示。在這樣的存儲(chǔ)結(jié)構(gòu)上,矩陣第j列的元素之和即是頂點(diǎn)j的入度,當(dāng)檢測(cè)到某列j的元素之和為0,則頂點(diǎn)j即可輸出,要?jiǎng)h除所有從頂點(diǎn)j所發(fā)出的弧即是把第j行的所有元素全令為0。文獻(xiàn)給出了相應(yīng)算法,并進(jìn)而加以優(yōu)化,提出用一個(gè)二維數(shù)組來(lái)存儲(chǔ)AOV網(wǎng)的e條有向邊,如矩陣B所示。A=??????????000000100000110000100000001001001100???????????B=???????????????1112334623435665???????????????A=(011100001000000011000001000000000010)?B=(1213142335364665)采用這樣的存儲(chǔ)結(jié)構(gòu),若某一頂點(diǎn)號(hào)K不出現(xiàn)在矩陣B的第2列中,則說(shuō)明頂點(diǎn)K的入度為0,即可輸出。要?jiǎng)h除從頂點(diǎn)K所發(fā)出的弧,則可處理為將矩陣B第1列中值為K的元素所在行的第2列也令為K。這樣,同時(shí)又標(biāo)記了頂點(diǎn)K已被輸出。算法的設(shè)計(jì)是很巧妙的,而且,其空間復(fù)雜為O(e),也有不小的改進(jìn)。但運(yùn)算量比較大,每選取一個(gè)入度為0的頂點(diǎn)需掃描一遍數(shù)組的第2列,刪除輸出頂點(diǎn)和從該頂點(diǎn)所發(fā)出的弧又需掃