依赖关系算法

前端之家收集整理的这篇文章主要介绍了依赖关系算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

关系依赖算法



一、引言

昨天,因为工作需要,在处理对多个表同时插入时,表与表之间存在依赖关系(即存在外键引用),需要有一个算法对所有相关表进行重新排序,将没有依赖的表先插入,有依赖的表在它所依赖表插入之后,在进行插入操作。引申到生活中,我们平时同样会遇到或多或少的很多事情,它们之前同样存在着千丝万缕的依赖关联。这时候我们同样需要将所有的事情排一下顺序,确定自己是先做什么,后做什么。

二、场景

现在摆在我们面前有几件事情,ABCDEFG,当然,D必须在A完成之后做,我们把这种关系定义为“依赖”,用符号“A-->D”标识,表示事情D是依赖事情A的,这样,它们的关系如下图所示:



三、算法步骤

1、我们确定所有事情清单(简称T),并画出如上类似的关联图形。

事情清单:T(A,B,C,D,E,F,G)

2、列出所有依赖关系清单(简称R)。

依赖关系清单R:左右两边分别标记为RL关系清单和RR关系清单。
A-->G
A-->D
A-->G
B-->C
D-->B
D-->E
F-->E
G-->F
B-->G

3、开始运算。

约定左边为依赖关系清单R,右边为事情清单,分隔符号“|” 前边的事情表示已经排好,后边是等待排的事情。

第一步:开始时,分隔符号在事情清单开始,表示所有事情均等待排序。将等待排序的清单中划掉RR关系清单中出现过的事情,将未划掉的放到分隔符前边,然后从依赖关系清单中同时划掉分隔符前边出现过的关系对,得到第二步,此时事情A已经排好。



第二步:重复第一步,得到第三步,此时事情AD已经排好。



第三步:重复第一步,得到第四步,此时事情ADB已经排好。



第四步:重复第一步,得到第五步,此时事情ADBCG已经排好。



第五步:重复第一步,得到第六步,此时事情ADBCGF已经排好。



第六步:重复第一步,得到第七步,此时事情ADBCGFE已经排好。



第七步:完成。最终事情的执行顺序序列为ADBCGFE,当然这也不是唯一的答案,从第五步我们可以看出,CG是可以互换的,所以ADBGCFE也是最终答案。



四、结论

通过这样一个算法,我们就把事情ABCDEFG都打理清楚了,接下来我们需要做的,就是按照最终执行序列着手去做了。这里就不提供代码实现了,重要的是思想与执行力。


五、注意

当然,该方法是有前提条件的,各个事情之间不能存在两两相互依赖,此时是无解的。例如,场景中A-->C改成C-->A,则存在C-->A-->D-->B-->C,无解。


上文来自:http://blog.csdn.net/cn_gaowei/article/details/7641649

原文链接:https://www.f2er.com/javaschema/284475.html

猜你在找的设计模式相关文章