资源描述：
《网树求解有向无环图中具有长度约束的简单路径和最长路径问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、?期李艳等：网树求解有向无环图中具有长度约束的简单路径和最长路径问题11网树求解有向无环图中具有长度约束的简单路径和最长路径问题李艳1),孙乐2),朱怀忠2),武优西2)1)(河北工业大学经济管理学院,天津中国300401)2)(河北工业大学计算机科学与软件学院,天津中国300401)摘要具有长度约束的简单路径问题(SimplePathswithLengthConstraint,SPLC)是指求解图G中任意两点间路径长度为m的简单路径数，是k-path问题的一种特殊情况。本文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(NettreeforSPLCinDire
2、ctedAcyclicGraphs,NSPLCDAG)。网树是一种多树根多双亲的数据结构。NSPLCDAG算法将该问题转化为一棵网树后，利用树根路径数这一性质对其进行求解。对NSPLCDAG算法进行改造，可以对最长路径问题进行求解，形成了网树在有向无环图中求解最长路径算法(NettreefortheLongestPathinDAGs,NLPDAG)，NLPDAG算法可找到所有的最长路径，在对NLPDAG算法做进一步改进以形成改进的NLPDAG算法，改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径。实验结果验证了NSPLCDAG和改进的NLPDAG算法
3、的正确性与有效性。关键词有向无环网络；简单路径；长度约束；最长路径；网树中图法分类号**** DOI号：ANettreeforSimplePathswithLengthConstraintandtheLongestPathinDirectedAcyclicGraphsLIYan1),SUNLe2),ZHUHuai-Zhong2),WUYou-Xi2)1)(SchoolofEconomicsandManagement,HebeiUniversityofTechnology,Tianjin300401,China)2)(SchoolofComputerScienceandE
4、ngineering,HebeiUniversityofTechnology,Tianjin300401,China)AbstractTheproblemofSimplePathswithLengthConstraint(SPLC)istocalculatethenumberofsimplepathsbetweentwoverticesunderthelengthconstraintminthegraph.Itisaspecialcaseofthek-pathproblem.InordertosolvetheprobleminDirectedAcyclicGraphs(DA
5、Gs),thispaperproposesanalgorithmnamedNettreeforSimplePathswithLengthConstraintinDAGs(NSPLCDAG)basedonadatastructureofNettreewhichmayhavemorethanonerootandoneparent.FirstNSPLCDAGtransformsthegraphintoaNettree.ThentheconceptofthenumberofrootpathsofNettreeisusedtosolvetheproblem.BasedonNSPLCD
6、AG,anewalgorithmnamedNettreefortheLongestPathinDAGs(NLPDAG)isconstructedwhichcanfindallthelongestpaths.ThenNLPDAGisimprovedandtheimprovedNLPDAGcanfindoneofthelongestpathswithlineartimecomplexity.TheexperimentalresultsverifythecorrectnessandeffectivenessofthetwoalgorithmsofNSPLCDAGandtheimp
7、rovedNLPDAG.Keywordsdirectedacyclicgraphs;simplepath;lengthconstraint;thelongestpath;nettree?期李艳等：网树求解有向无环图中具有长度约束的简单路径和最长路径问题111引言图是一种比线性表和树更为复杂的数据结构。在线性表中，结点间为单前驱单后继的线性关系；在树结构中，结点间为单前驱多后继的非线性关系；而在图结构中，结点间则为多前驱多后继的非线性关系，图中任意两个结点之间都可能相关。因此，图已经被广泛应用于诸如语言学、逻辑学、物
