在列表字典中查找循环

Question

我有一个 python id 字典。每个 id 都有一组它引用的其他 id。如何在字典中找到循环引用？

我的字典的一个例子是：

{1: [3], 2: [1], 3: [2, 4], 4: [2, 3]}.

每个 id 键的值是它引用的其他 id 的列表，它们不能引用自己。

因此，如果存在循环引用，输出将是：

{3, 4 , 3}.

我正在努力弄清楚如何解决这个问题，因为这似乎是一个常见问题！非常感谢任何提供帮助的人。

Answer 1

networkx 库可以在您的图表中找到循环。您将需要实例化一个有向图，因为您的 ID 之间的链接是 one-way。您的图表中有多个循环。比如3到4，4到3，也算是一个循环

import networkx as nx

data = {1: [3], 2: [1], 3: [2, 4], 4: [2, 3]}
graph = nx.DiGraph(data)

list(nx.simple_cycles(graph))
# returns:
[[1, 3, 4, 2], [1, 3, 2], [3, 4]]

Answer 2

如果您正在寻找长度仅为 2 的循环引用，即仅针对 (i,j) 对，这样 i 引用 j 并且 j 引用 i，那么下面的代码有效：

d = {1: [3], 2: [1], 3: [2, 4], 4: [2, 3]}

for i in d:
    for j in d[i]:
        if i in d[j]:
            print("Cycle found: ", i, j)

输出：

Cycle found:  3 4
Cycle found:  4 3

上面的程序做了以下工作：对于字典中的每个键i，如果i引用了j，那么检查j是否也引用了i（即i是否也在d[j]中），如果是，则打印我和j。您可以扩充程序以仅在 i < j 时存储（或打印）(i,j)，以免每个循环打印两次。

如果你还想打印更大长度的循环引用（比如当i引用j，j引用k，k引用i），那么你可以构建边集{(i,j)的有向图: i 引用 j}，以及运行一种算法（例如 Johnson's algorithm) 以查找有向图中的所有基本循环。

在列表字典中查找循环

Finding cycles in a dictionary of lists

python

dictionary

circular-dependency

circular-reference