如何在多级引用和依赖项中检测循环逻辑或递归

Question

我有一个像这样的多级依赖图,我需要在这个图中检测任何循环引用.

A = B.

B = C.

C = [D,B]

D = [C,A]

有人有这样的问题吗？

有什么办法吗

谢谢,对不起英语.

=========更新==========

我有另一种情况.

1

2 = 1

3 = 2

4 = [2,3]

5 = 4

在这种情况下,我的递归代码在"4"引用中迭代两次,但是这个引用不会生成无限循环.我的问题是知道函数何时迭代多次引用并且不是无限循环,何时是无限循环,以通知用户.

1 = 4

2 = 1

3 = 2

4 = [2,3]

5 = 4

这种情况与第二个例子有点不同.这会产生无限循环.我怎么知道案件何时产生无限循环？

Answer 1

拓扑排序.维基百科上的描述很清楚,适用于您的所有示例.

基本上,您从一个没有依赖项的节点开始,将它放在已排序节点的列表中,然后从每个节点中删除该依赖项.对于你的第二个例子,这意味着你从1开始.一旦你删除所有依赖关系1你剩下2.你最终排序他们1,2,3,4,5并看到没有周期.

对于您的第三个示例,每个节点都有一个依赖项,因此无处可寻.这样的图必须包含至少一个循环.

Answer 2

保留唯一标识的节点列表。尝试遍历整个树，但继续检查列表中的节点，直到您将一个节点称为子节点，该节点已经存在于唯一列表中 - 从那里获取它（根据您的要求处理循环或简单地忽略它）