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

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

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

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

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

5、無環(huán)圖中的一條最長路徑。實驗結果驗證了NSPLCDAG和改進的NLPDAG算法的正確性與有效性。關鍵詞有向無環(huán)網(wǎng)絡；簡單路徑；長度約束；最長路徑；網(wǎng)樹中圖法分類號DOI號：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)樹求解有向無環(huán)圖中具有長度約束的簡單路徑和最長路徑問題3NSPLCDAG算法的時間復雜度和空間復雜度，并通過示例來說明算法的工作原理；第5節(jié)提出了最長路徑的求解算法并給出了求解示例；第6節(jié)給出了實驗結果及分析；第7節(jié)得出了本

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

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

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

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

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