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

Question

我有一个像这样的多级依赖关系图，我需要检测该图中的任何循环引用。

A = B

乙=丙

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

Topological sorting .维基百科上的描述很清楚，适用于您的所有示例。

基本上，您从一个没有依赖项的节点开始，将其放入已排序节点列表中，然后从每个节点中删除该依赖项。对于您的第二个示例，这意味着您从 1 开始。一旦您删除了对 1 的所有依赖项，您就剩下 2。您最终将它们排序为 1,2,3,4,5 并看到没有循环。

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