基于新增序偶的传递闭包求解算法  

A transitive closure solution algorithm based on new ordered couples

作　　者：张世龙[1] 唐雅娜[1] 邹阿金[2] 

机构地区：[1]仲恺农业工程学院信息科学与技术学院,广东广州510225 [2]广东海洋大学信息学院,广东湛江524088

出　　处：《仲恺农业工程学院学报》2014年第2期23-26,共4页Journal of Zhongkai University of Agriculture and Engineering

基　　金：广东省自然科学基金(S2012010009976);广东省科技计划(2011B040200074);湛江市科技攻关计划(2011C3105001)资助项目

摘　　要：针对在已有传递闭包的基础上新增序偶后的传递闭包求解问题,提出了一种基于新增序偶的传递闭包求解算法,并给出了详细证明过程.该算法在已有的传递闭包基础上,通过把新增序偶及该序偶的所有派生间接指向序偶添加到已有的传递闭包中实现求解过程,从而使算法的时间复杂度降低为O(n2),并且不受稀疏矩阵或序偶链的链长等不确定因素影响,最后通过一个实例说明了该算法的执行过程.A transitive closure solution algorithm based on new ordered couples was proposed , which aimed to solve transitive closure problems after adding new ordered couples to current transitive closure . The demonstration process was provided as well .In order to solve the problem , the new ordered couples and all the derivatives indirectly pointed to the ordered couples were added to the existing transitive clo -sure.Thus, the time complexity of the algorithm can be reduced to O （n^2）, while the algorithm will not be affected by sparse matrix or chain length of ordered couple chain .Finally, an example was given to il-lustrate the execution of the algorithm .

关 键 词：传递闭包 新增序偶 二元关系 时间复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]