在列表词典中查找周期

Question

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

我的字典的一个示例是：

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

每个ID键的值是它引用的其他ID的列表，它们无法自行引用。

因此，如果有循环参考，输出将是：

{3, 4 , 3}.

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

Answer 1

NetworkX库可以在图表中找到周期。您需要实例化有向图，因为ID之间的链接是单向的。您的图中有多个周期。例如，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），以便我参考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（即我是否也在d [j]中），如果是，则打印i和j。您只有在i＆lt； J，为了不打印每个周期两次。

如果您还要打印较大长度的圆形引用（例如i引用j，j引用k和k引用i时），则可以用edge set {（i，j）构造有向图：我参考j} ，并运行算法（例如 Johnson的算法） Digraph。