網(wǎng)樹(shù)求解有向無(wú)環(huán)圖中具有長(zhǎng)度約束的簡(jiǎn)單路徑和最長(zhǎng)路徑問(wèn)題

1、第卷第期計(jì)算機(jī)學(xué)報(bào)Vol.No.20年？月CHINESEJOURNALOFCOMPUTERS.20———————————————收稿日期：年月日投稿時(shí)不填寫(xiě)此項(xiàng)；最終修改稿收到日期：年月日投稿時(shí)不填寫(xiě)此項(xiàng).本課題得到國(guó)家自然科學(xué)基金(61072100)；國(guó)家自然科學(xué)基金(51107029)；河北省自然科學(xué)基金(G2010000165)資助.李艷，女，1975年生，博士，Email:lywuc@，副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘與智能計(jì)算.

2、孫樂(lè)，男，1986年生，研究生，Email:lelelele86@，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘與智能計(jì)算.朱懷忠，男，1978年生，碩士，Email:t.，講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘與智能計(jì)算.武優(yōu)西（通信作者），男，1974年生，博士，Email:wuc567@，教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘與智能計(jì)算.通訊作者：武優(yōu)西電話(huà)：13116179687網(wǎng)樹(shù)求解有向無(wú)環(huán)圖中具有長(zhǎng)度約束的簡(jiǎn)單路徑和最長(zhǎng)路徑問(wèn)題李艷1)孫樂(lè)2)朱懷忠2)武優(yōu)西2)

3、1)(河北工業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院天津中國(guó)300401)2)(河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院天津中國(guó)300401)摘要具有長(zhǎng)度約束的簡(jiǎn)單路徑問(wèn)題(SimplePathswithLengthConstraintSPLC)是指求解圖G中任意兩點(diǎn)間路徑長(zhǎng)度為m的簡(jiǎn)單路徑數(shù)，是kpath問(wèn)題的一種特殊情況。本文基于網(wǎng)樹(shù)數(shù)據(jù)結(jié)構(gòu)提出了在有向無(wú)環(huán)圖中求解SPLC問(wèn)題的算法(treefSPLCinDirectedAcyclicGraphsNSPLCDA

4、G)。網(wǎng)樹(shù)是一種多樹(shù)根多雙親的數(shù)據(jù)結(jié)構(gòu)。NSPLCDAG算法將該問(wèn)題轉(zhuǎn)化為一棵網(wǎng)樹(shù)后，利用樹(shù)根路徑數(shù)這一性質(zhì)對(duì)其進(jìn)行求解。對(duì)NSPLCDAG算法進(jìn)行改造，可以對(duì)最長(zhǎng)路徑問(wèn)題進(jìn)行求解，形成了網(wǎng)樹(shù)在有向無(wú)環(huán)圖中求解最長(zhǎng)路徑算法(treeftheLongestPathinDAGsNLPDAG)，NLPDAG算法可找到所有的最長(zhǎng)路徑，在對(duì)NLPDAG算法做進(jìn)一步改進(jìn)以形成改進(jìn)的NLPDAG算法，改進(jìn)的NLPDAG算法可在線(xiàn)性時(shí)間復(fù)雜度內(nèi)給出有向

5、無(wú)環(huán)圖中的一條最長(zhǎng)路徑。實(shí)驗(yàn)結(jié)果驗(yàn)證了NSPLCDAG和改進(jìn)的NLPDAG算法的正確性與有效性。關(guān)鍵詞有向無(wú)環(huán)網(wǎng)絡(luò)；簡(jiǎn)單路徑；長(zhǎng)度約束；最長(zhǎng)路徑；網(wǎng)樹(shù)中圖法分類(lèi)號(hào)DOI號(hào)：AtreefSimplePathswithLengthConstrainttheLongestPathinDirectedAcyclicGraphsLIYan1)SUNLe2)ZHUHuaiZhong2)WUYouXi2)1)(SchoolofEconomicsMan

6、agementHebeiUniversityofTechnologyTianjin300401China)2)(SchoolofComputerScienceEngineeringHebeiUniversityofTechnologyTianjin300401China)AbstractTheproblemofSimplePathswithLengthConstraint(SPLC)istocalculatethenumberofsim

7、plepathsbetweentwoverticesunderthelengthconstraintminthegraph.Itisaspecialcaseofthekpathproblem.IndertosolvetheprobleminDirectedAcyclicGraphs(DAGs)thispaperproposesanalgithmnamedtreefSimplePathswithLengthConstraintinDAGs

8、(NSPLCDAG)basedonadatastructureoftreewhichmayhavemethanonerootoneparent.FirstNSPLCDAGtransfmsthegraphintoatree.Thentheconceptofthenumberofrootpathsoftreeisusedtosolvetheproblem.BasedonNSPLCDAGanewalgithmnamedtreeftheLong

9、estPathinDAGs(NLPDAG)isconstructedwhichcanfindallthelongestpaths.ThenNLPDAGisimprovedtheimprovedNLPDAGcanfindoneofthelongestpathswithlineartimecomplexity.Theexperimentalresultsverifythecrectnesseffectivenessofthetwoalgit

10、hmsofNSPLCDAGtheimprovedNLPDAG.Keywdsdirectedacyclicgraphssimplepathlengthconstraintthelongestpathtree期李艷等：網(wǎng)樹(shù)求解有向無(wú)環(huán)圖中具有長(zhǎng)度約束的簡(jiǎn)單路徑和最長(zhǎng)路徑問(wèn)題3NSPLCDAG算法的時(shí)間復(fù)雜度和空間復(fù)雜度，并通過(guò)示例來(lái)說(shuō)明算法的工作原理；第5節(jié)提出了最長(zhǎng)路徑的求解算法并給出了求解示例；第6節(jié)給出了實(shí)驗(yàn)結(jié)果及分析；第7節(jié)得出了本

11、文結(jié)論。2問(wèn)題的定義定義1.圖G=(VE)，其中V稱(chēng)為頂點(diǎn)集，E稱(chēng)為邊集。從頂點(diǎn)v到頂點(diǎn)v’的路徑是一個(gè)有序頂點(diǎn)序列S=v=v0v1…vm=v’，其中頂點(diǎn)序列應(yīng)滿(mǎn)足E(1jm)。路徑長(zhǎng)度是路徑中???有向邊的數(shù)目。如果序列S中任何兩個(gè)頂點(diǎn)不重復(fù)出現(xiàn)，則稱(chēng)此路徑為簡(jiǎn)單路徑。定義2.具有長(zhǎng)度約束的簡(jiǎn)單路徑SPLC問(wèn)題是指在圖G=(VE)及圖中任意兩點(diǎn)uvV和一個(gè)?正整數(shù)m，求解從u到v路徑長(zhǎng)度為m的簡(jiǎn)單路徑數(shù)問(wèn)題。SPLCinDAGs是指在

12、給定的有向無(wú)環(huán)圖中求解SPLC問(wèn)題。定義3.鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，圖G采用鄰接矩陣存儲(chǔ)。二維數(shù)組元素g[i][j]=1(1ijnn=|V|)表示頂點(diǎn)i到頂點(diǎn)j之間存??在一條有向邊，否則表示頂點(diǎn)i到頂點(diǎn)j之間無(wú)邊。頂點(diǎn)vi的出度(用OD(vi)表示)是第i行的元素之和，計(jì)算公式如下：(1)????10]][[)(njijigvOD頂點(diǎn)vi的入度(用ID(vi)表示)是第i列的元素之和，計(jì)算公式如下：(2)????10]]

13、[[)(njiijgvID例1.如圖1所示的有向無(wú)環(huán)圖其頂點(diǎn)個(gè)數(shù)n=9，求從頂點(diǎn)1到頂點(diǎn)7路徑長(zhǎng)度約束為m=4的簡(jiǎn)單路徑數(shù)。圖1一個(gè)有向無(wú)環(huán)圖從圖1可以看出，頂點(diǎn)1到7路徑長(zhǎng)度約束為4的路徑數(shù)為10，即12437、12367、14367、12587、14587、14987、15987、12497、12597和14597。SPLCinDAGs問(wèn)題的求解難度在于，頂點(diǎn)u和v之間的路徑數(shù)呈現(xiàn)指數(shù)形式，因此不能采用窮舉法列出所有可能的路徑并判定

14、路徑長(zhǎng)度是否滿(mǎn)足約束條件來(lái)進(jìn)行求解，本文采用網(wǎng)樹(shù)這一數(shù)據(jù)結(jié)構(gòu)進(jìn)行求解。3網(wǎng)樹(shù)的定義及性質(zhì)本節(jié)給出了網(wǎng)樹(shù)的定義和性質(zhì)。定義4.網(wǎng)樹(shù)數(shù)據(jù)結(jié)構(gòu)是結(jié)點(diǎn)的集合，這個(gè)集合可以為空集，否則這個(gè)集合由若干不同的根結(jié)點(diǎn)r1…rm和0或很多非空子網(wǎng)樹(shù)T1T2…Tn構(gòu)成，這些子網(wǎng)樹(shù)的樹(shù)根至少存在一條邊與網(wǎng)樹(shù)的根結(jié)點(diǎn)ri相連接，這里1m1n且1in。????圖2給出了一棵一般意義上的網(wǎng)樹(shù)。r1rm…T1T2Tn…圖2一棵網(wǎng)樹(shù)網(wǎng)樹(shù)具有如下5個(gè)性質(zhì)[1315]：(

15、1)網(wǎng)樹(shù)是樹(shù)結(jié)構(gòu)的拓展，它具備很多與樹(shù)相似的概念，如根結(jié)點(diǎn)，葉子結(jié)點(diǎn)，層，雙親，孩子等；(2)一棵網(wǎng)樹(shù)可以有n個(gè)根結(jié)點(diǎn)，其中n1；?(3)除了根結(jié)點(diǎn)之外，網(wǎng)樹(shù)的其它結(jié)點(diǎn)可以有多個(gè)雙親結(jié)點(diǎn)；(4)從一個(gè)結(jié)點(diǎn)到達(dá)網(wǎng)樹(shù)的一個(gè)根結(jié)點(diǎn)的路徑數(shù)不唯一；(5)同一結(jié)點(diǎn)可以在網(wǎng)樹(shù)的不同層上多次出現(xiàn)。定義5.由于同一結(jié)點(diǎn)可以在網(wǎng)樹(shù)的不同層上多次出現(xiàn)，為了更好地區(qū)分網(wǎng)樹(shù)結(jié)點(diǎn)，這里用nij來(lái)表示第j層的結(jié)點(diǎn)i。定義6.從結(jié)點(diǎn)nij到達(dá)根結(jié)點(diǎn)的路徑數(shù)稱(chēng)為樹(shù)根路