如何处理递归逻辑

问题:一个任务Task可以存在几个先置任务:
如TaskA有俩个先置任务TaskB、TaskC,
先置任务的意思是,在执行A任务之前,TaskB与TaskC必须先处理,那么这样就存在一个问题:
如果用户设置TaskA的先置任务是TaskB,但是在TaskB的先置任务是TaskC,TaskC的先置任务是TaskA,这样在启动任何一个任务的时候,都必须要先处理先置任务,这样就进入了一个死循环。

假设现在是为TaskA设置先置任务,向处理方法内传入List<Long>类型的先置任务ID,对于这个可能存在循环依赖的问题,有什么好的解决办法吗?
想听听大佬的思路。

阅读 231
评论
    3 个回答

    那其实挺简单的,当作类似于树形结构(要新建的任务作为根节点、前置任务们作为子节点,前置任务的前置任务们作为孙节点),做按层遍历即可,看是否有中间某个节点的子节点指向的是根节点,如果有,就说明死循环了,跳出遍历结束判断即可;直到所有层都遍历结束后都没找到第二个根节点,就说明没死循环。

    如图所示,正常的、无死循环的树状结构(假设一个任务可以充当多个任务的前置任务,即树的节点可以重复):

    image.png

    展开后就变为:

    image.png

    如果存在死循环,则结构会变为:

    image.png

    展开后就不画了,意思你明白就行,就是根节点已经出现多次了。

    这里只画了三层,应该可以表达清楚了吧?总之一层一层找,找到第二个根节点了就跳出(已经死循环了),找不到就去下一层继续找,直到遍历结束。

    P.S. 你可能会问如果不是根节点(即不是当前要新建的任务)产生循环,而是原来就有死循环怎么办。但如果你已经建好的任务也是按照上面的方式做了判断的话,压根是不会出现死循环的,所以你每次只需要确保最新的这个不出现死循环就行了。

    P.S. 这是每层遍历的解法,其实前序或后序遍历也行,甚至能有性能优化,你可以自己琢磨一下。

      任务依赖关系相当于一个有向图,循环依赖即表示存在环。搜索“有向图,环”即可得到答案。

        任务ID放入LinkedList中,重复则死循环了

          撰写回答

          登录后参与交流、获取后续更新提醒

          相似问题
          推荐文章