网树求解有向无图中具有长度约束的简单路径和最长路径问题.doc

网树求解有向无环图中具有长度约束的简单路径和最长路径问题 李艳1), 孙乐2), 朱怀忠2) , 武优西2) 1)( 河北工业大学 经济管理学院, 天津 中国 300401) 2)(河北工业大学 计算机科学与软件学院, 天津 中国 300401) 摘 要 具有长度约束的简单路径问题(Simple Paths with Length Constraint, SPLC)是指求解图G中任意两点间路径长度为m的简单路径数，是k-path 问题的一种特殊情况。本文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs, NSPLCDAG)。网树是一种多树根多双亲的数据结构。NSPLCDAG算法将该问题转化为一棵网树后，利用树根路径数这一性质对其进行求解。对NSPLCDAG算法进行改造，可以对最长路径问题进行求解，形成了网树在有向无环图中求解最长路径算法(Nettree for the Longest Path in DAGs, NLPDAG)，NLPDAG算法可找到所有的最长路径，在对NLPDAG算法做进一步改进以形成改进的NLPDAG算法，改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径。实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性。 关键词 有向无环网络；简单路径；长度约束；最长路径；网树 中图法分类号 ****　　　DOI号： A Nettree for Simple Paths with Length Constraint and the Longest Path in Directed Acyclic Graphs LI Yan1), SUN Le2) , ZHU Huai-Zhong2) , WU You-Xi2) 1)(School of Economics and Management, Hebei University of Technology, Tianjin 300401, China) 2)(School of Computer Science and Engineering, Hebei University of Technology, Tianjin 300401, China) Abstract The problem of Simple Paths with Length Constraint (SPLC) is to calculate the number of simple paths between two vertices under the length constraint m in the graph. It is a special case of the k-path problem. In order to solve the problem in Directed Acyclic Graphs (DAGs), this paper proposes an algorithm named Nettree for Simple Paths with Length Constraint in DAGs (NSPLCDAG) based on a data structure of Nettree which may have more than one root and one parent. First NSPLCDAG transforms the graph into a Nettree. Then the concept of the number of root paths of Nettree is used to solve the problem. Based on NSPLCDAG, a new algorithm named Nettree for the Longest Path in DAGs (NLPDAG) is constructed which can find all the longest paths. Then NLPDAG is improved and the improved NLPDAG can find one of the longest paths with linear time complexity. The experimental results verify the correctness and effectiveness of the two algorithms of NSPLCDAG and the improved NLPDAG. Key words