摘要
针对在已有传递闭包的基础上新增序偶后的传递闭包求解问题,提出了一种基于新增序偶的传递闭包求解算法,并给出了详细证明过程.该算法在已有的传递闭包基础上,通过把新增序偶及该序偶的所有派生间接指向序偶添加到已有的传递闭包中实现求解过程,从而使算法的时间复杂度降低为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 .
出处
《仲恺农业工程学院学报》
CAS
2014年第2期23-26,共4页
Journal of Zhongkai University of Agriculture and Engineering
基金
广东省自然科学基金(S2012010009976)
广东省科技计划(2011B040200074)
湛江市科技攻关计划(2011C3105001)资助项目
关键词
传递闭包
新增序偶
二元关系
时间复杂度
transitive closure
new ordered couples
binary relation
time complexity
