【摘要】 针对在已有传递闭包的基础上删除序偶后的传递闭包求解问题,提出一种基于传递闭包的传递闭包动态求解算法,给出了其形式化描述形式,并给出了算法的详细证明过程。该算法在已有的传递闭包基础上,通过把新删除序偶及该序偶的所有依赖间接指向序偶从已有传递闭包中删除实现求解过程,从而使算法的时间复杂度降低为O(n2),并且不受稀疏矩阵或序偶链的链长等不确定因素影响,最后通过一个实例说明了该算法的执行过程。更多还原

【Abstract】 Aiming at the problem of transitive closure based on present transitive closure and deleted ordered couple,a dynamic algorithm of transitive closure based on present transitive closure is proposed and designed,and is proven in detail,the formal description of the algorithm is also given.In order to get the new transitive closure,the new deleted ordered couple and all dependency indirection ordered couple are deleted from the present transitive closure,so that the time complexity of the algorithm is reduced toO(n2),and isn’t affected by uncertain factors,such as sparse matrix and the length of ordered couple chain.Finally,an example is given to account for the execution of the algorithm.更多还原